Functional CSV Parser

Question

I've been starting to migrate some C++ code from imperative to more of a functional style. I'm new to functional programming so I'm trying to get a sense of how well this code fits into the functional programming paradigm.

The purpose of the code is to scan tokens from CSV files, and currently passes all the written tests I have.

Here's the header.

#pragma once

#include <cstddef>

/// Enumerates the several types of CSV tokens.
enum class csvTokenType {
  /// A null token.
  Null,
  /// A newline sequence.
  Newline,
  /// A separator character.
  Separator,
  /// A quoted cell.
  QuotedCell,
  /// An unquoted cell.
  UnquotedCell
};

/// Contains data belonging to a token.
class csvToken final {
  /// The type of this token.
  csvTokenType type;
  /// The character data belonging to the token.
  const char* data;
  /// The number of characters in the token.
  size_t size;
public:
  /// Constructs a null token.
  csvToken() noexcept : type(csvTokenType::Null), data(""), size(0) { }
  /// Constructs a CSV token.
  /// @param t The type to assign the token.
  /// @param d The data to assign the token.
  /// @param s The size of the data being assigned to the token.
  csvToken(csvTokenType t, const char* d, size_t s) noexcept : type(t), data(d), size(s) { }
  /// Indicates if this is a valid token or not.
  /// @returns True if it's a valid token, false otherwise.
  operator bool () const noexcept {
    return type != csvTokenType::Null;
  }
  /// Checks for token type equality.
  /// @param otherType The type of token to check for.
  /// @returns True if the types are equal, false otherwise.
  bool operator == (csvTokenType otherType) const noexcept {
    return type == otherType;
  }
  /// Checks for equality with string data.
  /// @param str The string to check.
  /// @returns True if the strings are equal, false otherwise.
  bool operator == (const char* str) const noexcept;
};

/// Scans for a token.
/// @param data The data to scan.
/// @param size The size of the data to scan.
/// @returns The resultant token.
csvToken csvScan(const char* data, size_t size) noexcept;

Here's the implementation.

#include "csvScan.hpp"

#include <algorithm>

#include <string.h>

