Parsing RFC 4180 CSV with GOTOs

Question

One of my data-import tools needs to support CSV files. I thought that parsing CSV is such a simple task that I didn't want to use any any external libraries for that. So here is one more RFC 4180 CSV parser. This one however works with two gotos.

---

I don't preach never use goto because I find there are situations in which it's useful. In this implementation it allows me to reduce code repetition by having only a single yield return and resetting all variables before parsing each line. Without the goto it would require one yiled return inside the loop and another one at the end for the last line. Resetting flags would also need to be done twice - initilization before the loop and then after each line.

The parser does not use any continues and if elses. I find they are confusing so I'd rather nest one more if/else than break the flow multiple times with a continue or seemingly equal conditions.

Everything it needs to be able to do is to parse a CSV into lines and columns. Reading files, verifying equal column count in each line or using headers for DataTables are jobs that other modules will take care of.

The interface might look unnecessary but I need it for dependency injection and mocking/testing.

public interface ICsvParser
{
    IEnumerable<List<string>> Parse(string csv, char separator = ';');
}

public class CsvParser : ICsvParser
{
    public IEnumerable<List<string>> Parse(string csv, char separator = ';')
    {
        if (csv == null) { throw new ArgumentNullException(nameof(csv)); }
        if (string.IsNullOrEmpty(csv)) { yield break; }

        var doubleQuote = '"';
        var carriageReturn = '\r';
        var lineFeed = '\n';
        var eof = false;

        var i = 0;

    resume:

        var isQuote = false;
        var isEscapeSequence = false;
        var isLineBreak = false;

        var buffer = new StringBuilder();
        var line = new List<string>();

        for (; i < csv.Length; i++)
        {
            var current = csv[i];

            if (isLineBreak)
            {
                if (current == lineFeed)
                {
                    i++; // Skip the line-feed.
                    goto yield;
                }

                throw new ArgumentException($"Invalid character at {i}. Expected '\\n' but found '{current}'.");
            }
            else
            {
                if (isEscapeSequence)
                {
                    if (current == doubleQuote)
                    {
                        buffer.Append(current);
                    }
                    else
                    {
                        isQuote = !isQuote;
                        if (current == separator)
                        {
                            line.Add(buffer.ToString());
                            buffer.Clear();
                        }
                        else
                        {
                            buffer.Append(current);
                        }
                    }

                    isEscapeSequence = false;
                }
                else
                {
                    if (current == doubleQuote)
                    {
                        isEscapeSequence = true;
                    }
                    else
                    {
                        if (current == separator && !isQuote)
                        {
                            line.Add(buffer.ToString());
                            buffer.Clear();
                        }
                        else
                        {
                            if (current == carriageReturn)
                            {
                                isLineBreak = true;
                            }
                            else
                            {
                                buffer.Append(current);
                            }
                        }
                    }
                }
            }
        }

        eof = true;

    yield:

        // Current buffer is not added yet.
        line.Add(buffer.ToString());

        yield return line;

        if (!eof)
        {
            goto resume;
        }
    }
}

---

Example

// test data
var csv = new[]
{
    "foo;bar",
    "baz;qux",
    "\"foo;foo\";qux",
    "foo\"\";\"\"bar",
    "\"foo;\"\"foo\";qux",
    ";",
}
.Join("\r\n"); // my helper extension

var csvParser = new CsvParser();
csvParser.Parse(csv).Dump();
csvParser.Parse("").Dump();

Output:

foo 
bar 

baz 
qux 

foo;foo 
qux 

foo" 
"bar 

foo;"foo 
qux 

<empty>
<empty>

<empty> is just a placeholder I used here to indicate empty strings.

Answer 1

1) I would save constants (doubleQuote, etc.) as fields, so they don't take up extra space in already fairly large method body.

2) I think your use of goto is fine. However you can also rewrite it without goto. At first glance it boils down to:

var buffer = new StringBuilder();
var line = new List<string>();
foreach(var ch in csv)
{
    var newLine = IsNewLine(ch);

    if (!newLine && TryAppend(ch, buffer, ...)) continue;

    line.Add(buffer.ToString())
    buffer.Clear();

    if (newLine)
    {
        yield return line;
        line = new List<string>();
    }
}

if (line.Any()) yield return line;

which also looks fine and is a bit easier to read if you ask me.

3) Alternatively you can go further with gotos and use them as full-fledged state machine. It will allow you to easily remove common sections such as

line.Add(buffer.ToString());
buffer.Clear();

and deep if-else nests will probably go away as well.

Answer 2

The biggest problem with gotos is that they make it really hard to refactor code easily.

Your loop body alone is 66 lines of code long and has a nesting depth of 5. Length of code and nesting depth are two of the prime indicators of complexity and are pretty good indicators for bugs.

To reduce both of those metrics you usually break up your one large method into smaller methods that do one specific thing. And that's exactly where gotos cause trouble: It's impossible to easily refactor your code because it's very tightly interwoven, in this case it's even worse because we jump outside the loop body so we actually have to look at the whole method which is over 100 (!) characters long.

Compare this to Nikita's pseudo code. It has - 12 lines of code and - nesting depth of 2

This does not mean that the complete code including all the separate methods would be shorter (it certainly would have less nesting depth though), but you can now understand each method on its own without having to worry about more low-level details of the others.

PS: And on a performance point of view, gotos have the additional disadvantage that they complicate the control flow graph which means that some compilers might generate worse code - particularly since it's a rarely used feature so not much time goes into improving code that uses it.

Answer 3

My rule of thumb is if you can avoid goto then you should avoid it.

If you want to avoid if..elseif but you don't want to have deeply nested if..else you could take a switch instead.

I would switch the condition of if (current == separator && !isQuote) to first check isQuote == false as well.

