6
\$\begingroup\$

One of the more recent functions I've needed for personal and work purposes is to split a string on a delimiter, but while ignoring the delimiter when inside a quote. Just as well, if within a quote then two adjacent double-quotes ("") should be treated as a double-quote escape, and as such should be output directly into the resultant string.

Input:

"\"Doe, \"\"John\"\" Johnathan\", \"Doe, James\"".QuotedSplit(",")

Output:

"Doe, \"\"John\"\" Johnathan", "Doe, James"

This actually posed a larger challenge than I originally anticipated, but in the end it was resolved pretty swiftly.

Obviously I want comments on all facets, but especially the idea of the performance of the method, and anything related to the yield return nature of it. I want it to be as lazy as possible, after all that's what good framework developers do, but I also want it to be robust.

The code is actually surprisingly long, but I think that's my fault for not abstracting it to a class, and I really do not want to abstract this to a class.

The method is as follows:

public static IEnumerable<string> QuotedSplit(this string s, string delim)
{
    var esb = new ExtendedStringBuilder(s.Length);

    bool inQuote = false;
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == '\"')
        {
            if (i < s.Length - 1 && s[i + 1] == '\"')
            {
                esb += s[i++];
                esb += s[i];
            }
            else
            {
                inQuote = !inQuote;
                esb += s[i];
            }
        }
        else if (!inQuote)
        {
            if (s[i] == delim[0])
            {
                var split = true;
                for (int j = 0; j < delim.Length; j++)
                {
                    if (s.Length - 1 <= i + j)
                    {
                        split = false;
                        break;
                    }

                    if (s[i + j] != delim[j])
                    {
                        split = false;
                        break;
                    }
                }

                if (split)
                {
                    yield return esb;
                    esb.Length = 0;
                    i += delim.Length - 1;
                    split = true;
                    continue;
                }
            }

            esb += s[i];
        }
        else if (inQuote)
        {
            esb += s[i];
        }
    }

    if (esb.EndsWith(delim))
    {
        esb.Length -= delim.Length;
    }

    yield return esb;
}

The unique advantage of this method is that it can take a string as the delimiter, and will lazily evaluate it, without creating a weird method structure (like string.Split does).

I haven't noticed any bugs with it, though I guess it's possible that there are some. I've used it in the production environment it's part of for a while with no issues.

\$\endgroup\$
  • \$\begingroup\$ @t3chb0t They don't do the same thing. The one you linked to uses specific chars, not a string, to split on. \$\endgroup\$ – Der Kommissar Jun 27 '17 at 18:41
  • \$\begingroup\$ Yes, except when you're splitting on a group of chars a simple case doesn't work like that. \$\endgroup\$ – Der Kommissar Jun 27 '17 at 18:44
  • \$\begingroup\$ What if the delim was encapsulated as a Regex? I don't mean passed in as such; the client shouldn't have to deal with Regex's. \$\endgroup\$ – radarbob Jun 27 '17 at 18:56
  • \$\begingroup\$ @radarbob It could be, but that would lend itself to potential performance issues -- feel free to suggest that as an answer, if you back it up with some BenchmarkDotNet comparison metrics I'll be happy to swap it. \$\endgroup\$ – Der Kommissar Jun 27 '17 at 18:57
  • 1
    \$\begingroup\$ I was thinking code length and the "exposed, raw, low level" nature of it. I don't think about performance per se when thinking about maintainability. \$\endgroup\$ – radarbob Jun 27 '17 at 19:03
5
\$\begingroup\$

You can simplify your logic a bit. Once in a quote you don't need to check for anything until you either at the end of the string or find another quote.

I also didn't use the ExtendedStringBuilder since I don't have that code and just used the StringBuilder class

From limited testing it returns the same as your function and from using Stopwatch class building a string of 10,000,000 random char it's a bit faster but nothing that couldn't be attributed to noise.

First I would create another method to just read ahead. It makes it easier to see if we equal the delimiter passed in

