Title: Code Critique Competition 108

Author: Bob Schmidt

Date: 03 November 2017 16:48:07 +00:00 or Fri, 03 November 2017 16:48:07 +00:00

Summary: Set and collated by Roger Orr. A book prize is awarded for the best entry.

Body: 

Please note that participation in this competition is open to all members, whether novice or expert. Readers are also encouraged to comment on published entries, and to supply their own possible code samples for the competition (in any common programming language) to scc@accu.org.

Note: If you would rather not have your critique visible online, please inform me. (Email addresses are not publicly visible.)

Last issue’s code

I want to collect the meals needed for attendees for a one-day event so I’m reading lines of text with the name and a list of the meals needed, and then writing the totals. However, the totals are wrong – but I can’t see why:

    > meals
    Roger breakfast lunch
    John lunch dinner
    Peter dinner
    
    Total: 3 breakfast: 3 lunch: 2 dinner: 2

There should only be 1 breakfast, not 3!

Please can you help the programmer find the bug – and suggest some possible improvements to the program!

• Listing 1 contains meal.h
• Listing 2 (overleaf) contains meals.cpp

#pragma once
#include <iosfwd>
#include <sstream>
#include <string>
enum class meal : int
{
   breakfast, lunch, dinner,
};

// Used for name <=> value conversion
struct
{
  meal value;
  std::string name;
} names[] =
{
  { meal::breakfast, "breakfast" },
  { meal::lunch, "lunch" },
  { meal::dinner, "dinner" },
};

std::istream &operator>>(std::istream &is, 
  meal &m)
{
  std::string name;
  if (is >> name)
  {
    for (auto p : names)
    {
      if (p.name == name)
        m = p.value;
    }
  }  return is;
}

std::ostream &operator<<(std::ostream &os, 
  meal const m)
{
  for (auto p : names)
  {
    if (p.value == m)
      os << p.name;
  }
  return os;
}

// Type-safe operations
constexpr meal operator+(meal a, meal b)
{
  return meal(int(a) + int(b));
}

meal operator+=(meal &a, meal b)
{
  a = a + b;
  return a;
}

constexpr meal operator|(meal a, meal b)
{
  return meal(int(a) | int(b));
}

constexpr meal operator&(meal a, meal b)
{
  return meal(int(a) & int(b));
}

// Check distinctness
static_assert((meal::breakfast | meal::lunch |
 meal::dinner) == (meal::breakfast +
 meal::lunch + meal::dinner), "not distinct");
			

#include "meal.h"
#include <iostream>
#include <list>
struct attendee
{
   std::string name;
   meal meals; // set of meals
};

using attendees = std::list<attendee>;

attendees get_attendees(std::istream &is)
{
  attendees result;
  std::string line;
  while (std::getline(is, line))
  {
    std::istringstream iss(line);
    std::string name;
    iss >> name;
    meal meal, meals{};
    while (iss >> meal)
      meals += meal; // add in each meal
    if (is.fail())
      throw std::runtime_error("Input error");
    result.push_back({name, meals});
  }
  return result;
}
			

Critiques

Kaartic Sivaraam

The issue seems to be with the ‘enum class’

  enum class meal : int
  {
    breakfast, lunch, dinner,
  };

They have the values of 0, 1, 2 each having ‘at most’ one bit set in binary, of course. The issue is that as ‘breakfast’ has value of 0 it is impossible to distinguish between the one who wants breakfast and who doesn’t. That’s because the expression

  (item.meals & m) == m

always evaluates to true for the value of breakfast (0). The following change would fix the issue.

  enum class meal : int
  {
    breakfast=1, lunch=2, dinner=4,
  };

Further, the following method seems to need a little tweak,

  std::istream &operator>>(std::istream &is,
    meal &m)

It doesn’t seem to be setting the failbit of the is in case it doesn’t identify the ‘valid’ input. I guess the following change fixes that. Correct me, if I’m wrong.

  std::istream &operator>>(std::istream &is,
    meal &m)
  {
    std::string name;
    bool found = false;
    if (is >> name)
    {
      for (auto p : names)
      {
        if (p.name == name) {
          m = p.value;
          found = true;
          break;
        }
      }
    }
    if(!found)
      is.setstate(std::ios::failbit);
    return is;
  }

Nitpicking a little more, the file meal.h doesn’t look like a header though it has the .h suffix, which isn’t such a good thing. It should be split into two files named meal.h and meal.cpp. The file currently named meals.cpp should be renamed to something else more meaningful, probably attendee_meal_requirements.cpp.

Russel Winder

Having looked at the C++ code presented for Code Critique 107, my reaction was WTF. After a moment to collect myself, I realised: C++ is just totally the wrong language with which to attempt the problem as stated. Thus I provide no answer to “Please can you help the programmer find his bug” (*), and thus likely relinquish any possibility of winning this code critique. However for “suggest some other possible problems with their program.” I suggest: the single biggest problem with this code is that it is written in C++.

Clearly I need to follow up on this conclusion with some positive and constructive thoughts.