Using a switch and implementing @NikitaB's answer part about the const chars will look like

public class CsvParser : ICsvParser
{
    private const char doubleQuote = '"';
    private const char carriageReturn = '\r';
    private const char lineFeed = '\n';
    public IEnumerable<List<string>> Parse(string csv, char separator = ';')
    {
        if (csv == null) { throw new ArgumentNullException(nameof(csv)); }
        if (string.IsNullOrEmpty(csv)) { yield break; }

        var isQuote = false;
        var isEscapeSequence = false;
        var isLineBreak = false;

        var buffer = new StringBuilder();
        var line = new List<string>();

        for (var i = 0; i < csv.Length; i++)
        {
            var current = csv[i];
            switch (current)
            {

                case (lineFeed):
                    line.Add(buffer.ToString());
                    yield return line;

                    isQuote = false;
                    isEscapeSequence = false;
                    isLineBreak = false;
                    buffer.Clear();
                    line.Clear();
                    break;

                case (doubleQuote):
                    if (isEscapeSequence)
                    {
                        buffer.Append(current);
                    }
                    isEscapeSequence = !isEscapeSequence;
                    break;

                case (carriageReturn):
                    isLineBreak = true;
                    break;

                default:
                    if (isLineBreak)
                    {
                        throw new ArgumentException($"Invalid character at {i}. Expected '\\n' but found '{current}'.");
                    }
                    if (isEscapeSequence)
                    {
                        isQuote = !isQuote;
                        isEscapeSequence = false;
                    }
                    if (isQuote == false && current == separator)
                    {
                        line.Add(buffer.ToString());
                        buffer.Clear();
                    }
                    else
                    {
                        buffer.Append(current);
                    }

                    break;
            }
        }
        line.Add(buffer.ToString());

        yield return line;
    }
}

Answer 4

I have rewritten the CsvParser multiple times and this is its 5-th incarnation. It became a CsvReader that now works with a TextReader so that I don't have to load the entire csv-file in order to parse it. I removed the GOTOs and extracted the new ReadFieldAsync method that now contains the logic. There is also a new helper method MoveNext that now advances the current position. I tried to create an enumerator for the stream but it does not support an async API so I dropped this idea.

public interface ICsvReader : IDisposable
{
    Task<IList<string>> ReadLineAsync();
}

public class CsvReader : ICsvReader
{
    private const char doubleQuote = '"';
    private const char carriageReturn = '\r';
    private const char lineFeed = '\n';
    private const int charCount = 1;
    private const int noCharRead = 0;

    private readonly TextReader _csv;
    private readonly char _separator;
    private readonly char[] _current = new char[1];
    private int _position;
    private bool _isEndOfLine;
    private bool _isEndOfStream;

    public CsvReader(TextReader csv, char separator = ';')
    {
        _csv = csv;
        _separator = separator;
    }

    public CsvReader(string csv, Encoding encoding, char separator = ';')
    : this(new StreamReader(new MemoryStream(encoding.GetBytes(csv))), separator)
    {
    }

    public CsvReader(string csv, char separator = ';')
    : this(csv, Encoding.UTF8, separator)
    {
    }

    private char Current => _current[0];

    public Task<IList<string>> ReadLineAsync()
    {
        if (_isEndOfStream)
        {
            return Task.FromResult((IList<string>)null); ;
        }

        _isEndOfLine = false;

        var line =
            enumerable
                .Always(async () => await ReadFieldAsync())
                .TakeWhile(field => field.Result != null)
                .Select(t => t.Result)
                .ToList();

        return Task.FromResult((IList<string>)line);
    }

    private async Task<string> ReadFieldAsync()
    {
        if (_isEndOfStream || _isEndOfLine)
        {
            return null;
        }

        var isQuoted = false;
        var field = new StringBuilder();

        while (await MoveNextAsync())
        {
            if (Current == doubleQuote)
            {
                // Ignore the first double-quote.
                if (!await MoveNextAsync())
                {
                    return field.ToString();
                }

                // Double-quote not followed by another double-quote means the filed is quoted.
                if (Current != doubleQuote)
                {
                    isQuoted = !isQuoted;
                }
            }

            // Use only not-quoted separators for splitting.
            if (Current == _separator && !isQuoted)
            {
                return field.ToString();
            }

            if (Current == carriageReturn && !isQuoted)
            {
                // Ignore carragie-return.
                if (!await MoveNextAsync())
                {
                    throw new ArgumentException($"Missing line-feed at {_position}.");
                }

                if (Current == lineFeed)
                {
                    _isEndOfLine = true;
                    return field.ToString();
                }

                throw new ArgumentException($"Invalid character at {_position}. Expected '\\n' (line-feed) but found '{Current}'.");
            }

            field.Append(Current);
        }

        return field.ToString();
    }

    private async Task<bool> MoveNextAsync()
    {
        if (!_isEndOfStream)
        {
            _position++;
        }

        // Read one character at a time.
        return !(_isEndOfStream = await _csv.ReadAsync(_current, 0, charCount) == noCharRead);
    }

    public void Dispose()
    {
        _csv.Dispose();
    }
}

The helper extension Always that I use here is implemented as:

public static class enumerable
{
    public static IEnumerable<T> Always<T>(Func<T> get)
    {
        while (true)
        {
            yield return get();
        }
    }
}

And it can be used like this:

var csv = new[]
{
    "foo;bar",
    "baz;qux",
    "\"foo;foo\";qux",
    "foo\"\";\"\"bar",
    "\"foo;\"\"foo\";qux",
    ";",
}
.Join("\r\n");

using (var csvReader = new CsvReader(csv))
{
    enumerable
        .Always(async () => await csvReader.ReadLineAsync())
        .TakeWhile(line => line.Result != null)
        .Select(line => line.Result)
        .Dump();
}