private static IEnumerable<char> ReadNext(string str, int currentPosition, int count)
{
    for (var i = 0; i < count; i++)
    {
        if (currentPosition + i >= str.Length)
        {
            yield break;
        }
        else
        {
            yield return str[currentPosition + i];
        }
    }
}

I switch the for loop into a while so I can mess with the counter. While you can change a counter in a for loop I generally frown on that as a developer I would not normally expect that. With a while loop I would

public static IEnumerable<string> QuotedSplit2(string s, string delim)
{
    const char quote = '\"';

    var sb = new StringBuilder(s.Length);
    var counter = 0;
    while (counter < s.Length)
    {
        // if starts with delmiter if so read ahead to see if matches
        if (delim[0] == s[counter] && 
            delim.SequenceEqual(ReadNext(s, counter, delim.Length)))
        {
            yield return sb.ToString();
            sb.Clear();
            counter = counter + delim.Length; // Move the counter past the delimiter 
        }
        // if we hit a quote read until we hit another quote or end of string
        else if (s[counter] == quote)
        {
            sb.Append(s[counter++]);
            while (counter < s.Length && s[counter] != quote)
            {
                sb.Append(s[counter++]);
            }
            // if not end of string then we hit a quote add the quote
            if (counter < s.Length)
            {
                sb.Append(s[counter++]);
            }
        }
        else
        {
            sb.Append(s[counter++]);
        }
    }

    if (sb.Length > 0)
    {
        yield return sb.ToString();
    }
}

SequenceEqual isn't known to be fast but unless you have a large string you using as a delimiter I wouldn't worry about it. If you do, then it might be worth changing the IEnumerable<char> into a string using String.Concat and comparing the string from String.Concat directly to the delim variable.

Test

static void Main(string[] args)
{
    var random = new Random();
    var str = String.Concat(Enumerable.Range(1, 10000000).Select(_ => (char) random.Next(32, 122)));
    var timer = new Stopwatch();
    timer.Start();
    var result2 = QuotedSplit2(str, "1\\").ToArray();
    timer.Stop();
    Console.WriteLine(timer.ElapsedMilliseconds);
    timer.Reset();

    timer.Start();
    var result = QuotedSplit(str, "1\\").ToArray();
    timer.Stop();
    Console.WriteLine(timer.ElapsedMilliseconds);
    timer.Reset();

    Console.WriteLine(result2.SequenceEqual(result));
    Console.WriteLine(result2.Length);

    Console.ReadLine();
}
\$\endgroup\$
  • \$\begingroup\$ The ExtendedStringBuilder is my own version of the StringBuilder that has a few extra features, but none of the additional features (except the operator + implementation) are really used here, so that's no big deal. :) \$\endgroup\$ – Der Kommissar Jun 28 '17 at 12:29
2
\$\begingroup\$
  • You have some code duplication inside this method which can be removed. Especially esb += s[i]; which is done in each of the if branches at least if there is no continue. Placing this line after the if..else if..else if will make it obvious that the last else if isn't needed.

  • This lines of code

    if (split)
    {
        yield return esb;
        esb.Length = 0;
        i += delim.Length - 1;
        split = true;
        continue;
    }  
    

    especially the split = true; is looking strange. split is true anyway and its scope isn't alive anymore after continue;.

  • Your method parameters aren't validated, but I hope that you just didn't post the validation. As you didn't do validation, I didn't either in the provided code ;-)

So let us clean this up

public static IEnumerable<string> QuotedSplit(this string s, string delim)
{
    var esb = new ExtendedStringBuilder(s.Length);

    bool inQuote = false;
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == '\"')
        {
            if (i < s.Length - 1 && s[i + 1] == '\"')
            {
                esb += s[i++];
            }
            else
            {
                inQuote = !inQuote;
            }
        }
        else if (!inQuote)
        {
            if (s[i] == delim[0])
            {
                var split = true;
                for (int j = 0; j < delim.Length; j++)
                {
                    if (s.Length - 1 <= i + j)
                    {
                        split = false;
                        break;
                    }

                    if (s[i + j] != delim[j])
                    {
                        split = false;
                        break;
                    }
                }

                if (split)
                {
                    yield return esb;
                    esb.Length = 0;
                    i += delim.Length - 1;
                    continue;
                }
            }
        }
        esb += s[i];
    }

    if (esb.EndsWith(delim))
    {
        esb.Length -= delim.Length;
    }

    yield return esb;
}  

