11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mathieu Guindon Dec 26 '17 at 15:47
18
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I pick options 1 & 3 :-) and I totaly missed this redundancy... although I don't know yet how to rewrite it so that it's both nice looking and yet not overcomplicted. \$\endgroup\$ – t3chb0t Dec 26 '17 at 11:59
  • 4
    \$\begingroup\$ Or just use '"' directly instead of doubleQuote. Variables like var theLetterA = 'A';does not remove a "magic constant". \$\endgroup\$ – Eric Dec 27 '17 at 8:18
  • 1
    \$\begingroup\$ @Eric OTOH, it does allow you to insert inside jokes such as t_paamayim_nekudotayim as an alias for ::. \$\endgroup\$ – John Dvorak Dec 27 '17 at 10:57
  • 1
    \$\begingroup\$ Good point on doubleQuote. I think escapeChar would be a better name. \$\endgroup\$ – Nikita B Dec 27 '17 at 12:29
  • \$\begingroup\$ @JohnDvorak, pretty sure the correct spelling is Nekuda.. Nekudatayim. \$\endgroup\$ – Drag and Drop Dec 27 '17 at 12:54
12
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It's really hard to decide what is less wrong, a goto or introducing redundancy. Without going you'll have two returns. This isn't pretty either. \$\endgroup\$ – t3chb0t Dec 26 '17 at 16:17
  • 7
    \$\begingroup\$ @t3chb0t Having a single return statement duplicated is hardly a big deal. Redundancy is a problem if you duplicate complex logic because it means you have to change the code at multiple points - that's not really a problem with a single statement. Not being able to read the whole method on my 30" monitor on the other hand would cause me to reject the code during code reviews. It's really, really hard to understand a method if you have to scroll around to understand the control flow. \$\endgroup\$ – Voo Dec 26 '17 at 16:34
  • 2
    \$\begingroup\$ Part of this nesting depth is due to the bizarre avoidance of the else if construct \$\endgroup\$ – Eric Dec 27 '17 at 6:32
  • 4
    \$\begingroup\$ @t3chb0t A parser by definition will have a long list of branches somewhere, simply to describe all the different branches of its grammar. There is absolutely nothing wrong with it and it's actually what people expect. It makes the code consistent and easy to extend. Just for fun go ahead and introduce comments (say /* comment*/) to your code and see how much of it you have to rewrite. That's another consequence of it being very entangled - for larger parsers this way just doesn't scale. \$\endgroup\$ – Voo Dec 27 '17 at 8:43
  • 2
    \$\begingroup\$ @t3chb0t The whole idea behind the experiment is to let you find out yourself the advantages and disadvantages of that code. I'm sure we all agree that extensibility and maintainability are one of the most important things one can strive for. So doing exactly that (finding out how easy it is to adapt and extend the code) will give you very important insights into how well it really works: How hard is it to the find spots you have to adapt? Do you have to adapt more than one part of your code? Did your changes break other independent parts of the code? And so on. \$\endgroup\$ – Voo Dec 27 '17 at 9:18
5
\$\begingroup\$

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;
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, it's nice to see a switch in action ;-) though still thinking my code is prettier and easier to follow. With a flat structure it's not so easy to see in which mode you currently are in - that's why I avoid else if, I like it less then the goto :-] You also need to guard other conditions when execution path does not match previous ifs. With simple if/else there are no such situations so it's less error-prone. \$\endgroup\$ – t3chb0t Dec 27 '17 at 8:28
  • 3
    \$\begingroup\$ @t3chb0t, IMHO this implementation is easier to read. It is a state machine and it reads as a state machine: for linebreak - do this, for doublequote - do that, etc. Some of the "states" are not immediately apparent, but most are (for example doublequote+isEscapeSequence state is hard to represent as separate switch case). On the other hand, when I look at your implementation, it is way harder to tell "what happens when parser finds a doublequote", because this logic is separated into different if-else branches. It is not isolated from other states and it cannot be understood in isolation. \$\endgroup\$ – Nikita B Dec 27 '17 at 11:51
  • \$\begingroup\$ P.S. I agree, that goto-based solution can be shorter and single return is an advantage. I'm not sure it's worth it though. Voo summed up the disadvantages very well. \$\endgroup\$ – Nikita B Dec 27 '17 at 11:53
1
\$\begingroup\$

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();
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.