namespace {

/// A simple class for quick and safe
/// string scanning.
struct csvStringView final {
  /// The string data.
  const char* data;
  /// The size of the string.
  size_t size;
  /// Constructs the string view.
  csvStringView(const char* d, size_t s) noexcept : data(d), size(s) { }
  /// Gets a character at a specified offset.
  /// @param i The offset of the character to get.
  /// @returns The character at the specified offset.
  /// If the offset is out of bounds, then zero is returned instead.
  char operator [] (size_t i) const noexcept {
    return (i < size) ? data[i] : 0;
  }
  /// Returns a beginning iterator.
  /// @returns The beginning iterator.
  const char* begin() const noexcept {
    return data;
  }
  /// Returns the ending iterator.
  /// @returns The ending iterator.
  const char* end() const noexcept {
    return data + size;
  }
};

/// Returns the first non-null token
/// generated by one of the functions in the parameter list.
/// @tparam FirstMatcher The type of the first callable token scanner.
/// @tparam OtherMatchers The type of the other callable token scanners.
/// @param strView The string view to scan.
/// @param firstMatcher The first token scanner.
/// @param otherMatchers The other token scanners.
/// @returns The first non-null token from the given matchers.
template <typename FirstMatcher, typename... OtherMatchers>
csvToken csvFirstMatch(const csvStringView& strView, FirstMatcher firstMatcher, OtherMatchers... otherMatchers) {

  auto token = firstMatcher(strView);

  return token ? token : csvFirstMatch(strView, otherMatchers...);
}

/// The last resort matching function.
/// @tparam LastMatcher The type of the last token matcher.
/// @param strView The string view being scanned.
/// @param lastMatcher The last token matcher.
/// @returns The resultant token.
template <typename LastMatcher>
csvToken csvFirstMatch(const csvStringView& strView, LastMatcher lastMatcher) {
  return lastMatcher(strView);
}

/// Indicates if a character is
/// a separator or not.
/// @param c The character to check.
/// @returns True if the character is
/// a separator, false if it is not.
bool csvIsSeparator(char c) noexcept {
  return (c == ',') || (c == ';') || (c == '\t');
}

/// Indicates if the specified character
/// can be part of a newline sequence.
/// @param c The character to check.
/// @returns True if the character can
/// be part of a newline sequence, false otherwise.
bool csvIsNewline(char c) noexcept {
  return (c == '\n') || (c == '\r');
}

/// Indicates if the specified
/// character can terminate an unquoted cell.
/// @param c The character to check.
/// @returns True if the character can terminate
/// the call, false otherwise.
bool csvIsCellTerminal(char c) noexcept {
  return csvIsSeparator(c) || csvIsNewline(c);
}

/// Attempts to scan a separator character.
/// @param strView The string view to scan.
/// @returns The resultant token.
csvToken csvScanSeparator(const csvStringView& strView) noexcept {

  bool match = csvIsSeparator(strView[0]);

  csvToken goodToken(csvTokenType::Separator, strView.data, 1);

  return match ? goodToken : csvToken();
}

/// Attempts to scan a line feed.
/// @param strView The string being scanned.
/// @returns The resultant token.
csvToken csvScanLF(const csvStringView& strView) noexcept {

  csvToken goodToken(csvTokenType::Newline, strView.data, 1);

  auto match = (strView[0] == '\n');

  return match ? goodToken : csvToken();
}

/// Attempts to scan a line feed.
/// @param strView The string being scanned.
/// @returns The resultant token.
csvToken csvScanCRLF(const csvStringView& strView) noexcept {

  csvToken goodToken(csvTokenType::Newline, strView.data, 2);

  auto match = (strView[0] == '\r') && (strView[1] == '\n');

  return match ? goodToken : csvToken();
}

/// Attempts to scan any known newline sequence.
/// @param strView The string being scanned.
/// @returns The resultant token.
csvToken csvScanNewline(const csvStringView& strView) noexcept {
  return csvFirstMatch(strView, csvScanCRLF, csvScanLF);
}

/// Scans the contents of an unquoted cell.
/// @param strView The string view to scan.
/// @returns The resultant token.
csvToken csvScanUnquotedCell(const csvStringView& strView) noexcept {

  const auto* it = std::find_if(strView.begin(), strView.end(), csvIsCellTerminal);

  auto match = (it != strView.end());

  csvToken goodToken(csvTokenType::UnquotedCell, strView.begin(), it - strView.begin());

  return match ? goodToken : csvToken();
}

/// Scans a string view.
/// @param strView The string view to scan.
/// @returns The resultant token.
csvToken csvScan(const csvStringView& strView) noexcept {
  return csvFirstMatch(strView, csvScanSeparator, csvScanNewline, csvScanUnquotedCell);
}

} // namespace

bool csvToken::operator == (const char* str) const noexcept {

  size_t strSize = strlen(str);

  return (size == strSize) && (memcmp(str, data, strSize) == 0);
}

csvToken csvScan(const char* data, size_t size) noexcept {

  csvStringView strView(data, size);

  return csvScan(strView);
}

Answer 1

Your code isn't functional, neither in the sense of working properly, nor in the sense of respecting the principles of functional programming.

To parse a file, you need a way to consume the file. How would you do it with your function?

csvStringView fh = readFile(filepath.csv);
csvToken tok = csvFirstMatch(fh); 
// ???

You could imagine to compute a new string_view from the token length:

// ...
auto fh2 = remove_prefix(fh, tok.length);
csvToken tok2 = csvFirstMatch(fh2);

But you'll need to do it an unspecified number of times. So either you do this in a loop, but a loop isn't functional, or you muscle-up your parsing function to return not only the token, but also the stream:

std::pair<Token, std::string_view> parse_token(std::string_view stream);

