root/trunk/csvRange/csvRange.d

/**
This module allows the parsing of CSV files and otherwise similar delimited
files using alternative delimiters on-the-fly, with O(1) memory usage if the
files are processed as they are read from disk.  It attempts to handle issues
like newlines and delimiters in quoted fields and escaped quotes correctly.

There are two recognized ways of escaping a quote in this library:  The
backslash method (\") and the double-quote ("") method.  According to Wikipedia
the double-quote method is teh standard.  On the other hand, in my observations
the backslash method occurs more often in practice.

References:

http://en.wikipedia.org/wiki/Comma-separated_values

Copyright (C) 2011 David Simcha

License:

Boost Software License - Version 1.0 - August 17th, 2003

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/
module csvrange;

import std.stdio, std.array, std.range, std.exception, std.algorithm, std.conv,
    std.traits, std.string;

// Gives a range that may have value semantics reference semantics.
private final class RefRange(R)
{
    R _range;

    this(R range)
    {
        this._range = range;
    }

    bool empty() @property
    {
        return _range.empty;
    }

    void popFront()
    {
        _range.popFront();
    }

    ElementType!R front() @property
    {
        return _range.front;
    }
}

/**
Tests whether a type is a ranges of characters.
*/
template isCharRange(R)
{
    enum bool isCharRange = isInputRange!R && is(ElementType!R : dchar);
}

/**
Tests whether a range is a range of ranges of character ranges.
*/
template isStringMatrixLike(R)
{
    enum bool isStringMatrixLike = isInputRange!R
        && isInputRange!(ElementType!R)
        && isCharRange!(ElementType!(ElementType!R));
}

/**
This class is an input range that iterates over the columns of a single line of
a CSV file.   It is meant to be instantiated only by the CsvFile object,
and may be recycled when popFront() is called on the CsvFile object.  Also,
when popFront() is called on this object, the buffer is recycled.  For
usage details see csvFile().
*/
final class CsvLine(R) if(isCharRange!R)
{
    private typeof(appender!(char[])())_front;
    private R _rest;
    private dchar _delim;
    private bool _nextEmpty;
    private bool _empty;

    private this(R range, dchar delim)
    {
        this._rest = range;
        this._delim = delim;
        _front = appender!(char[])();
        prime();
    }

    private void reset()
    {
        _nextEmpty = false;
        _empty = false;
        prime();
    }

    @property char[] front()
    {
        return _front.data;
    }

    @property bool empty()
    {
        return _empty;
    }

    void popFront()
    {
        if(_nextEmpty)
        {
            _empty = true;
        }
        else
        {
            prime();
        }
    }

    void prime()
    {
        bool inQuotes = false;
        bool backslashEscape = false;
        bool firstChar = true;
        _front.shrinkTo(0);

        while(true)
        {
            scope(exit) firstChar = false;

            if(_rest.empty)
            {
                _nextEmpty = true;
                return;
            }

            dchar cur = _rest.front;
            if(cur == '"' && !backslashEscape)
            {
                // To allow quotes in quoted fields, the CSV spec allows them
                // to be escaped with a second quote.
                if(inQuotes)
                {
                    // Handle double quoting.
                    _rest.popFront();
                    if(_rest.empty)
                    {
                        _nextEmpty = true;
                        return;
                    }

                    if(_rest.front == '"')
                    {
                        _front.put('"');
                        _rest.popFront();
                        continue;
                    }

                    inQuotes = false;

                    if(_rest.front == _delim)
                    {
                        _rest.popFront();
                        return;
                    }
                    else if(_rest.front == '\r' || _rest.front == '\n')
                    {
                        continue;
                    }
                    else
                    {
                        enforce(0, "Invalid single quote within quoted field.");
                    }
                }
                else
                {
                    _rest.popFront();
                    if(_rest.empty || _rest.front == '\r' || _rest.front == '\n')
                    {
                        // Assume the quote was meant literally.
                        _front.put('"');
                        if(_rest.empty)
                        {
                            _nextEmpty = true;
                            return;
                        }
                        else
                        {
                            continue;
                        }
                    }
                    else if(_rest.front == '"')
                    {
                        // Assume the first quote was an escape even though
                        // we're not inside quotes.
                        _front.put('"');
                        _rest.popFront();
                        continue;
                    }
                    else if(firstChar)
                    {
                        inQuotes = true;
                        continue;
                    }
                    else
                    {
                        // Again, assume it's a literal b/c it's not at
                        // the beginning of a field.
                        _front.put('"');
                        _rest.popFront();
                        continue;
                    }
                }
            }

            if(backslashEscape)
            {
                if(cur == '"' || cur == '\\')
                {
                    // Then nust turn backslashEscape off and let the normal
                    // processing handle it.
                    backslashEscape = false;
                }
                else if(cur == 'n')
                {
                    // Then the file was output with newlines written as '\n'.
                    // Substitute a newline.
                    backslashEscape = false;
                    cur = '\n';
                    // Let normal flow take over.
                }
                else
                {
                    // Assume it's intended to be taken literally.
                    _front.put('\\');
                    // Let normal flow take over.
                }
            }

            if(cur == '\\')
            {
                backslashEscape = true;
                _rest.popFront();
                continue;
            }

            if(cur == '\n' && !inQuotes)
            {
                _rest.popFront();
                _nextEmpty = true;
                return;
            }

            if(cur == '\r' && !inQuotes)
            {
                // Get rid of the \n, too, if there is one, then return.
                _rest.popFront();
                if(!_rest.empty && _rest.front == '\n')
                {
                    _rest.popFront();
                }

                _nextEmpty = true;
                return;
            }

            if(cur == _delim && !inQuotes)
            {
                _rest.popFront();
                return;
            }

            // Finally the typical case:  Just append the thing.
            _front.put(cur);
            _rest.popFront();
        }
    }
}

