Писал csv парсер и столкнулся с проблемой, когда стандартных библиотечных функций как будто бы не хватает.
Дело в том, что CsvParser это автомат, который читает файл посимвольно и переходит из одного состояния в другое. И проблема с тем, что в общем случае надо читать несколько символов наперёд, чтобы решить, что надо переходить в другое состояние (из-за кавычек и переносов строки). С кавычками хватает Peek у стандартного StreamReader'а. А с переносом строки сложнее. Самое простое, что придумал, это создать свой Reader, который перед каждым чтением буфера бэкапирует предыдущее состояние. А потом по специальному методу CancelLastReading он восстанавливает его. Но решение довольно ресурсозатратное.
Кто как решает эту проблему (если сталкивались)?
Пасиб.
P.S. Вот этот класс. Решение абсолютно черновое. Писал, лишь бы юнит тесты прогонялись.
public class ExStreamReader : IDisposable {
private Stream _stream;
private Encoding _encoding;
private Decoder _decoder;
private char[] _buffer;
private int _bufferSize;
private int _bufferPosition;
private char[] _newLine;
private bool _endOfStream;
private long _lastBaseStreamPosition;
private int _lastBufferPosition;
private int _lastBufferSize;
private char[] _lastBuffer;
public ExStreamReader(Stream stream, Encoding enconding)
: this(stream, enconding, 1024) {
}
public ExStreamReader(Stream stream, Encoding enconding, int bufferSize) {
_stream = stream;
_endOfStream = _stream.Length == 0;
_encoding = enconding;
_decoder = _encoding.GetDecoder();
NewLineSymbol = "\n";
ByteBufferSize = bufferSize;
_buffer = new char[ByteBufferSize];
}
public bool EndOfStream {
get {
return (_stream.Position == _stream.Length) && (_bufferPosition == _bufferSize);
}
}
public int Read() {
char[] ch = new char[1];
int rez = Read(ch, 0, 1);
if (rez > 0) {
return ch[0];
} else {
return -1;
}
}
public string ReadString(int charsToRead) {
return new string(Read(charsToRead));
}
public char[] Read(int charsToRead) {
char[] ch = new char[charsToRead];
int rez = Read(ch, 0, charsToRead);
if (rez != charsToRead) {
char[] n_rez = new char[rez];
Array.Copy(ch, n_rez, rez);
return n_rez;
} else {
return ch;
}
}
public int Read(char[] buffer, int startIndex, int charsToRead) {
SaveInformationForCancelling();
int charsReaded = 0;
int destArrayStartIndex = startIndex;
while (charsReaded < charsToRead && !EndOfStream) {
if (_bufferPosition >= _bufferSize) {
ReadBuffer(_stream, _decoder, ref _buffer, ref _bufferPosition, ref _bufferSize, ref _endOfStream);
}
int rlCharsToRead = (charsToRead - charsReaded);
if (rlCharsToRead > _bufferSize - _bufferPosition) {
rlCharsToRead = _bufferSize - _bufferPosition;
}
Array.Copy(_buffer, _bufferPosition, buffer, destArrayStartIndex, rlCharsToRead);
charsReaded += rlCharsToRead;
destArrayStartIndex += rlCharsToRead;
_bufferPosition += rlCharsToRead;
}
return charsReaded;
}
private void SaveInformationForCancelling() {
_lastBaseStreamPosition = _stream.Position;
_lastBufferPosition = _bufferPosition;
if (_lastBuffer == null || _lastBuffer.Length != _buffer.Length) {
_lastBuffer = new char[_buffer.Length];
}
_buffer.CopyTo(_lastBuffer, 0);
_lastBufferSize = _bufferSize;
}
public void CancelLastReading() {
_stream.Position = _lastBaseStreamPosition;
_bufferPosition = _lastBufferPosition;
_bufferSize = _lastBufferSize;
_buffer = new char[ByteBufferSize];
if (_lastBuffer != null) {
_lastBuffer.CopyTo(_buffer, 0);
}
}
private void ReadBufferTailed(Stream stream, Decoder decoder, int tailStart, int tailSize, ref char[] buffer, ref int bufferPosition, ref int bufferSize, ref bool endOfStream) {
var tail = new char[tailSize];
Array.Copy(buffer, bufferPosition, tail, 0, tailSize);
Array.Copy(tail, 0, buffer, 0, tailSize);
ReadBuffer(stream, decoder, ref buffer, ref bufferPosition, ref bufferSize, tailSize, ByteBufferSize - tailSize, ref endOfStream);
bufferPosition = 0;
bufferSize = bufferSize + tailSize;
}
private void ReadBuffer(Stream stream, Decoder decoder, ref char[] buffer, ref int bufferPosition, ref int bufferSize, ref bool endOfStream) {
ReadBuffer(stream, decoder, ref buffer, ref bufferPosition, ref bufferSize, 0, ByteBufferSize / 2, ref endOfStream);
}
private static void ReadBuffer(Stream stream, Decoder decoder, ref char[] buffer, ref int bufferPosition, ref int bufferSize, int startWritingFrom, int bytesToRead, ref bool endOfStream) {
var b_buffer = new byte[bytesToRead];
var cnt_read = stream.Read(b_buffer, 0, bytesToRead);
if (cnt_read == 0) {
bufferPosition = 0;
bufferSize = 0;
endOfStream = true;
} else {
bufferPosition = startWritingFrom;
var chars_read = decoder.GetChars(b_buffer, 0, cnt_read, buffer, startWritingFrom);
bufferSize = chars_read;
}
}
private int _byteBufferSize;
public int ByteBufferSize {
get { return _byteBufferSize; }
private set {
if (value < 6) {
throw new ArgumentException("You cannot set buffer size shorter than maximum symbol size (6 bytes)");
}
_byteBufferSize = value;
}
}
public string NewLineSymbol {
get {
return new string(_newLine);
}
set {
_newLine = value.ToCharArray();
}
}
public long Position {
get {
return _stream.Position - _bufferSize + _bufferPosition;
}
}
public void Dispose() {
}
}
всю ночь не ем, весь день не сплю — устаю
Re: Чтение файла: заглянуть на несколько символов вперёд
Да нет никакой проблемы, тем более — с CSV Переносов, кстати, тоже, в CSV строка файла == строка таблицы. Просто читаете целиком одну строку в свой буфер и ходите по нему сколько угодно. Но необходимости в таком хождении в общем случае тоже нет. Даже читая посимвольно из однонаправленного потока, складываете символы в буфер, пока не обнаружите конец лексемы, а потом уже смотрите, что за лексема. Для кавычек и т.п. просто заведите ещё одно состояние, да и всё.
"Нормальные герои всегда идут в обход!"
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
N>И проблема с тем, что в общем случае надо читать несколько символов наперёд
Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось.
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, matumba, Вы писали:
M>Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось.
А как? Хоть намекните...
Я так понимаю, что можно добавить новые состояния, когда парсер "съел" половину переноса строки и ожидает вторую. Но при этом надо запоминать уже съеденную часть, чтобы в случае, если перенос строки не состоялся поменять поведение — в общем какой-то головняк.
Вот мой алгоритм:
private string[] ReadCsvLine() {
var rez = new List<string>();
var state = ReadingState.ExpectDataStart;
bool end_of_line = false;
char[] extra_data = null;
StringBuilder current_data = null;
do {
if (_reader.EndOfStream) {
switch (state) {
case ReadingState.Data:
case ReadingState.ExpectDataStart: {
AddValue(rez, current_data);
break;
}
case ReadingState.QuotedData: {
throw new CsvParserException("Unexpected end of line!");
}
case ReadingState.ExpectSeparator: {
// do nothingbreak;
}
default: {
throw new CsvParserException(string.Format("Unknown state [{0}]", state));
}
}
end_of_line = true;
break;
}
char cur = (char)_reader.Read();
switch (state) {
case ReadingState.ExpectDataStart: {
if (cur == '"') {
current_data = new StringBuilder();
state = ReadingState.QuotedData;
} else if (cur == ',') {
AddValue(rez, current_data);
} else if (IsNewLine(cur, _reader)) {
AddValue(rez, current_data);
state = ReadingState.NoRead;
end_of_line = true;
} else {
current_data = new StringBuilder();
current_data.Append(cur);
state = ReadingState.Data;
}
break;
}
case ReadingState.Data: {
if (cur == '"') {
throw new CsvParserException(string.Format("Unexpected quota inside data! Position: [{0}]", _reader.Position));
} else if (cur == ',') {
AddValue(rez, current_data);
current_data = null;
state = ReadingState.ExpectDataStart;
} else if (IsNewLine(cur, _reader)) {
AddValue(rez, current_data);
current_data = null;
state = ReadingState.NoRead;
end_of_line = true;
} else {
current_data.Append(cur);
if (extra_data != null) {
current_data.Append(extra_data);
}
}
break;
}
case ReadingState.QuotedData: {
if (cur == '"') {
if (NextSymbolIsQuota(_reader)) {
current_data.Append(cur);
_reader.Read();
} else {
AddValue(rez, current_data);
current_data = null;
state = ReadingState.ExpectSeparator;
}
} else {
current_data.Append(cur);
}
break;
}
case ReadingState.ExpectSeparator: {
if (cur == ',') {
current_data = null;
state = ReadingState.ExpectDataStart;
} else if (IsNewLine(cur, _reader)) {
state = ReadingState.NoRead;
end_of_line = true;
} else {
throw new CsvParserException(string.Format("Expected separator! Position: [{0}]", _reader.Position));
}
break;
}
default: {
throw new CsvParserException(string.Format("Unknown state [{0}]", state));
}
}
} while (!end_of_line);
return rez.ToArray();
}
private void AddValue(List<string> data, StringBuilder sb) {
if (sb != null) {
data.Add(sb.ToString());
} else {
data.Add(null);
}
}
private bool NextSymbolIsQuota(ExStreamReader reader) {
if (reader.EndOfStream) {
return false;
} else {
char nc = (char)reader.Read();
reader.CancelLastReading();
return nc == '"';
}
}
private bool IsNewLine(char ch, ExStreamReader reader) {
if (ch == _newLine[0]) {
bool is_new_line = true;
var buf = new char[_newLine.Length - 1];
int bytes_read = reader.Read(buf, 0, buf.Length);
for (int i = 0; i < bytes_read; i++) {
char val_from_buf = buf[i];
char val_from_nl = _newLine[i + 1];
if (val_from_buf != val_from_nl) {
is_new_line = false;
break;
}
}
if (is_new_line) {
return true;
} else {
reader.CancelLastReading();
return false;
}
} else {
return false;
}
}
private enum ReadingState {
ExpectDataStart = 0, Data, QuotedData, ExpectSeparator, NoRead /* expected that reading will not be performed in this state */
}
строго говоря он даже не совсем мой. я его слизал откуда-то и доработал на предмет распознавания разных переносов строк и ещё какой-то мульки (уже не помню).
всю ночь не ем, весь день не сплю — устаю
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Jolly Roger, Вы писали:
JR> Даже читая посимвольно из однонаправленного потока, складываете символы в буфер, пока не обнаружите конец лексемы, а потом уже смотрите, что за лексема.
А кстати, может в этом и соль. Я ориентируюсь на начало лексемы, а возможно надо на конец. Надо обмозговать, когда время будет.
всю ночь не ем, весь день не сплю — устаю
Re: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
N>Писал csv парсер и столкнулся с проблемой, когда стандартных библиотечных функций как будто бы не хватает.
Конечно нехватает. Парсеры писать вручную работа неблагодарная совсем.
Почему бы не использовать готовые парсеры (я не верю что нет доступных csv-парсеров)? Или же не сгенерировать его тем же Coco/R-ом? Хотя я бы Nemerle.Peg задействовал
/* иЗвиНите зА неРовнЫй поЧерК */
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, hardcase, Вы писали:
H>Конечно нехватает. Парсеры писать вручную работа неблагодарная совсем. H>Почему бы не использовать готовые парсеры (я не верю что нет доступных csv-парсеров)?
Всё начиналось с быстрого решения на MSJET. Потом оно оказалось неспособным что-то читать и пришлось уже думать над чем-то своим.
H>Или же не сгенерировать его тем же Coco/R-ом? Хотя я бы Nemerle.Peg задействовал
Знал бы, я б попробовал, конечно. Но сдаётся мне, что это поможет только по части ускорения написания (что не есть проблема). Мне-то судя по-всему надо правильно выделить состояния конечного автомата.
Плюс нехватка времени на изучение новых горизнтов даёт о себе знать.
В общем, сменил подглючноватый ExStreamReader на другую версию (сменив подход — теперь просто буферизую заранее прочитанные символы):
public class ExStreamReader : IDisposable {
private StreamReader _reader;
private InternalBuffer _buffer;
public ExStreamReader(Stream stream, Encoding enconding) {
_reader = new StreamReader(stream, enconding);
_buffer = new InternalBuffer(_reader);
}
public char Read() {
if (_buffer.IsEmpty) {
return (char)_reader.Read();
} else {
return _buffer.Read();
}
}
public int PreRead(ref char[] buffer, int index, int count) {
return _buffer.PreRead(ref buffer, index, count);
}
public void ConfirmPreRead() {
_buffer.Clear();
}
public bool EndOfStream {
get {
return _reader.EndOfStream;
}
}
public long Position {
get { return _reader.BaseStream.Position; }
}
public void Dispose() {
_reader.Dispose();
}
private class InternalBuffer {
private StreamReader _rdr;
private Queue<char> _buf = new Queue<char>();
public InternalBuffer(StreamReader rdr) {
_rdr = rdr;
}
public int PreRead(ref char[] buffer, int index, int count) {
int bytes = _rdr.Read(buffer, index, count);
for (int i = index; i < count + index; i++) {
_buf.Enqueue(buffer[i]);
}
return bytes;
}
public char Read() {
if (IsEmpty) {
throw new InvalidOperationException("You cannot read from InternalBuffer when it is empty");
}
return _buf.Dequeue();
}
public bool IsEmpty {
get {
return _buf.Count == 0;
}
}
public void Clear() {
_buf.Clear();
}
}
}
а сам парсер остался практически без изменений. Вроде работает и по скорости будет гораздо лучше, хотя исходный вопрос остаётся открытый.
всю ночь не ем, весь день не сплю — устаю
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
H>>Или же не сгенерировать его тем же Coco/R-ом? Хотя я бы Nemerle.Peg задействовал N>Знал бы, я б попробовал, конечно. Но сдаётся мне, что это поможет только по части ускорения написания (что не есть проблема). Мне-то судя по-всему надо правильно выделить состояния конечного автомата. N>Плюс нехватка времени на изучение новых горизнтов даёт о себе знать.
Когда я набросал на скорую руку парсер джейсона на Peg, был удивлен не столько скоростью написания (благо я уже юзал другие генераторы парсеров и в скорости написания peg не несет особых преимуществ, кроме тесной интеграции с .net), сколько скоростью самого парсера, он оказался быстрее рукописного Newton.Json в полтора раза. А автор джейсона вобщем-то обращает внимание на вопросы производительности.
Нехватка времени довольно смешная причина делать задачу вручную не пользуясь инструментами для этого созданными.
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
N>Здравствуйте, matumba, Вы писали:
M>>Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось. N>А как? Хоть намекните... N>Я так понимаю, что можно добавить новые состояния, когда парсер "съел" половину переноса строки и ожидает вторую.
Зачем?
Состояний у парсера очень немного.
1. BeforeData
2. WithinData
3. WithinQuotedData
4. RightAfterTheQuote
Переводы строк лучше склеивать, т.к. некоторые источники ограничиваются CR без LF. А "пустых строк" в CSV не бывает, поэтому CR CR = CR LF = LF LF = CR LF CR LF = "один перевод строки".
Схема переходов примитивна:
Здравствуйте, Ziaw, Вы писали:
Z>Нехватка времени довольно смешная причина делать задачу вручную не пользуясь инструментами для этого созданными.
Ага. Я бы даже сказал — парадоксальная. Просто (видимо) народ настолько привык к тому, что внешние "тулы" очень трудно сконфигурированный и прикрутить к процессу сборки, что и отношение соответствующие.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>А зачем такие задачи вообще вручную решать? Я вижу только одну причину — изучение ОК.
Ну ты же знаешь — я от переднего края отстал на годы. Для меня всё ещё написать свой парсер CSV с нуля, потом поматериться и отладить, потом поматериться и ускорить, потом поматериться и снова отладить — проще, чем даже взять готовый.
А уж тем более чем взять готовый генератор парсеров.
Можешь, кстати, показать, как правильные пацаны сейчас пишут парсер CSV? (Предположим, что все готовые парсеры — заведомое УГ).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Чтение файла: заглянуть на несколько символов вперёд
Если хочется иметь look-a-head, тем более для такого простого парсера — избавляемся от посимвольных чтений вообще, работаем только с буфером. Это не сложно, и на порядок быстрее.
Re[6]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Sinclair, Вы писали:
S>Ну ты же знаешь — я от переднего края отстал на годы. Для меня всё ещё написать свой парсер CSV с нуля, потом поматериться и отладить, потом поматериться и ускорить, потом поматериться и снова отладить — проще, чем даже взять готовый.
Да Вы батенька не отсталис! Вы батенька стареете похожес.
S>А уж тем более чем взять готовый генератор парсеров. S>Можешь, кстати, показать, как правильные пацаны сейчас пишут парсер CSV? (Предположим, что все готовые парсеры — заведомое УГ).
Да я тоже уже постарел. В показательных выступлениях не участвую. Как грится — дорогу молодежи!
Скажу только, что парсер CSV пишется с использованием того же PegGrammar-а где-то за час. Без опыта за 3.
В качестве примера могу показать свой парсер XML-я с брэкджеком и шлюхами (со сплайсами и встроенными операторами foreach, when и unless) — здесь. Он правда по сложнее раз эдак в несколько, но за счет декларативности код грамматики влезает на один экран (сравнимый рукописный парсер на шарпе потянет строк эдак на 1000).
. Он правда (по его же словам), с ним не за час справился, а за три, но то в основном потому, что опыта мало было. Зато обошелся без вопросов в форумах.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
F>Если хочется иметь look-a-head, тем более для такого простого парсера — избавляемся от посимвольных чтений вообще, работаем только с буфером. Это не сложно, и на порядок быстрее.
Я пропустил что-то новое в теории парсеров?
Раньше принято было считать, что быстрее все будет при заглядывании вперед на 0-1 символ, а чем больше заглядывание, тем медленнее разбор (в плоть до экспоненты).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
M>>Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось. N>А как? Хоть намекните... N>Я так понимаю, что можно добавить новые состояния, когда парсер "съел" половину переноса строки и ожидает вторую. Но при этом надо запоминать уже съеденную часть....
Ты сам себе намекнул.
Весь автомат укладывается в 3 состояния с сохранением промежуточного буфера:
0: читаем и запоминаем поля (обрабатывая запятую), пока не попадём на кавычки. Кавычки -> 1
1: Мы внутри строки — запоминаем символы или ждём очередную кавычку. Кавычки -> 2
2: Здесь ждём либо кавычки, либо запятую, обрабатываем соответственно (т.к. кавычки могут быть удвоенными внутри строки и просто окончание строки).
В конце проверяем состояние, если 1 — это ошибка. Не забываем про аккумулятор.
Для большей наглядности нарисуй этот автомат — что и в каком состоянии может быть — он не тривиален, но без трюков.
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Раньше принято было считать, что быстрее все будет при заглядывании вперед на 0-1 символ, а чем больше заглядывание, тем медленнее разбор (в плоть до экспоненты).
Тем более, что буферизация должна быть строго ортогональна алгоритму, собственно, разбора. Ещё не хватало свой BufferedStream каждый раз писать.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Переносов, кстати, тоже, в CSV строка файла == строка таблицы. Просто читаете целиком одну строку в свой буфер и ходите по нему сколько угодно. Но необходимости в таком хождении в общем случае тоже нет. Даже читая посимвольно из однонаправленного потока, складываете символы в буфер, пока не обнаружите конец лексемы, а потом уже смотрите, что за лексема. Для кавычек и т.п. просто заведите ещё одно состояние, да и всё.
"Нормальные герои всегда идут в обход!"
Ну и ладно, задачу всё равно это практически не усложняет.