That's well and good, but once you consider it, you realize you need to take up a new challenge: how will you chain or compose in any way two calls to parse_token if the return type isn't the same as the argument type?

The answer is actually quite obvious since we're talking about functional programming: you need a function to do that. Let's say we want to combine several parsers in an either/or way. We have a parse_quoted_cell and parse_unquoted_cell for instance and want to have the result of the fitting one:

auto parse_result = parse_quoted_cell(stream);
if (parse_result.first.type == Token::failure)
    return parse_unquoted_cell(stream);
return parse_result;

That can be easily generalized:

using Parse_result = std::pair<Token, Stream>;
using Parser = std::function<Parse_result(Stream)>;

Parser either_or(Parser f, Parser s) {
    return [f,s](Stream s) {
        auto res = f(stream);
        if (res.first.type == Token::failure) return s(stream);
        return res;
    };
}

"Either / or" isn't the only composition type you need. There's also an "and then". For instance, to parse a cell, you need to either parse a quoted or an unquoted cell, but also either a separator or the end of file. How would you do that? With a function, of course, and it would look like this:

Parser and_then(Parser f, Parser s) {
    return [f,s](Stream s) {
        auto res = f(stream);
        if (res.first.type == Token::failure) return res;
        auto res2 = s(res.second);
        return Parse_result(combine(res.first, res2.first), res2.second);
    };
}

Now we can create our cell parser from our building blocks:

Parser parse_cell = and_then(either_or(parse_quoted_cell, parse_unquoted_cell),
                             either_or(parse_separator, parse_eof));

It is rather interesting to see that parse_quoted_cell can itself be built from other building blocks:

Parser parse_quoted_cell = and_then(and_then(parse_quote, parse_unquoted_cell),
                                    parse_quote);

There are many cases where the same parser must be applied an unknown number of times. For instance, to parse the whole file, parse_cell should be applied repeatedly, until the end of file:

Parser parse_file = repeat(parse_cell);

where repeat can be defined recursively:

Parser repeat(Parser p) {
     return [p](Stream s) {
        auto res = p(stream);
        if (res.first.type == Token::failure) return res;
        auto res2 = repeat(p)(res.second);
        return Parse_result(combine(res.first, res2.first), res2.second);
    };
}

I admit that I didn't review your code in detail, but I feel like you should think the whole thing through again and then submit a revised program for a more detailed review.

Answer 2

A small observation on the includes and namespaces:

We have #include <cstddef>, but then use size_t in the global namespace, which is not portable according to the standard. We should be using std::size_t instead.

In the other file, we include the C compatibility header <string.h> - prefer to include <cstring> in new code, so that the names are available unambiguously in the std namespace (e.g. std::memcmp).

Answer 3

My main observation is that there seem to be a lot of free standing functions:

csvToken csvFirstMatch(const csvStringView& strView, FirstMatcher firstMatcher, OtherMatchers... otherMatchers)
csvToken csvFirstMatch(const csvStringView& strView, LastMatcher lastMatcher)
bool csvIsNewline(char c) noexcept
bool csvIsCellTerminal(char c) noexcept
csvToken csvScanSeparator(const csvStringView& strView) noexcept
csvToken csvScanLF(const csvStringView& strView) noexcept
csvToken csvScanCRLF(const csvStringView& strView) noexcept
csvToken csvScanNewline(const csvStringView& strView) noexcept
csvToken csvScanUnquotedCell(const csvStringView& strView) noexcept
csvToken csvScan(const csvStringView& strView) noexcept

And three classes

enum class csvTokenType
class csvToken final
struct csvStringView final

But it does not spring out at my how to use this.
Personally I would like to see something like:

CSVFile   file("FileName");
for(auto loop = file.begin(); loop != file.end(); ++loop) {
    // loop is now an iterator to a token.
}

// If you can do that with C++11
// Then the simpler syntax for C++14 make it easier:

CSVString  data(stringLoadedFromASourceThatIsNotAFile);
for(auto const& token: data) {
    // token is now a reference to the next token in the loop.
}