///
struct CsvFile(R)
{
    private RefRange!R _rest;
    private bool _empty;

    alias typeof(_rest) R2;
    alias CsvLine!(R2) Line;

    private dchar _delim;
    Line _front;

    this(R range, dchar delim)
    {
        this._rest = new RefRange!R(range);
        this._delim = delim;
        _front = new Line(_rest, _delim);
    }

    bool empty() @property
    {
        return _empty;
    }

    void popFront()
    {
        if(_rest.empty)
        {
            _empty = true;
            return;
        }

        // Have to iterate over _front to figure out where the thing ends.
        while(!_front.empty)
        {
            _front.popFront();
        }
        _front.reset;
    }

    Line front() @property
    {
        return _front;
    }
}

/**
Returns a struct that iterates over the rows of a CSV file (or more generally a
similar file with any delimiter character).  It is an input range of input
ranges.  Each call to front() produces a CsvLine object that can be used to
iterate over the columns of the current row.  Note that the CsvLine object is
recycled with every call to popFront().

Examples:
---
// charRange must be a range of characters representing a CSV file.
auto charRange = getCharRange();
auto csvIter = csvFile(charRange, ',');

// Iterate over the lines of the CSV file, excluding line breaks embedded in
// quotes.
string[] rowArrays;
foreach(row; csvIter)
{
    // Convert the row to an array of strings.
    rowArrays ~= array(
        map!"a.idup"(  // Necessary because CsvLine recycles buffers.
            row
        )
    );

    // row is now empty.  The next call to csvIter.popFront() will recycle
    // the object.
}
---
*/
CsvFile!(R) csvFile(R)(R range, dchar delim)
{
    return typeof(return)(range, delim);
}

///
final class CsvStructRange(S, R)
{
private:
    S _front;
    R _csvRange;
    size_t[] indices;
    Malformed _malformed;

public:
    this(R csvRange, string[] colHeaders, Malformed malformed)
    {
        enforce(colHeaders.length <= S.tupleof.length, text(
            "Can't have ", colHeaders.length, " fields in a ",
            S.tupleof.length, " field struct."));

        this._malformed = malformed;
        indices.length = colHeaders.length;
        size_t[string] colToIndex;
        foreach(i, h; colHeaders)
        {
            colToIndex[h] = size_t.max;
        }

        size_t colIndex;
        foreach(col; csvRange.front)
        {
            auto ptr = col in colToIndex;
            if(ptr)
            {
                *ptr = colIndex;
            }

            colIndex++;
        }

        indices.length = colHeaders.length;
        foreach(i, h; colHeaders)
        {
            immutable index = colToIndex[h];
            enforce(index < size_t.max, "Header not found:  " ~ h);
            indices[i] = index;
        }

        csvRange.popFront();
        this._csvRange = csvRange;
        prime();
    }

