![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
metaclassУбил наверно дня 4 на поиск бага в простейшем парсере.
Вводная: есть девайс, который непрерывно пишет данные вида:
Start
ConvertData
Sensor=0
... some uninteresting data
Value=23.4
... some uninteresting data
Sensor=1
... some uninteresting data
Value=23.5
... some uninteresting data
ADC
Channel=0
Value=345
Start
..далее все повторяется
Это дело читается енумератором и подается на парсер, завернутый в enumeratee. Парсер сделан на основе attoparsec, в основном, по той причине, что он легко конвертируется в iteratee-enumeratee.
Ключевой момент с этим парсером в том, что он умеет инкрементальный парсинг. Т.е. я подаю ему данные по кускам, он возвращает continuation, если ему недостаточно данных для продолжения работы. Именно поэтому он хорошо интегрируется с пакетом enumerator. Кроме того, мне упорно мерещится, что этот парсер сам по себе является реализацией Iteratees, т.к. их типы данных почти изоморфны друг другу.
Парсер состоит из двух уровней: первый разбирает поток в последовательность значений DeviceMsgs с двумя конструкторами:
Ссылка на код парсера: parseDeviceMsg
Второй уровень парсера анализирует последовательность уже DeviceMsg. Там имеется парсер последовательности "[Sensor/пропустить ненужные данные/Value/пропустить ненужные данные]"
И вот конкретно парсер для пропуска ненужных данных "skipMany isNotValue" ломается с грохотом и треском, если:
1) подавать данные не одной строкой, а по частям, при этом разбиение на части происходит перед или внутри строки Value
2) не добавить в парсер DeviceMsg пропуск whitespace после сообщения (строка с комментарием bugfix в исходнике по ссылке.
Т.е. суть бага: если парсеру "skipMany isNotValue" подавать данные с разбиением на границе не-срабатывания isNotValue (т.е. там где этот парсер должен закончить свою работу) - он не может сделать backtracking на позицию "до не-срабатывания isNotValue". Но только в том случае, если isNotValue не ждет в конце себя whitespace.
Чтобы выделить и найти ошибку, пришлось по очереди:
0)на каждом шаге обкуриваться исходниками Control.Applicative, Data.Attoparsec и прочего )
1)запилить неисчислимые количества traceShow во все углы программы
2)заменить чтение из ком-порта на подачу данных из файла
3)вычитать из девайса строки ровно в той последовательности кусков в которой их выдает enumerator и сделать из этого список
4)сделать функцию которая инкрементально кормит списком аттопарсековые парсеры.
5)сделать функцию которая берет строку и индекс в ней, разбивает ее на список из двух строк "до индекса" и "после индекса", подает их на парсер и проверяет - сломалось или нет. Это все делается в цикле по индексу от 0 до конца строки. Это показало что валится, если строка разбита в районе Value.
6)Сделать тестовый список, гарантированно ломающий инкрементальный парсинг
7)Уменьшать список и его парсеры, добиваясь, чтобы баг c разницей результатов парсинга [l1,l2] и [BS.append l1 l2] все равно проявлялся.
8)Свести баг парсера к вызову skipMany isNotValue
9)Начать модифицировать парсер parseDeviceMsg в попытке понять "что здесь воще творится?".
10) Добавить к нему "skipWhile isSpace_w8" посмотреть что все заработало, нихера не понять.
В общем, я формального способа понять, почему в одном варианте оно работает, в другом нет - не знаю. Вижу что проблема в backtracking+инкрементальный парсинг, но внутренности attoparsec, например - это ад из cps и адовых техник оптимизации.
Я даже не знаю, можно ли это вообще хотя бы в теории запустить под отладчиком.
Разве что отладчик будет рисовать граф и его редуцировать пошагово.
И да, "если прога на хаскеле компилируется - это не значит что она работает".
Вводная: есть девайс, который непрерывно пишет данные вида:
Start
ConvertData
Sensor=0
... some uninteresting data
Value=23.4
... some uninteresting data
Sensor=1
... some uninteresting data
Value=23.5
... some uninteresting data
ADC
Channel=0
Value=345
Start
..далее все повторяется
Это дело читается енумератором и подается на парсер, завернутый в enumeratee. Парсер сделан на основе attoparsec, в основном, по той причине, что он легко конвертируется в iteratee-enumeratee.
Ключевой момент с этим парсером в том, что он умеет инкрементальный парсинг. Т.е. я подаю ему данные по кускам, он возвращает continuation, если ему недостаточно данных для продолжения работы. Именно поэтому он хорошо интегрируется с пакетом enumerator. Кроме того, мне упорно мерещится, что этот парсер сам по себе является реализацией Iteratees, т.к. их типы данных почти изоморфны друг другу.
Парсер состоит из двух уровней: первый разбирает поток в последовательность значений DeviceMsgs с двумя конструкторами:
data DeviceMsg =
Header BS.ByteString
| KeyValue BS.ByteString BS.ByteString
deriving (Show,Eq)
Ссылка на код парсера: parseDeviceMsg
Второй уровень парсера анализирует последовательность уже DeviceMsg. Там имеется парсер последовательности "[Sensor/пропустить ненужные данные/Value/пропустить ненужные данные]"
И вот конкретно парсер для пропуска ненужных данных "skipMany isNotValue" ломается с грохотом и треском, если:
1) подавать данные не одной строкой, а по частям, при этом разбиение на части происходит перед или внутри строки Value
2) не добавить в парсер DeviceMsg пропуск whitespace после сообщения (строка с комментарием bugfix в исходнике по ссылке.
Т.е. суть бага: если парсеру "skipMany isNotValue" подавать данные с разбиением на границе не-срабатывания isNotValue (т.е. там где этот парсер должен закончить свою работу) - он не может сделать backtracking на позицию "до не-срабатывания isNotValue". Но только в том случае, если isNotValue не ждет в конце себя whitespace.
Чтобы выделить и найти ошибку, пришлось по очереди:
0)на каждом шаге обкуриваться исходниками Control.Applicative, Data.Attoparsec и прочего )
1)запилить неисчислимые количества traceShow во все углы программы
2)заменить чтение из ком-порта на подачу данных из файла
3)вычитать из девайса строки ровно в той последовательности кусков в которой их выдает enumerator и сделать из этого список
4)сделать функцию которая инкрементально кормит списком аттопарсековые парсеры.
5)сделать функцию которая берет строку и индекс в ней, разбивает ее на список из двух строк "до индекса" и "после индекса", подает их на парсер и проверяет - сломалось или нет. Это все делается в цикле по индексу от 0 до конца строки. Это показало что валится, если строка разбита в районе Value.
6)Сделать тестовый список, гарантированно ломающий инкрементальный парсинг
7)Уменьшать список и его парсеры, добиваясь, чтобы баг c разницей результатов парсинга [l1,l2] и [BS.append l1 l2] все равно проявлялся.
8)Свести баг парсера к вызову skipMany isNotValue
9)Начать модифицировать парсер parseDeviceMsg в попытке понять "что здесь воще творится?".
10) Добавить к нему "skipWhile isSpace_w8" посмотреть что все заработало, нихера не понять.
В общем, я формального способа понять, почему в одном варианте оно работает, в другом нет - не знаю. Вижу что проблема в backtracking+инкрементальный парсинг, но внутренности attoparsec, например - это ад из cps и адовых техник оптимизации.
Я даже не знаю, можно ли это вообще хотя бы в теории запустить под отладчиком.
Разве что отладчик будет рисовать граф и его редуцировать пошагово.
И да, "если прога на хаскеле компилируется - это не значит что она работает".
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Не понимаю я вас
Date: 2011-11-20 10:30 am (UTC)— Зачем?
— И напляшемся и наипемся!
Re: Не понимаю я вас
Date: 2011-11-20 10:32 am (UTC)Бездны сатаниские!
Date: 2011-11-20 10:38 am (UTC)Re: Бездны сатаниские!
Date: 2011-11-20 10:54 am (UTC)Пока руководство не убедит меня, что этого делать не надо.
Поосторожнее бы надо
Date: 2011-11-20 10:55 am (UTC)Re: Бездны сатаниские!
Date: 2011-11-20 10:26 pm (UTC)к чему вся эта рекурсивная самоебля?
Re: Бездны сатаниские!
Date: 2011-11-21 05:05 am (UTC)А на работе я предусмотрительно ничего не делаю, чтобы другие потом могли понять.
Re: Бездны сатаниские!
Date: 2011-11-21 07:28 am (UTC)Re: Бездны сатаниские!
Date: 2011-11-21 07:57 am (UTC)Re: Бездны сатаниские!
Date: 2011-11-21 08:38 am (UTC)Re: Бездны сатаниские!
Date: 2011-11-21 08:40 am (UTC)Re: Бездны сатаниские!
Date: 2011-11-25 12:25 am (UTC)загадочные уходят в первую очередь. из опыта.
Re: Бездны сатаниские!
Date: 2011-11-21 08:43 am (UTC)Re: Бездны сатаниские!
Date: 2011-11-25 12:22 am (UTC)Вот поэтому я обычно пишу свои парсеры
Date: 2011-11-20 10:35 am (UTC)Re: Вот поэтому я обычно пишу свои парсеры
Date: 2011-11-20 10:55 am (UTC)Упс
Date: 2011-11-20 11:59 am (UTC)no subject
Date: 2011-11-20 11:42 am (UTC)no subject
Date: 2011-11-20 11:54 am (UTC)no subject
Date: 2011-11-20 12:46 pm (UTC)no subject
Date: 2011-11-20 11:57 am (UTC)no subject
Date: 2011-11-20 12:14 pm (UTC)А как выглядит isNotValue? И что значит "ломается с грохотом и треском"?
no subject
Date: 2011-11-20 12:42 pm (UTC)Т.е. парсер, ничего не возвращающий, но успешно отрабатывающий только в случае, если пришло не сообщение Value=...
Замечание от К.О.
Date: 2011-11-20 12:55 pm (UTC)no subject
Date: 2011-11-20 03:27 pm (UTC)1. skipWhile isSpace_w8 пропускает пробелы и в какой-то момент запрашивает часть символов из Value=1, эти символы идут в добавку (которая Added)
2. работает парсер вида a <|> b, где a успешно отработает, тогда из определения (<|>) видим, что вся добавка, которую мы получили до входа в a будет отброшена.
3. дальше по списку идёт испорченная добавка, а результате восстанавливаем неправильное состояние.
Вот мой код и пример как вопроизвести проблему:
Тут я вижу два варианта: 1. убрать skipWhile isSpace_w8 перед (<|>); 2. использовать безоткатные парсеры (задача позволяет).
no subject
Date: 2011-11-20 03:40 pm (UTC)no subject
Date: 2011-11-22 02:41 pm (UTC)no subject
Date: 2011-11-23 02:12 am (UTC)no subject
Date: 2011-11-20 03:49 pm (UTC)no subject
Date: 2011-11-20 05:18 pm (UTC)no subject
Date: 2011-11-20 05:06 pm (UTC)Но позвольте — как же он служил в очистке? (C)
no subject
Date: 2011-11-21 06:19 am (UTC)Если взглянуть на attoparsec, то можно заметить, что он состоит из двух частей (условно): Data.Attoparsec и Data.Attoparsec.Combinator. Проблемы возникли с комбинаторной частью, которая одновременно самая медленная в attoparsec (поэтому её не рекомендуют использовать в документации к attoparsec).
Парсеры из Data.Attoparsec (т.е. takeWhile, skipWhile, scan и прочие) это такие продвинутые итераторы написанные вручную: они быстрые, смотрят только на один символ вперёд. Отсюда два следствия: 1) обычно их и используют; 2) у них нет проблем с возвратом при инкрементальном разборе.
> Т.е. должно быть известно, что инкрементальный аттопарсек не работает
Вполне возможно, что об этом и не знают, нужно писать автору.
no subject
Date: 2011-11-21 06:25 am (UTC)Хотел сказать, что в документации к attoparsec не рекомендуют использовать комбинаторы:
no subject
Date: 2011-11-21 07:29 am (UTC)Если код на функциональном языке менее прозрачен, чем на императивном - нахрена он такой нужен? Так что "ад из cps и адовых техник оптимизации" использовать нельзя, лучше взять какой-нибудь нормальный генератор парсеров, выдающий код на C.
no subject
Date: 2011-11-21 07:51 am (UTC)no subject
Date: 2011-11-21 08:07 am (UTC)2. Те, что под це -
2.1. хорошо обкатаны
2.2. дают шустрый код на выходе