Next we could extract the part where we check if we need to split, to a separate method like so

private static bool HasValueAtPosition(this string s, string value, int position)
{
    for (int j = 0; j < value.Length; j++)
    {
        if (s.Length - 1 <= position + j
            || s[position + j] != value[j])
        {
            return false;
        }
    }
    return true;
}  

which results in the former method like so

public static IEnumerable<string> QuotedSplit(this string s, string delim)
{
    var esb = new ExtendedStringBuilder(s.Length);

    bool inQuote = false;
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == '\"')
        {
            if (i < s.Length - 1 && s[i + 1] == '\"')
            {
                esb += s[i++];
            }
            else
            {
                inQuote = !inQuote;
            }
        }
        else if (!inQuote && s.HasValueAtPosition(delim, i))
        {
            yield return esb;
            esb.Length = 0;
            i += delim.Length - 1;
            continue;
        }
        esb += s[i];
    }

    if (esb.EndsWith(delim))
    {
        esb.Length -= delim.Length;
    }

    yield return esb;
}  
\$\endgroup\$
2
\$\begingroup\$

You can call this implementation insane but I find encapsulating nearly everything in it makes the algorithm very easy to follow even if you look a it in a few weeks and especially for someone who's never seen it before. But this does not only apply to this algorighm but every other one.

Very often we think that an algorithm is so trivial that it does not need any encapsulation or helper variables or anything alike but all the questions and clarification and comments say the exact opposite. It's very difficult to get the idea of it if all you see are some mysterious comparisons or strange calculations. Luckily there is almost always a name we can give such operations or conditions.

This is exactly what I did with it. I had a rather hard time to understand it at first but as I had a general idea of how it works I was able to guess what the particular line is for and as soon as I understood it, I give it a name. It's very likely that if I now showed this to anybody who does not know its exact purpose, he would probably be able to figure it out without debugging or running it first.

I did not only named the core-logic but I also changed the order of the conditions to simpilfy them especially the else if (!inQuote) and else if (inQuote) became if(quoted) {} else {} to remove the repetition and to shorten the ifs.

Additionaly to make it behave similar to the other split methods I added the StringSplitOptions that will allow you to ignore empty tokens that your original code can only do when the last token is a delimiter.

public static IEnumerable<string> SplitQuoted(
    this string input,
    string delimiter,
    StringSplitOptions options = StringSplitOptions.None)
{
    var token = new StringBuilder(input.Length);

    var quoted = false;

    for (var i = 0; i < input.Length; i++)
    {
        if (IsQuote(input[i]))
        {
            if (IsDoubleQuote(i))
            {
                // Collect both quotes.
                token.Append(input[i++]);
                token.Append(input[i]);
            }
            else
            {
                quoted = !quoted;
                token.Append(input[i]);
            }
            continue;
        }

        if (quoted)
        {
            token.Append(input[i]);
        }
        else
        {
            if (IsDelimiter(input, i, delimiter))
            {
                var isValidToken =
                    options == StringSplitOptions.None ||
                    (options == StringSplitOptions.RemoveEmptyEntries && token.Length > 0);
                if (isValidToken)
                {
                    yield return token.ToString();
                }
                token.Clear();
                JumpOverDelimiter(ref i);
                continue;
            }

            token.Append(input[i]);
        }
    }

    if (options == StringSplitOptions.RemoveEmptyEntries && token.Length == 0)
    {
        yield break;
    }

    yield return token.ToString();

    bool IsQuote(char c) => c == '\"';

    bool IsDoubleQuote(int i) => i < input.Length - 1 && IsQuote(input[i + 1]);

    void JumpOverDelimiter(ref int i) => i += delimiter.Length - 1;
}

There sub-loop has now its own method that looks for the delimiter. This one to got a few more names to give all these conditions meaning.