What language would be good for this problem? The answer is clearly (**) Python (https://www.python.org). In rw_meals.py I provide a program that answers the problem as set by “I”. Python has proper enums and sets, so obviates the need for all the extra code to be found in the C++ files: “I” had some good implementation ideas, but trying to realise them in C++ is, well let us be kind and say non-trivial. Multiple calls of the C++ count function are replaced by a single call of the Python reduce function from the functools package (Python 3 is, of course, assumed here). The brevity and clarity of the Python code mean that it is likely right just by observation. However, given the test data:

 |> rw_meals.py
    Roger breakfast lunch
    John lunch dinner
    Peter dinner
    Total: 3, breakfast: 1, lunch: 2, dinner: 2

we discover the code actually does give the answer expected. Obviously though this is but a single functional test, more tests, unit as well as functional should be provided if the code is to go into service for more than this one occasion.

Of course there will be people unwilling to accept this Python code as a solution because it isn’t native code, or some other third rate excuse of this sort. OK, I shall cope with this quasi-objection by providing a solution using D (https://dlang.org). In rw_meals.d is code that is very similar to the Python code, and produces the same result, the correct result:

 |> rdmd rw_meals.d
    Roger breakfast lunch
    John lunch dinner
    Peter dinner
    Total: 3, breakfast: 1, lunch: 2, dinner: 2

D doesn’t have a built in set type, nor does it have an explicit set type in the standard library. The obvious (***) choices for implementing a set in D are to use a Red-Black Tree (there is an implementation in the standard library) or use an associative array (aka hash map, dictionary). In this case, I have used an associative array with the value of each key being the same as the key, which is about as close to a hash set as makes little difference.

I wonder what a good C++ code would look like? I am not sure I actually care as I have Python and D versions that satisfy me. Use the right tool for the right job as the saying goes.

Notes

(*) Let us assume “I” is actually a man, rather than this being bad phrasing by the CVu team.

(**) Though obviously others will say Ruby, or Lisp, or… well anything other than C++ really.

(***) To me, others may have a different view.

Source code follows

(Ed: reformatted slightly for publication.)

---- rw_meals.py ----
#!/usr/bin/env python3

import enum
import functools
import sys

class Meal(enum.Enum):
  breakfast = 'breakfast'
  lunch = 'lunch'
  dinner = 'dinner'

def get_attenders():
  result = {}
  for line in sys.stdin.readlines():
    data = line.strip().split()
    result[data[0]] =\
      {Meal(x) for x in data[1:]}
  return result

if __name__ == '__main__':
  attenders = get_attenders()
  counts = functools.reduce(
    lambda t, x: [t[0] +\
     (1 if Meal.breakfast in x else 0),
       t[1] + (1 if Meal.lunch in x else 0),
       t[2] + (1 if Meal.dinner in x else 0)],
        attenders.values(),
        [0, 0, 0]
  )
  print('Total: {}, breakfast: {}, lunch: {},\
   dinner: {}'.format(len(attenders),\
     *counts))

---- rw_meals.d ----
import std.algorithm: map, reduce;
import std.array: array, split;
import std.conv: to;
import std.stdio: lines, stdin, writefln,
  writeln;
import std.string: strip;

enum Meal: string {
  breakfast = "breakfast",
  lunch = "lunch",
  dinner = "dinner",
}
auto getAttenders() {
  Meal[Meal][string] people;
  foreach (string line; stdin.lines()) {
    auto data = line.strip().split();
    Meal[Meal] mealSet;
    foreach (item;
      data[1..$].map!(a => to!Meal(a))) {
      mealSet[item] = item;
    }
    people[data[0]] = mealSet;
  }
  return people;
}
void main() {
  auto attenders = getAttenders();
  auto counts = reduce!(
    (t, x) => [t[0] + ((Meal.breakfast in x) ?
                        1 : 0),
               t[1] + ((Meal.lunch in x) ?
                        1 : 0),
               t[2] + ((Meal.dinner in x) ?
                        1 : 0)])(
                  [0, 0, 0],
                  attenders.byValue().array);
  writefln("Total: %d, breakfast: %d,"
    " lunch: %d, dinner: %d",
    attenders.length, counts[0], counts[1],
    counts[2]);
}

Jim Segrave

The basic problem with this program is that the enums being used have the values breakfast: 0, lunch: 1 and dinner: 2. For every attendee, the test to see if they want breakfast tests:

  if((item.meals & 0) == 0)

which will always be true, so everyone is listed as wanting breakfast. This could be fixed by changing the enum definition to read:

  breakfast = 1, lunch = 2, dinner = 4,

That still leaves problems: if someone orders breakfast twice on one line, they’ll get lunch instead, two lunches results in only dinner, etc. No error report is generated.

If someone orders two dinners, they only get the default breakfast, as the sum of two dinner enums is 4 and only 0, 1 and 2 are recognised in this code.

If one of the input lines is duplicated, that attendee will be scheduled to have two of each meal they’ve selected.

Invalid meal names are ignored, but not reported, which is probably not a good idea.

If someone is attending but doesn’t choose any meal at all, with the current code she still gets put down for breakfast, which is wrong, if the enum is fixed, she’s not considered as attending and the number of attendees will only be the number of people having a meal, which should be separate counts.

Then there are style problems:

meal is a class, but it’s also the name of a variable, attendees is a class and again, the name of a variable, resulting in lines such as:

  meal meal, meals{};

and

  auto attendees{ get_attendees( std::cin) };

These are syntactically valid, but make reading the code difficult.

While it’s valid to replace the body of main with a try{} catch{} block, it is, to say the least, not idiomatic.

The code uses function-style casts, the widespread consensus among C++ developers is that these and C-style casts should be replaced with the C++ cast operator.

The fact that no less than 4 operator overloads are used to perform dubious operations on enums (assigning the sum of two enums to an enum may be correct, but more often is not. The fact that these overloads are needed for handling enums should be a hint that an enum probably isn’t the right type to use.)

Realistically, C++ isn’t the right language for a task like this, an ordinary scripting language would be more appropriate (shorter, quicker to write, easier to debug). There are still other lurking issues – the attendee names and meal names are case-sensitive. While it would be easy to ensure that the meal choices are handled caselessly, names are a different problem; they may contain UTF characters or they may not be convertible between lower and upper case (I believe that there is a variant of 'I’ in Turkish which has no lower case). The program also doesn’t address names well in that it isn’t designed to handle multi-word names (Gerrit Jan for example is often taken as a first name, not a first and middle name). The sample input uses first names only, for any sizeable list, the probability of a clash is not insignificant.

These problems require a lot more design and specification before trying to implement a real solution.

Nonetheless, I’ve re-written this in C++11 or later and addressed the earlier problems I’ve noted with duplicated entries on the same line, misspelled meal names, attendees choices being spread over more than one line. As a side benefit, it’s possible to get a list of all the attendees, whether they are on a strict diet or not and, for each meal type, a list of who has chosen that meal. The program can either receive the list of attendees and their meal choices on stdin or read it from a file given as the sole argument to the program.

The meal choices have been moved to an initializer list at the top of the C++ file, simply adding another meal name to that list is sufficient to enable it to be processed (note the commented out "high-tea" in the initializer list).

I’ve attached the header file meal.h, the C++ code cc106.cpp, and a somewhat larger sample input file cc106.input.

-- revised header file --
#pragma once
#include <fstream>
#include <initializer_list>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <map>
#include <string>
#include <vector>
class Meal_name {
 private:
    static int        new_id;
    static int        total_meals;
    int               count;
 public: 
    int         const id;
    std::string const meal_name;
    Meal_name(const char * name);
    // return number of these meals needed
    int  get_count() const { return count; }
    // return total number of meals
    // (all types)
    int  get_total_meals() const {
      return total_meals; }
    // somebody wants one of these meals
    void incr() { ++count; ++total_meals;}
};
using Selection    =
  std::pair<const std::string, int>;
using Attendee_map =
  std::map<const std::string, int>;
using Choice_vec   =
  std::vector<Meal_name>;

ssize_t lookup_meal(const std::string & name,
  const Choice_vec & vec);

Selection parse_line(
  const std::string & input_line, int line_no,
  Attendee_map & attendees,
  const Choice_vec & vec);

void process_line(
  const std::string & input_line, int line_no,
  Attendee_map & attendees,
  Choice_vec & vec);

-- revised C++ code --
#include "meal.h"
// initializer list with the names of all the
// different meals attendees can choose
std::initializer_list<Meal_name> all_choices 
{"breakfast", "lunch", "dinner",
 /* "high-tea", */ };
// ensure each Meal_name has an id which is a
// power of 2 (1, 2, 4, ...)
int Meal_name::new_id = 1;
Meal_name::Meal_name(const char * name)
: count(0),
  id(Meal_name::new_id), meal_name(name) {
  new_id *= 2;
}
int Meal_name::total_meals = 0;

// return index of meal 'name' in the vector
// or -1 if not found
ssize_t lookup_meal(const std::string & name,
  const Choice_vec & vec) {
  for(size_t i = 0; i <  vec.size(); ++i) {
    if(vec[i].meal_name.compare(name) == 0) {
      return static_cast<ssize_t> (i);
    }
  }
  return -1;
}
// parse an input line, returning the attendee
// name (if any) and the bitwise
// or of the meals selected (blank lines will
// return this as zero)
Selection parse_line(
  const std::string & input_line, int line_no,
  Attendee_map & attendees,
  const Choice_vec & vec) {

  std::string    name;
  std::istringstream is(input_line);
  // skip blank lines
  is >> name;
  if(name.size() == 0) {
    // skip blank lines
    return Selection{"", 0};
  }
  // ensure the name is registered if new
  attendees.emplace(name, 0);
  int choice = 0;
  std::string meal;
  // accumulate all errors for this input line
  std::ostringstream errs;
  while(is >> meal) {
    auto idx = lookup_meal(meal, vec);
    if(idx < 0) {
      errs << "\t\"" << meal <<
        "\" is not a valid name for a meal" <<
        std::endl;
      continue;
    }
    if((choice & vec[idx].id) != 0) {
      errs << "\t\"" << meal <<
        "\" appears more than once"
        " on this line" << std::endl;
      continue;
    }
    choice |= vec[idx].id;
  }
  // report if there were any problems on this
  // line
  if(errs.str().size() != 0) {
    std::cout << "Line " << line_no << ": "
      << input_line << std::endl;
    std::cout << errs.str();
  }
  return Selection(name, choice);
}
void process_line(
  const std::string & input_line, int line_no, 
  Attendee_map & attendees, Choice_vec & vec) {
  Selection sel(parse_line(
    input_line, line_no, attendees, vec));
  const std::string & name = sel.first;
  int choice = sel.second;
  if(choice == 0) {
    // blank line or no meals ordered on this
    // line
    return;
  }
  // previously ordered meals
  int old_choice = attendees[name];
  // newly ordered meals
  int new_choice = ~old_choice & choice;
  int idx = 0;
  while(new_choice != 0) {
    if(new_choice & 1) {
      // update no. of these meals ordered,
      // total meals
      vec[idx].incr();
    }
    new_choice >>= 1;
    ++idx;
  }
  attendees[name] = choice | old_choice;
}
int main(int argc, char **argv) {
  // set up the possible meals
  Choice_vec meal_choices(all_choices);
  // a map to track attendees
  Attendee_map attendees;
  // use cin unless there's a CLI parameter
  // (file of input lines)
  std::istream *f = &std::cin;
  std::ifstream ifs;
  ifs.exceptions(std::ifstream::badbit |
    std::ifstream::failbit);
  try {
    if(argc > 1) {
      ifs.open(argv[1]);
      f = &ifs;
    }
    std::string line;
    int     line_no = 0;
    while(std::getline(*f, line)) {
      process_line(line, ++line_no,
        attendees, meal_choices);
      if(ifs.eof()) {
        ifs.close();
        break;
      }
    }
  }
  catch (std::ios_base::failure &ex) {
    std::cerr << "File read error on " <<
     ((argc > 1) ? argv[1] : "standard input")
     << std::endl;
    exit(1);
  }
  std::cout << "\nAttendees: " <<
    attendees.size() << " Total meals: ";
  std::cout <<
    meal_choices[0].get_total_meals();
  for(auto meal : meal_choices) {
    std::cout << " " << meal.meal_name << ": "
      << meal.get_count();
  }
  std::cout << "\n\n" << std::setw(9) <<
    "Attendees" << ":";
  std::string separator = " ";
  for(auto participant: attendees) {
    std::cout << separator << 
      participant.first;
    separator = ",  ";
  }
  for(auto meal: meal_choices) {
    std::cout << "\n\n" << std::setw(9) <<
      meal.meal_name << ":";
    int  id = meal.id;
    separator = " ";
    for(auto participant: attendees) {
      if(participant.second & id) {
        std::cout << separator <<
          participant.first;
        separator = ",  ";
      }
    }
  }
  std::cout << std::endl;
                       
}
-- sample input --
  Roger breakfast lunch dinner
  John  lunch dinner
  Peter dinner
  Dave

  Paul  dinner lunch
  Mary  dinner
  Sadie high-tea dinner
  Peter dinner lunch
  Dave

  Kevin breakfast lunch lunch
  Huey  lunch
  Alvin 

Felix Petriconi <felix@petriconi.net>

The main problem of the code is in the definition of the enum at the very beginning:

  enum class meal : int
  {
    breakfast,
    lunch,
    dinner
  };

Later in the code the enum is used as a bit field, so the values were combined with plus and or operators. But the enum values were not defined as a bitfield. Per default the first enum is initialised with zero and the next ones follow continuously. So the present code is equal to

  enum class meal : int
  {
    breakfast = 0,
    lunch = 1,
    dinner = 2
  };

So a combination of breakfast | lunch is equal to 0 | 1 which is equal to 1. That means that the information of breakfast would be lost.

The bitfield should be corrected to

  enum class meal : int
  {
    breakfast = 1,
    lunch = 2,
    dinner = 4
  };

Further this should be improved:

The choice of enum class at the beginning is good. This C++11 feature ensures that potential accidental conversions to an integer type will not happen.

The loop inside the following stream operator std::istream &operator>>(std::istream &is, meal &m) should be changed to

  for (const auto& p : names) {
    if (p.name == name)
      m = p.value;
  }

because the existing code would create a copy of p for every loop iteration, which is a waste of resources. The same is valid for the loop inside the std::ostream &operator<<(std::ostream &os, meal const m) operator.

The operator

  constexpr meal operator+(meal a, meal b) {
    return meal(int(a) + int(b));
  }

tries to combine enumerated values but it may return values that are no valid meal. So a dinner + lunch results into a 2+4 (or 1+2 in the original code) None of the results is a valid meal value. So the operator should not return a type of meal, but an int.

The same is true for the meal operator+=(meal &a, meal b).

So all operators would become:

  constexpr int operator+(meal a, meal b) {
    return int(a) + int(b);
  }
  int operator+=(int &a, meal b) {
    a = a + int(b);
    return a;
  }
  constexpr int operator|(meal a, meal b) {
    return int(a) | int(b);
  }
  constexpr int operator&(int a, meal b) {
    return a & int(b);
  }

The following static_assert is a great way to ensure that the bitfield uses each enum value exclusively. Since I changed the results type of the operators, the static_assert would have to be changed to

  static_assert((int(meal::breakfast) |
    int(meal::lunch) | int(meal::dinner)) ==
                (int(meal::breakfast) +
    int(meal::lunch) + int(meal::dinner)),
    "not distinct");
The problem of possible invalid enum values implies that the struct

  struct attendee
  {
    std::string name;
    meal meals; // set of meals

  };

should be changed to

  struct attendee
  {
    std::string name;
    int meals; // set of meals
  };

The type definition using attendees = std::list<attendee>; should be changed to using attendees = std::vector<attendee>; because all non array like types have a very bad cache locality. Sometime ago I read the good advice, that every usage of a different container than array or vector should be explicitly justified.

I had to change the get_attendees function on my Mac to

  attendees get_attendees(std::istream &is) {
    attendees result;
    std::string line;
    while (std::getline(is, line)) {
      std::istringstream iss(line);
      if (line.empty())           // new line
        return result;            // new line

      std::string name;
      iss >> name;
      meal meal;
      int meals{};
      while (iss >> meal)
        meals += meal; // add in each meal
      if (is.fail())
        throw std::runtime_error("Input error");
      result.push_back({name, meals});
    }
    return result;
  }

Otherwise the while loop did not terminate.

Inside the while loop the variable meals is default initialised by using {} to zero which is in the old code breakfast, even if the attendee might not have breakfast. So I would extend the enum class with a none = 0 enumerated value so that a {} results in an initialised variable with no value.

The function count

  size_t count(attendees a, meal m) {
    size_t result{};
    for (auto &item : a) {
      // Check 'm' present in meals
      if ((item.meals & m) == m)
        ++result;
    }
    return result;
  }

is written with the correct intention in mind. But it fails when the first enumerated value has the implicit value of zero. The expression of (time.meals & 0) == 0 is always true. This results in the described failure of three breakfasts. Within this for loop I would change the type of the loop variable from auto& to const auto&, because the function has const semantics. As well there is no need to pass the attendees a parameter by value. In this case const & would be better, so the unnecessary copy of the complete container could be avoided. So the improved version would look like:

  size_t count(const attendees& a, meal m) {
    size_t result{};
    for (const auto& item : a) {
      // Check 'm' present in meals
      if (static_cast<meal>(item.meals & m)
          == m)
        ++result;
    }
    return result;
  }

In a next step I would change the routine by using an STL algorithm, because here a reduce is implemented by hand.

  size_t count(const attendees& a, meal m) {
    return std::accumulate(a.cbegin(), a.cend(),
      0,
      [m](std::size_t r, const auto& item) {
         return r + (((item.meals & m) != 0)
           ? 1 : 0);
    });
  }

The main function is a little bit unusual, because its body is the try–catch block. So I would slightly change it to:

  int main() {
    try {
      auto attendees{get_attendees(std::cin)};
      std::cout << "Total: " << attendees.size()
        << '\n';
      for (auto m : {meal::breakfast,
                   meal::lunch, meal::dinner}) {
        std::cout << ' ' << m << ": " <<
          count(attendees, m);
      }
      std::cout << '\n';
      return 0;
    }
    catch (const std::exception &ex) {
      std::cout << ex.what() << '\n';
    }
    return -1;
  }

So I recommend to add a newline at the end of the ‘Total’ line. From my point of view that would improve the readability of the output. Initialising the ranged based for loop per value is fine, because it is a loop over integral values and there is no performance penalty compared to a const& value.

At the end of the output I would return in case of an overall success a zero and in case of a failure a non-zero value. That is the common behaviour of programs.

James Holland

The student has recognised that the meal enumerations have to be distinct and has had the foresight to construct a static_assert in an attempt to enforce that condition. Unfortunately, there are two problems associated with the student’s code. Firstly, not only do the enumerations have to be unique, they have to contain one, and only one, bit position that has a value of ‘1’. This is so that each bit position within the enumeration is associated with a single meal type. The second problem is that the student’s static_assert does not fully test for these conditions.

Making the meal enumerations fit the above requirements is simple; just make each a successive integer power of 2. This gives the enumerations breakfast, lunch and dinner the values of 1, 2 and 4 respectively. Enforcing this at compile-time is a little more difficult, however.

The approach I have adopted is to count the number of ‘1’s in each enumeration and to ensure it is equal to one. I have written a constexpr function to do this. Then, to ensure each enumeration is unique, I ‘or’ all the enumerations and compare the result with the number of enumerations I am ‘or’ing, in this case, three. Thanks to constexpr, all this is done at compile-time.

  // Count the number of 1 bits.
  constexpr size_t number_of_one_bits(
    const meal & m)
  {
    using meal_type =
      typename std::underlying_type_t<meal>;
    size_t number_of_ones = 0;
    for (size_t bit_position = 0;
         bit_position <= 8 * sizeof (meal_type);
         ++bit_position)
    {
      if (static_cast<meal_type>(m) & 
        (1L << bit_position))
      {
        ++number_of_ones;
      }
    }
    return number_of_ones;
  }
  static_assert(
    number_of_one_bits(meal::breakfast) == 1 &&
    number_of_one_bits(meal::lunch) == 1 &&
    number_of_one_bits(meal::dinner) == 1 &&
    number_of_one_bits(meal::breakfast |
      meal::lunch | meal::dinner) == 3,
    "Meal enumerations are not distinct.");

Finally, I am not sure how the student intended to signal to the program that all attendees’ meal requirements have been entered. I have amended the software so that a blank line will bring things to a satisfactory close by employing line.empty() as shown below.

  while (std::getline(is, line), !line.empty())

Jason Spencer

The basic problem with the code is that the meal enum is being used as a bit mask but actually expresses a bit position. Enum entries (scoped and unscoped) are assigned values which increment by one from the previous entry, starting from 0 for the first entry, unless the value is explicitly specified. So in the code meal::breakfast has a value of 0 (0000b), meal::lunch a value of 1 (0001b), and meal::dinner a value of 2 (0010b). I believe the intent of the programmer is to use the enum as a bitmask where every enum value has a different single bit set, so in this case the least significant bit (LSB) should signify breakfast, the second LSB lunch and the third LSB dinner – the values of which should be 0001b, 0010b, 0100b. The simple solution would be to make the enum:

  enum class meal : int { breakfast = 1,
    lunch = 2, dinner = 4, };

or

  enum class meal : int { breakfast = 1 << 0,
    lunch = 1 << 1, dinner = 1 << 2, };

My preferred solution would be to keep the enum the way it is, consider it a bit position rather than a bitmask, and wherever the meal bits are set or tested use (1 << meal) instead of just meal.

But I’ll come back to the design later. There are other problems in the code, in order of the listings:

meal.h:

• <iosfwd> should be <iostream> – the stream operators are actually called on istreams and ostreams in the code, so we use more than just forward declarations. Yes, sstream will include iostream anyway, but it’s more robust to include iostream directly if sstream is ever removed...
• <sstream> should be removed – no stringstreams are used in this file.
• Don’t use a signed type for the enum underlying type – whether the enum is a bit position, or a bit mask. You lose one bit for the sign, and if you ever shift the bits you might run into trouble with sign extension. Consider perhaps using an unsigned integer type with a specific size e.g. uint16_t, uint32_t or uint64_t (from the <cstdint> header) – this way it’ll be easier to read your intent with respect to memory usage. And if the mask is ever stored in another struct the issue of padding and storage can be more easily addressed.
• Consider renaming the meal enum to meal_t – so then there’s no confusion between the meal type and the instance (see my (1 << meal) sentence above).
• struct names[] should be const as it’s a lookup table which isn’t expected to be changed. And if some code does change it, it may break the enum to string search loops.
• the operator>>(istream,meal) overload:
  • The range for loop doing a linear search should be const auto & p : names instead of auto p : names to prevent an unnecessary copy or an accidental overwrite of p.
  • Currently, if the meal isn’t found in names then the word is still consumed from the stream, without an error being set, or the meal result variable being updated. The failbit must be set on the istream when the meal isn’t found. This is done with is.setstate(std::ios_base::failbit); Note that setstate could also throw an exception at this point, depending on prior calls to istream::exceptions(..).
  • Prefer using istream::sentry to trim whitespace from the input stream and to skip processing if the input stream already has the failbit set.

    You might not be expecting whitespace, but you don’t know where the operator>> overload will be used in future, so don’t rely on it being stripped (although of course is >> name should strip it for you anyway, so this isn’t a hard rule).

• the operator<<(ostream,meal) overload: Nothing is printed if the meal isn’t found in names. Also, if multiple bits are set then all recognised meals would be printed, but without a delimiter. If the bit position is not found in names consider whether an exception should be thrown, or the failbit set on the ostream, or whether you just print the raw bitmask (as a binary string)? The const ref is again missing from the range for loop search.
• operator+(meal,meal), operator|(meal,meal) and operator&(meal,meal) would preferably have (const meal, const meal) arguments since we’re not planning on changing them.
• operator+=(meal & a, meal b) should return an lvalue, so the return type should be meal & and not meal: (meals+=lunch)+=dinner should be valid. The second arg, meal b could be const meal b as we don’t expect to change it.
• In the enum manipulation functions (that is the overloads of +, +=, |, &) – I’d strongly advise against hardcoding the int type into the operation – consider

        meal(static_cast<
          std::underlying_type<meal>::type>(a)+...)

  instead of meal(int(a)+...) – this way if you change the enum’s underlying type your arithmetic won’t break and there’s much less maintenance. C++14 has the slightly shorter std::underlying_type_t<meal> over C++11’s std::underlying_type<meal>::type.

• The static_assert test isn’t perfect – it wouldn’t catch the enum values set to { breakfast = 0, lunch = 0, dinner = 0, }. There’s also a question over what distinct means – unique values or no overlapping set bits? This seems to test for no-overlapping bits, so adding a fourth meal { breakfast, lunch, dinner, beer } (i.e. as a bit position enum, and not the shifted bit mask enum) would cause the assert to fail. There’s also no equivalent test that ::name in names[] are unique, although that might be overkill. Some might argue the test of uniqueness in the enum is overkill.

meals.cpp:

• #include <string> and #include <sstream> are missing. There’s no compilation error because they were already included in meals.h, but if that ever changes (sstream should be dropped from meals.h anyway), it’s best to include here.
• consider renaming attendee type to attendee_t to prevent confusion with an instance.
• attendee::name could be const as there’s no obvious use case for changing the name after the struct is created.
• in get_attendees(..):
  • Perhaps consider a rename to better express that meals are also read? Maybe read_attendees_meals? get usually implies an accessor, not a stream reader.
  • Regarding the initialisation of meal and meals in meal meal, meals{};: the meal variable is uninitialised, while meals is initialised to the default value, which should be 0. Perhaps consider initialising to 0 explicitly, since that’s what we want in an empty mask. If iss >> meal cannot find the meal in names it won’t update the meal variable – and then meals will either be corrupted by the uninitialised meal, or will have another meal added of the value of the previously read meal (which complicates things even more when you consider the next point).
  • The use of arithmetic add to add a meal in operator+= called by meals += meal; would mean that adding two lunches would become a single dinner (easy to do since we don’t test for duplicates, or report errors). That’s wrong.
• std::istream &operator>>(std::istream &is, meal &m) doesn’t set the istream’s fail bit if the meal isn’t recognised, so get_attendees(std::istream &is) won’t catch unknown meals. Worse still the meal variable in get_attendees is uninitialised and may now not be set in the read, while still being ‘inserted’ into meals.
  • There is no testing whether the read value for meal is already set in meals.
• In main():
  • The main function is a special case when it comes to return values in that when there is no return statement an implicit return 0; is added (3.6.1.5 of [1]). In the case of a function-try-block when the function is main the compiler should do this at the end of the try clause.

    However, when reaching the end of the catch clause in the function-try-block the behaviour is equivalent to a return with no argument (15.3.14 of [1]), and therefore in this case the exit code is undefined. An explicit return 1; statement should be added to the end of the catch clause.

  • Rename count(..) to count_meals(..) – a function called ‘count’ could count anything, and could be confused with std::count. By the way – count_meals could easily be implemented with std::count_if:

         size_t count_meals(const attendees_t a,
           const meal m) {
           return std::count_if( std::begin(a),
             std::end(a), [ m ] (
               const attendees_t::value_type & item ) {
                return (item.meals & m);
           });
         }

  • when outputting the meals in the for range loop an initialiser_list of enums is used – this is yet another location to update if the enum list is ever changed. Unless a specific order of meals output is required consider using the enum values in names[]:

            for (const auto & mn : names )
              std::cout << ' ' << mn.name <<  ": "
                << count_meals ( attendees, mn.value );

In terms of general design:

• If new meals are ever added to the meal enum in meal.h there are four places that need to be updated – the enum, names, the static_assert and the list in main. Consider grouping at least the first three in the header file for easier updating.
• Consider changing the output text to say Number of guests: instead of Total: as the latter could be interpreted as the total number of meals.
• Consider moving the enum-to-string and string-to-enum mapping to two new functions – it’ll make testing easier, the code will be self documenting, error handling can be made cleaner and the code may be reused elsewhere. These could be methods in attendee_t, although ideally the responsibility would be put in a new meal_t class alongside other helper functions and tests.
• in get_attendees(..) consider splitting the stream reading from the input parsing – in the future the reading and parsing can then change independently. Meals and attendees can also then be parsed from a string, without having to create a stringstream object.
• Although it’s syntactically sugary, I’d consider dropping the enum +, +=, |, & overloads – since we’re going to the trouble of naming the meals and having an enum for them, why confuse things by using cryptic symbols to manipulate them? meals += meal might be more intuitive than meals |= meal, but also possibly wrong. And is the meal enum type (meal, singular) a valid place to hold multiple meals (as the superposition of meals in a bitfield) ? The merged value is no longer one of the listed enum tokens, and is that conceptually still a meal?

  Do we even need both operator| and operator+? If it’s just used for the static_assert then do the addition there rather than making a user think it’s valid for general use – an API is as much about preventing users from doing things, as it is about facilitating things.

I see four points for further investigation:

Information encoding

Do we need a bitmask? Yes, it’s very memory efficient, but it has a limited and fixed number of available flags that are stored in it. If the meal names are hard-coded into an enum each bit field must have a given meaning at compile time. What if new meals are introduced, or the meals of multiple days need encoding in the future? a re-write and re-compile is needed (making sure to catch all four places that need the enum list needs to be updated).

My preferred design is to take a list of meals on the command line, and for each input line either put the meals as strings in an std::unordered_set, or an std::unordered_multiset (if in the future you want to allow multiple instances of a meal), without a bitmask. Or read the meal names as strings and directly increment a map like std::unordered_map<std::string, size_t> meal_tally;

Alternatively, encode the meals (the valid values of which are again specified on the command line) into a std::bitset (you’d need to specify a compile time limit on the number of meal options) or a std::vector<bool>. You have the meal names on the command line so can easily map bit positions to and from meal names. The ordering of meals on the command line can also specify the output ordering.

The drawback of dynamically specifying names is that if the bitmask is ever serialised as an integer the bit position meanings must be encoded separately.

Bitmask use

I would urge caution on using the enum type you’ve created to represent multiple meals as a bitmask. Their superposition has a different meaning to the original enums, and possibly has a conflicting absolute value. If you do want to use bitmasks, and you want the bit meaning to be specified at compile time as an enum, then use the enum as a bit position. Make it a scoped enum with an underlying type that is an unsigned integer. Have a typedef specifying an unsigned integer type which is called mealset_t (for the actual bitmask), or use an std::bitset, since the latter will deal with the bit positions and offsets for you. But don’t use the meal enum type as a bitmask type, because you’d be killing the meaning.

To get an idea of how an enum bitmask could be implemented have a look at 17.5.2.1.3 in [1].

enum management

C++ has very limited introspection, so you can’t at runtime convert an enum entry into a string with the human-readable name, and you can’t iterate over the enum values, nor even get the number of entries. Enums are just a bunch of scoped, or unscoped, constants. You could, however do things like:

  enum class meal_t : uint32_t { breakfast,
    lunch, dinner, leftovers, NUM_MEALS };
  const char * meal_names[] = { "breakfast",
    "lunch", "dinner", "leftovers" };
  static_assert(
    std::size(meal_names)==NUM_MEALS);

which is similar to what the student did with struct names[], but this suffers from poor maintenance, so you could get a little hacky with Boost.Preprocessor [2] and use the compiler pre-processor to automate the code generation:

  #include <boost/preprocessor/seq/for_each.hpp>
  #define STRINGIFYADDCOMMA_(s) #s,
  #define STRINGIFY_ADD_COMMA(r, data, elem)\
    STRINGIFYADDCOMMA_(elem)
  #define COMMAIFY(r, data, elem) elem, 
  #define PREFIX_COMMA(r, data, elem)\
    data::elem, using utype = uint32_t;
  
  #define MEALS_SEQ\
    (breakfast)(lunch)(dinner)(beer)(icecream)
  enum class meal_t : utype {
    BOOST_PP_SEQ_FOR_EACH( COMMAIFY, DUMMY, 
  MEALS_SEQ)
  };
  constexpr meal_t allmeals [] = {
    BOOST_PP_SEQ_FOR_EACH( PREFIX_COMMA, 
    meal_t, MEALS_SEQ)
  };
  const char * meal_names[]= {
    BOOST_PP_SEQ_FOR_EACH( STRINGIFY_ADD_COMMA, 
      DUMMY, MEALS_SEQ)
  };

It’s somewhat of a mess, I know, and the code is a little difficult to read, but to iterate over all meal enums you just iterate over allmeals, to map names, use meal_names[], to get number of meal types use std::size(allmeals). And if you need to add new meals, you just add them to MEALS_SEQ and the rest is automatically generated. In GCC you an use the -E switch to see the output of the pre-processor.

Or you could just use a library like Better Enums [3].

iostream overloading

If you’ve overloaded a stream operator then there are a number of expectations. The expectations are in regard to exception handling and error reporting. As mentioned already the istream’s failbit must be set if formatted input is expected and it is a different format. Further, the streams and data must be left in a consistent state. Most formatted stream overloads leave, on bad input, the stream with the failbit set, no update of the variable, but possibly some characters taken from the input stream. This is a basic exception guarantee, and a strong guarantee would be hard or impossible to do with a stream (it may not be possible to roll back the underlying buffer or look-ahead far enough). All the details are covered in [4] and it is probably the go-to book for IOStreams – although the book is a little dated, the principles are all there.

It’s a good exercise in stream use, but instead of the overloads I’d recommend writing string to enum conversion functions and leave the I/O to the enum user.

In terms of further reading, apart from what is already mentioned above, [5] may be a useful reference to the state of streams (section 15.4) and exception use (section 15.4.4), as well as sentry objects (section 15.5.4) and std::bitset (section 12.5). In fact section 12.5.1 has an example use of an enum to specify bit position in a bitset used as a bitmask.

Of course, you could also implement the whole thing about two orders of magnitude faster in awk:

echo -e "Roger breakfast lunch\nJohn lunch dinner\nPeter dinner" | awk 
'{ for(i=2;i<=NF;++i) ++cnt[$i] } END { printf "Guests: " NR; for (i in 
cnt) printf " " i ": " cnt[i]; printf"\n"; }'

References

[1] Working Draft, Standard for Programming Language C++, n4296, 2014-11-19

[2] http://www.boost.org/doc/libs/release/libs/preprocessor/

[3] http://aantron.github.io/better-enums/

[4] Standard C++ IOStreams and Locales: Advanced Programmer’s Guide and Reference by Angelika Langer and Klaus Kreft, Addison Wesley, 1st edition (31 Jan. 2000), ISBN 0321585585

[5] The C++ Standard Library: A Tutorial and Reference 2nd Edition by Nicolai M. Josuttis, Addison-Wesley, 25 May 2012 ISBN 0132977737

Commentary

The basic problem in the critique – that of using an enumeration to contain a set of values – is one that crops up in various guises. I would suggest that defining arithmetic operations on an enumeration is a category error.

While, as noted in some of the critiques, use of an enum is very efficient in terms of data storage it does have some other issues with usability. I suspect data storage is unlikely to be a serious problem for this program so I would probably recommend using an alternative design.

It might be worth exploring std::bitset as this already provides the logical operators, but the simplest design might just be to use a std::set of enumeration values (or even of strings) unless and until performance or memory use is a constraint.

Unfortunately, C++ does not provide any assistance with ensuring that enumerated values used as a bitmask are ‘sane’ (each defines a single bit with no overlaps). C# has an attribute (Flags) which at first sight looks useful, but it does not affect nor check the values in the enum.

Another problem with bitmasks is that of the detection of the ‘no bits set’ case. I recall when Microsoft Windows added a new value to the bitmask of file attributes, FILE_ATTRIBUTE_NORMAL, which is a simulated attribute that is set when no other attributes are set. The intent was that the ‘no flags set’ case could be detected by checking for this ‘special’ bit, but its existence caused a number of other problems and the need in some cases to special-case this value.

The Winner of CC 107

All the critiques that engaged with the code identified the fundamental problem with a bitmask value for breakfast of 0. Jason’s approach of keeping the implicit assignment of enum values and using bit shifting operations could a good way to proceed as it works with the flow of the language idioms; I’d probably want to see the bit shifting encapsulated to avoid confusion for the user.

While combining enumeration values with logical ‘or’ can produce values that are not in the list of named values this is not a problem, syntactically anyway, in C++ as the standard is careful to define the valid range of an enumeration to include these unnamed values. The danger of converting to the underlying type is that type safety is lost.

Jason’s point about the number of places to change if a new meal type were added is a good teaching point to make to the author of the code. These sort of hidden dependencies in code bases make changes significantly harder, and learning to avoid creating them in the first place is good practice.

I have a great deal of sympathy with Russel’s approach to the problem (echoed by Jim as well) that this problem does not seem to be a natural fit for the language used.

As Titus Winters pointed out in his keynote that this year’s CppCon, one of the oddities of programming is that the lifetime of a program can vary by many orders of magnitude. Efficiency (whatever that means) must factor in the cost of writing and modifying the program; since the author here states they are writing a program for a one-off event the time spent developing the program is likely to significantly exceed the total time spent executing it. Ease of development then becomes very significant. So I’m not persuaded that using Boost.Preprocessor is a good solution to this particular problem as I suspect that might increase development time!

I was unable to explain Felix’s problem with requiring a check on line.empty() – perhaps someone more experienced with the internals of the Mac C++ runtime can explain this? (The extra check does no harm however, and may even make the intent clearer.)

Several people mentioned the need to take care when overloading streaming operators to ensure the flags are set correctly, especially on input. In many cases this happens incidentally, as a call inside the implementation of the operator fails and sets the flags; this critique demonstrates one of the cases where a fully fledged solution needs to ensure the failbit is set manually on error.

Overall I am awarding Jason the prize for this critique as I thought he both covered the presenting problems well but also gave some other good suggestions for the author to improve their skill at programming.

Code Critique 108

(Submissions to scc@accu.org by Dec 1st)

I’ve got a problem with an extra colon being produced in the output from a program. I’ve stripped down the files involved in the program a fair bit to this smaller example. Here is what the program produces:

    test_program Example "With space"
    1:: 1001:Example
    2:: "1002:With space"

I can’t see where the two colons after each initial number come from as I only ask for one.

Please can you help the programmer find the cause of their problem and suggest some other possible things to consider about their program.

• Listing 3 contains record.h
• Listing 4 contains record.cpp
• Listing 5 contains escaped.h
• Listing 6 contains test_program.cpp

namespace util
{
  class Record {
  public:
    Record(uint64_t id,
      std::string value = {});
    std::string to_string() const;
    // other methods elided
  private:
    uint64_t const id;
    std::string value;
  };
  inline
  std::string to_string(Record const &r)
  {
    return r.to_string();
  }
}
			

#include <cstdint>
#include <sstream>
#include <string>

#include "record.h"

util::Record::Record(uint64_t id, std::string value)
  : id(id), value(value) {}

std::string util::Record::to_string() const
{
  std::ostringstream oss;
  oss << id << ":" << value;
  return oss.str();
}

			

#pragma once
#include <string>

namespace util
{
  // provide 'escaped' textual representation
  // of value
  // - any double quotes need escaping with \    
  // - wrap in double quotes if has any spaces
  template <typename T>
  std::string escaped_text(T t)
  {
    using namespace std;
    
    auto ret = to_string(t);
    for (std::size_t idx = 0;
      (idx = ret.find(idx, '"')) !=
        std::string::npos;
      idx += 2)
    {
      ret.insert(idx, "\\", 1);
    }
    if (ret.find(' ') != std::string::npos)
    {
      ret = '"' + ret + '"';
    }
    return ret;
  }
}
			

#include <cstdint>
#include <iostream>
#include "record.h"
#include "escaped.h"

using namespace util;

template <typename K, typename V>
void output(K key, V value)
{
  std::cout << escaped_text(key) << ": "
    << escaped_text(value) << '\n';
}
 
int main(int argc, char **argv)
{
  static uint64_t first_id{1000};
  for (int idx = 1; idx != argc; ++idx)
  {
    Record r{++first_id, argv[idx]};
    output(idx, r);
  }
}
			

You can also get the current problem from the accu-general mail list (next entry is posted around the last issue’s deadline) or from the ACCU website (http://accu.org/index.php/journal). This particularly helps overseas members who typically get the magazine much later than members in the UK and Europe.

Notes: 

More fields may be available via dynamicdata ..