    void prime()
    {
        while(true)
        {
            try
            {
                primeImpl();
                return;
            }
            catch(Exception e)
            {
                if(_malformed == Malformed.throwException)
                {
                    throw e;
                }
                else
                {
                    _csvRange.popFront();
                    if(empty)
                    {
                        return;
                    }
                    else
                    {
                        continue;
                    }
                }
            }
        }
    }


    void primeImpl()
    {
        size_t colIndex;
        _front = S.init;

        foreach(colData; _csvRange.front)
        {
            scope(exit) colIndex++;

            foreach(ti, ToType; typeof(_front.tupleof))
            {

                if(ti >= indices.length)
                {
                    continue;
                }

                if(indices[ti] == colIndex)
                {
                    static if(isNumeric!(ToType))
                    {
                        colData = colData.strip();
                    }
                    else static if
                    (is(ToType == char[]) || is(ToType == const(char)[])
                     || is(ToType == const(char[])))
                    {
                        // colData gets overwritten and to!(char[])(char[])
                        // will not copy it.
                        colData = colData.dup;
                    }

                    _front.tupleof[ti] = to!ToType(colData);
                }
            }
        }
    }

    void popFront()
    {
        _csvRange.popFront();
        if(!empty)
        {
            prime();
        }
    }

    @property S front()
    {
        return _front;
    }

    @property bool empty()
    {
        return _csvRange.empty;
    }
}

/**
Determines whether CsvStructRange will ignore malformed lines or throw an
exception.
*/
enum Malformed
{
    ///
    ignore,

    ///
    throwException
}


/**
Given a struct type S, a range of characters representing a CSV file, and
an array of strings representing relevant column headers, read the CSV
file into an array of structs, one for each row.  The order of fields in
colHeaders must correspond to the order of the fields in the struct.
However, it is acceptable for colHeaders to include only a subset of the
columns in the CSV file and to only contain information for the first
colHeaders.length elements of the struct.

If a specified column header is not found, an exception is thrown.

All type conversions are done automatically, and if a type is to be converted
to a numeric type (an integer or floating point number), leading and trailing
whitespace are removed from the cell before this is attempted.  The Malformed
enum controls whether an exception is thrown when a type conversion fails,
or whether the line is simply ignored.  The default is to throw an exception.

Examples:
---
struct Person
{
    uint programmingSkill;
    float sleepHours;
    string favoriteLanguage;
    float reserved;
}

auto csvRange = csvFile(getCharRange(), '\t');
auto personRange = csvStructRange!Person(csvRange,
    ["Programming Skill", "Sleep Hours", "Favorite Language"]
);

foreach(person; personRange)
{
    if(person.sleepHours > 7 && person.programmingSkill > 8)
    {
        assert(person.favoriteLanguage == "D");
    }

    assert(reserved == float.init);  // No header for it, so it's not populated.
}
---
*/
CsvStructRange!(S, R) csvStructRange(S, R)
(R csvRange, string[] colHeaders, Malformed malformed = Malformed.throwException)
if(is(S == struct) && isStringMatrixLike!R)
{
    return new CsvStructRange!(S, R)(csvRange, colHeaders, malformed);
}

struct S
{
    uint a;
    string c;
    float b;
    uint dummy;

    string toString()
    {
        return text(a, '\t', b, '\t', c);
    }

    bool opEquals(const ref typeof(this) rhs) const
    {
        return a == rhs.a && b == rhs.b && c == rhs.c;
    }
}

unittest
{
    auto str1 =
"a\tb\tc
1\t2.5\t\"foo \t stuff \n \"\" bar \"\"\"
2\t5\tbar
3\t7.5\tbaz
";

// Same as str1 but put crazy quoting stuff in middle and use backslash escape
// for soem quotes.
    auto str2 =
"a\tc\tb
1\t\"foo \t stuff \n \\\" bar \"\"\"\t2.5
2\tbar\t5
3\tbaz\t7.5
";

    alias typeof(csvFile(str1, '\t')) Foo;
    auto res1 = array(
        csvStructRange!S(csvFile(str1, '\t'), ["a", "c", "b"])
    );

    assert(res1[0] == S(1, "foo \t stuff \n \" bar \"", 2.5));
    assert(res1[1] == S(2, "bar", 5));
    assert(res1[2] == S(3, "baz", 7.5));

    auto res2 = array(
        csvStructRange!S(csvFile(str2, '\t'), ["a", "c", "b"])
    );

    assert(res1 == res2);
}

void main(){}