private static bool IsDelimiter(string input, int index, string delimiter)
{
    var isDelimiterStart = input[index] == delimiter.First();
    if (!isDelimiterStart) { return false; }

    var canContainDelimiter = input.Length - 1 - index >= delimiter.Length - 1;
    if (!canContainDelimiter) { return false; }

    for (int j = 0; j < delimiter.Length; j++)
    {
        var isDelimiterChar = input[index + j] == delimiter[j];
        if (!isDelimiterChar) { return false; }
    }

    return true;
}

I won't claim the names are perfect (like the canContainDelimiter could be isInputLongEnough etc) (or that there is no more room for improvement) because as we all know it's really hard to come up with good names but as soon as you find them, the code is almost self-explaining. So keep up finding good names and you won't have to do it yourself everytime (explain the code). Let the code do it for you.

Example output for "\"Doe, \"\"John\"\" Johnathan\", \"Doe, James\",,,,foo,," and delimiter ,,

Original:

"Doe, ""John"" Johnathan", "Doe, James" 
[String.Empty]
foo

With option None:

"Doe, ""John"" Johnathan", "Doe, James" 
[String.Empty]
foo
[String.Empty]

With options RemoveEmptyEntries:

"Doe, ""John"" Johnathan", "Doe, James" 
foo

[String.Empty] - This is just a symbolic placeholder because the quote formatting does not display an empty line at the end.

\$\endgroup\$
  • \$\begingroup\$ Why is it returning "Doe, ""John"" Johnathan", "Doe, James" as a single line? In my example those are separate entries. \$\endgroup\$ – Der Kommissar Jun 28 '17 at 15:54
  • 1
    \$\begingroup\$ @EBrown becasue the delimiter here is a double comma ,, (I wanted to see if a longer delimiter will be correctly recognized) \$\endgroup\$ – t3chb0t Jun 28 '17 at 15:55
  • \$\begingroup\$ Ah, my bad, good stuff then. :) \$\endgroup\$ – Der Kommissar Jun 28 '17 at 15:56
0
\$\begingroup\$

I think there is a simpler approach

public static IEnumerable<string> Parse (string input, string delimeter)
{
    StringBuilder sb1 = new StringBuilder();
    StringBuilder sb2 = new StringBuilder();
    char? c = null;
    bool inQuote = false;
    bool safety = false;
    foreach(char next in input)
    {
        if (c != null)
        {

            if (c == '\"' && !safety)
            {
                inQuote = !inQuote;
                safety = false;
            }
            if (inQuote)
            {
                if (c == '\"' && next == '\"')
                {
                    safety = true;
                }
                sb1.Append(c);
            }
            else
            {
                sb2.Append(c);
                if (sb2.ToString() == delimeter)
                {
                    sb2.Clear();
                    if (sb1.Length > 0)
                    {
                        yield return sb1.ToString();
                        sb1.Clear();
                    }
                }
                else if (sb2.Length > delimeter.Length)
                {
                    sb1.Append(sb2.ToString());
                    sb2.Clear();
                }
            }
        }               
        c = next;
    }
    yield return sb1.ToString() + sb2.ToString() + c;
}
\$\endgroup\$
  • \$\begingroup\$ This is wrong. You don't handle "", which means a literal quote escape will be treated as the end of one quoted string and the start of another. \$\endgroup\$ – Der Kommissar Jun 28 '17 at 12:18
  • 1
    \$\begingroup\$ That was not clear in the requirements. And still not clear. A test case should have cleared this up. \$\endgroup\$ – paparazzo Jun 28 '17 at 12:21
  • \$\begingroup\$ In all fairness, I responded to your comment on the question with that requirement. \$\endgroup\$ – Der Kommissar Jun 28 '17 at 12:23
  • \$\begingroup\$ The only issue with your edit is that ""s is going to flip the inQuote on the s, because it doesn't see the "" - also, I'm not the one who DV'd (I did UV briefly before I noticed that issue though). \$\endgroup\$ – Der Kommissar Jun 28 '17 at 12:40
  • \$\begingroup\$ OK I will probably just delete it. \$\endgroup\$ – paparazzo Jun 28 '17 at 12:45

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.