# Огляд frawk
*Цей документ передбачає деякі базові знання з Awk. Я виявив, що [Awk за 20 хвилин](https://ferd.ca/awk-in-20-minutes.html)
є надійним вступом, тоді як [**сторінка Гримуара**](https://www.grymoire.com/Unix/Awk.html)
містить більше деталей. Відповідно до загальноприйнятої практики, я був
непослідовним у цьому репо з тим, як я використовую великі літери в
«AWK».*
Мій примірник [книги про AWK](https://en.wikipedia.org/wiki/The_AWK_Programming_Language)
починається з простого повідомлення:
> Користувачі комп'ютерів витрачають багато часу, виконуючи прості
> механічні маніпуляції з даними — змінюючи формат даних,
> перевіряючи їх достовірність, знаходячи елементи з певною властивістю,
> додаючи числа, друкуючи звіти тощо\... Awk — це мова програмування,
> яка дозволяє виконувати такі завдання за допомогою дуже коротких
> програм.
Сьогодні я вважаю, що цей діагноз вірний: я проводжу багато часу,
займаючись дрібним текстом. Незважаючи на всі його недоліки як мови, я
вважаю, що Awk є дуже цінним інструментом, коли така «коротка програма»
є бажаною. Я написав frawk, щоб мати можливість писати програми Awk за
інших обставин. Це не означає, що я хочу, щоб frawk був версією Awk з
функціями вищого рівня; Я ціную, що Awk рідко уникає лабораторії
однорядкових програм і не має бажання писати великі програми мовою,
подібною до Awk.
Frawk усуває два основних недоліки, які я знайшов у Awk.
1. Відсутність підтримки структурованих вхідних даних у форматі CSV.
2. Іноді — невдала продуктивність.
Ми можемо взяти кожен з них по черзі, а потім перейти до того, як
реалізується frawk. Перш ніж заглибитися в бур'яни, я хочу пояснити, що
моєю головною метою при запуску цього проекту було дізнатися щось нове:
я хотів написати невеликий компілятор, я хотів дізнатися про LLVM і
хотів зробити базовий статичний аналіз. З цього приводу frawk мав
неперевершений успіх.
**Frawk** все ще неповний. Я виявив, що
цього достатньо для моїх повсякденних сценаріїв, але деякі
функції Awk ще не реалізовані, і реалізація, ймовірно, набагато менш
стабільна, ніж ті, які ви знаєте і любите. Якщо відкинути ці
застереження, ось чому я думаю, що frawk цікавий.
## Трохи структуровані дані
Frawk з опцією `-i csv` буде належним чином аналізувати та екранувати
дані CSV. У цьому розділі пояснюється, чому це цінно.
Awk обробляє дані рядок за рядком, розбиваючи за допомогою «роздільника
записів», який (по суті) є регулярним виразом. Це означає, що написати
сценарій досить легко:
```awk
awk - F',' ' NR > 1 { SUM += $2 } END { print SUM }'
```
підсумувати другий стовпець у файлі, де поля завжди розмежовують комами.
Наступне введення дасть `6`.
Item,Quantity
Carrot,2
Banana,4
Однак сценарій дасть неправильний результат, якщо вхідним є файл CSV з
вбудованими комами в деяких полях, наприклад:
Item,Quantity
Carrot,2
"The Deluge: The Great War, America and the Remaking of the Global Order, 1916-1931", 3
Banana,4
У цьому випадку другим полем третього рядка буде текст «Америка та
перебудова глобального порядку», який буде мовчки примусово приведений
до числа 0, тим самим нічого не вносячи в загальну суму та занижуючи
суму на 3.
Іншими словами, стандартний синтаксис посилань у Awk на стовпці за
допомогою `$1`, `$n`, тощо, може не працювати, якщо вхідним є
екранований файл CSV. На практиці я виявив, що не можу довіряти Awk у
роботі з великим файлом CSV, де я не можу вручну перевірити, чи немає в
полях вбудованого «`,`». Але frawk з опцією `-i csv` буде належним
чином аналізувати та екранувати дані CSV. Awk — це досить виразна
мова, якою можна було б розібрати CSV вручну, але це громіздко й
неефективно.
## Ефективність та спеціально створені інструменти
frawk часто набагато швидший, ніж такі утиліти, як
[gawk](https://www.gnu.org/software/gawk/) і [mawk](https://invisible-island.net/mawk/), під час аналізу великих файлів даних або виконання особливо
інтенсивних обчислень. Основними причинами вищої продуктивності frawk є:
1. frawk визначає типи для своїх змінних, тому він вирішує, які змінні
є числами, а які рядками, перш ніж запустити програму. Це може
прискорити арифметику в жорстких циклах, а також усуває
розгалуження, коли справа доходить до виконання примусу між рядками
та числами. frawk досягає цього, зберігаючи майже всю семантику Awk:
єдині помилки типу, які дає frawk, це також помилки типу в Awk.
2. Той факт, що frawk створює типізоване подання, дозволяє йому
генерувати досить простий CLIF або LLVM IR, а потім JIT цей IR для
машинного коду під час виконання. Це дозволяє уникнути накладних
витрат на перекладач ціною кількох мілісекунд часу під час запуску.
frawk надає інтерпретатор байт-коду (увімкнений за допомогою
параметра `-Binterp`) для менших скриптів і для допомоги в
тестуванні.
3. frawk використовує деякі досить новітні методи [ефективної перевірки UTF-8](https://github.com/lemire/fastvalidate-utf-8),
[аналізу CSV](https://github.com/geofflangdale/simdcsv)
та [розбору чисел з плаваючою комою](https://github.com/lemire/fast_double_parser).
Крім того, він використовує високоякісні реалізації [регулярних виразів](https://github.com/rust-lang/regex)
і [стандартних колекцій](https://github.com/rust-lang/hashbrown), а також кілька інших корисних бібліотек від спільноти Rust.
Той факт, що в існуючих реалізаціях Awk, як правило, не вистачає великої
підтримки CSV, у поєднанні з слабкою продуктивністю на більших наборах
даних у порівнянні з такою мовою, як Rust, означало, що розробники
вдалися до створення спеціальних інструментів для обробки файлів CSV і
TSV. Такі інструменти, як [xsv](https://github.com/BurntSushi/xsv) і
[tsv-utils](https://github.com/eBay/tsv-utils),
чудові; якщо ви ще не перевірили їх і помічаєте, що обробляєте великі
обсяги табличних даних, варто потрохи їх переглянути. Але хоча ці
інструменти швидкі, вони не є повною заміною Awk. Вони не забезпечують
повноцінної мови програмування, і виконувати з ними навіть помірно
складні операції може бути громіздко.
Я виявив, що навіть для коротких програм frawk працює порівняно з xsv
для даних CSV і в 2-3 рази швидше для даних TSV порівняно з tsv-utils.
frawk може виконувати запити, подібні до tsv-utils, до даних CSV за
значно менший час, ніж `csv2tsv` може
конвертувати дані в TSV. Я думаю, що це досить хороший компроміс, якщо
ви хочете виконати операцію вищого рівня, яку ці та інші інструменти не
підтримують. Перегляньте документ із [контрольними показниками](https://github.com/ezrosent/frawk/blob/master/info/performance.md),
щоб отримати жорсткі цифри щодо цього.
## Структура frawk
frawk структурований як звичайний компілятор та інтерпретатор. За
допомогою вихідного коду frawk аналізує його, перетворює на кілька
проміжних уявлень, генерує код нижнього рівня та виконує його.
1. [Лексер](https://github.com/ezrosent/frawk/blob/master/src/lexer.rs)
токенізує вихідний код frawk.
2. Синтаксичний аналізатор створює абстрактне синтаксичне дерево (
[AST](https://github.com/ezrosent/frawk/blob/master/src/ast.rs)
) з потоку маркерів.
3. AST перетворюється на нетипований контрольний потоковий графік (
[CFG](https://github.com/ezrosent/frawk/blob/master/src/cfg.rs)
). Ми виконуємо [перетворення](https://github.com/ezrosent/frawk/blob/master/src/dom.rs)
[SSA](https://en.wikipedia.org/wiki/Static_single_assignment_form)
на цьому CFG.
4. З CFG у формі SSA [алгоритм
висновку](https://github.com/ezrosent/frawk/blob/master/src/types.rs)
призначає типи всім змінним у програмі.
5. Враховуючи нетипований CFG і результати алгоритму висновку, ми
можемо створити типізований CFG з явними інструкціями байт-коду. (Це відбувається [тут](https://github.com/ezrosent/frawk/blob/master/src/compile.rs) .)
6. Звідти код опускається до однієї з (a) [байт-інструкцій](https://github.com/ezrosent/frawk/blob/master/src/bytecode.rs)-коду,
які можна [інтерпретувати](https://github.com/ezrosent/frawk/blob/master/src/interp.rs)
безпосередньо, (b) [LLVM-IR](https://github.com/ezrosent/frawk/blob/master/src/codegen/llvm/mod.rs),
який компілюється JIT і потім запускається, або (c)
[cranelift](https://github.com/ezrosent/frawk/blob/master/src/codegen/clif.rs).
Більшість із цього є досить стандартним. Перші кілька кроків можна
знайти (наприклад) у [Книзі тигрів](https://www.cs.princeton.edu/~appel/modern/ml/).
Я використав це як основне посилання, а також читав про альтернативи
алгоритму Ленгауера-Тарьяна для побудови SSA, які були опубліковані
після «Книги тигрів».
Ви можете переглянути текстове представлення нетипізованого CFG,
передавши прапор `--dump-cfg` у frawk. Байт-код і LLVM можна
переглянути за допомогою параметрів `--dump-bytecode` і `--dump-llvm`.
Останній буде оптимізований; `-O0`. Перехід приблизно покаже LLVM,
створений frawk.
Щоб уникнути тривалого часу компіляції та складних збірок, код LLVM і
Cranelift виконує виклики функцій у той самий час виконання, яке
використовується для інтерпретації інструкцій байт-коду. Переміщення
більшої частини коду часу виконання в згенерований код під час
складання, ймовірно, призведе до швидшої програми, оскільки це дасть
LLVM (і меншою мірою, Cranelift) більше можливостей для вбудовування й
оптимізації викликів під час виконання. Поточний підхід допомагає
скоротити час складання, а налаштувати збірку просто.
### Статичний аналіз
Я прочитав чудову книгу *[Static Program Analysis](https://cs.au.dk/~amoeller/spa/)*,
створюючи frawk. Серед іншого, він показав мені, що багато
властивостей програми можна апроксимувати як рішення (потенційно
рекурсивних!) рівнянь, визначених у відповідному частковому порядку,
якщо функції, що визначають ці рівняння, є [монотонними](https://en.wikipedia.org/wiki/Monotonic_function%23Monotonicity_in_order_theory).
Крім того, можна розв'язати ці рівняння, пропустивши їх через прості
мережі [в стилі розповсюдження](https://www.youtube.com/watch?v%3Ds2dknG7KryQ),
поки їх значення не перестануть змінюватися. Основними прикладами цього є:
- Виведені [типи](https://github.com/ezrosent/frawk/blob/master/src/types.rs)
для змінних frawk. Щоб дізнатися більше про виведення типу,
перегляньте [цей документ](https://github.com/ezrosent/frawk/blob/master/info/types.md).
- [Висновок, які стовпці не потрібно
аналізувати.](https://github.com/ezrosent/frawk/blob/master/src/pushdown.rs)
- Визначення , на [які глобальні змінні](https://github.com/ezrosent/frawk/blob/0cf6bd7554ba14193f32337ea54bd1a8f1401f1f/src/compile.rs#L694)
посилається функція, і функції, які вона викликає.
- [Виключення](https://github.com/ezrosent/frawk/blob/master/src/input_taint.rs)
потенційно небезпечних викликів оболонки.
Все це було реалізовано за допомогою дуже корисної бібліотеки [petgraph](https://github.com/petgraph/petgraph).
## Відмінності від AWK
структура і мова frawk запозичені майже оптом з Awk; використання frawk
дуже схоже на використання mawk, nawk або gawk. frawk також підтримує
багато складніших функцій Awk для реалізації, наприклад printf, і
визначені користувачем функції. Хоча багато поширених ідіом від Awk
підтримуються у frawk, деякі функції відсутні, а інші надають тонко
несумісну семантику. Будь ласка, подайте запит на функцію, якщо певний
елемент поведінки, на який ви покладаєтесь, відсутній; ніщо в реалізації
frawk не перешкоджає можливостям стандартної мови Awk, хоча деякі можуть
бути проблемними для реалізації.
Цей список відмінностей не є вичерпним. Зокрема, я не був би здивований,
якщо б виявив, що в парсері frawk є помилки.
### Чого не вистачає
- За замовчуванням frawk використовує бібліотеку
[ryu](https://github.com/dtolnay/ryu)
для друку чисел з плаваючою комою, а не змінну `CONVFMT`. Явна зміна
точності виводу з плаваючою комою вимагає відповідного виклику
`printf `або `sprintf`.
- `next`, або `nextfile` підтримуються у frawk, але їх можна
викликати лише з основного циклу. Я не зустрічав жодного сценарію
Awk, який використовує будь-яку з цих команд всередині функції, і це
велике спрощення просто заборонити цей випадок. Знову ж таки, дайте
мені знати, чи це важливий для вас варіант використання.
- Багато розширень з gawk (наприклад, спільні процеси, багатовимірні
масиви) також не реалізовані. Більшість «книжкових» вбудованих
функцій і команд awk на даний момент підтримуються, але, будь ласка,
повідомте про проблему, якщо ви помітили якісь прогалини.
- Хоча це ніколи не пробували, я щиро сумніваюся, що frawk буде
працювати добре — або взагалі — на 32-розрядній платформі. Я
підозрюю, що він буде працювати набагато повільніше на 64-розрядній
архітектурі без x86.
### Що нового
- frawk підтримує параметри командного рядка, які розбивають усі
вхідні дані (незалежно від значення `-i csv`) відповідно до
форматів CSV та TSV, призначаючи необробленому рядку та N-му полю в
поточному рядку, повністю екрановані. Існує також еквівалентна
функція для вихідних CSV-екранованих рядків (увімкнено за
допомогою). `-i tsv FS RS $0 $N -o csv -o tsv`
- frawk має вбудовану функцію `join_fields`, яка створює рядок
певного діапазону вхідних стовпців.
- frawk надає функцію `int` для перетворення скалярного значення в
ціле число, а також функцію `hex` для перетворення шістнадцяткового
рядка в ціле число. Він також підтримує шістнадцяткові числові
літери.
- Для сценаріїв, які запускаються з одним із параметрів `icsv`,
`itsv`, сценаріїв, які розбиваються лише пробілами, або сценаріїв,
які використовують лише один однобайтовий запис і роздільник полів,
frawk підтримує [паралельне](https://github.com/ezrosent/frawk/blob/master/info/parallelism.md)
виконання сценарію .
- Далі побітові оператори `gawk `підтримуються через вбудовані
модулі `and`, `or`, `compl`, `lshift`, `rshift `і `xor`.
Frawk також підтримує `rshiftl` — логічний зсув вправо. На
відміну від `gawk`, функції `and`, `or` і `xor` не є змінними.
- Функції frawk можуть повертати масиви, виклики функцій можуть
зʼявлятися в позиції масиву для циклу for-each.
- За допомогою прапорця `-H` frawk аналізує перший рядок введення (без
оновлення `NR` або `FNR`) і заповнює вбудовану змінну `FI` вмістом
полів у першому рядку, що відповідає їхньому індексу. Отже, у
сценарії, який аналізує файл із полем під назвою «count» у стовпці
6, вираз `$FI["count"]`поводиться як `$6`. Реалізація цієї функції у
frawk добре поєднується з аналізом проекції.
### Чим відрізняється
Жодна з цих відмінностей не є фундаментальною для підходу frawk; без них
*можна* обійтися, за певну ціну. Повідомте мені, якщо ви виявите більше
розбіжностей або виявите, що наведене нижче є серйозною перешкодою:
- *Синтаксис регулярних* виразів frawk наразі використовує синтаксис
[регулярних](https://docs.rs/regex/1.3.7/regex/)
виразів Rust. Це схоже, але не тотожне, до синтаксису регулярного
виразу Awk. Я розглядав можливість впровадження власного механізму
регулярних виразів або компіляції регулярних виразів Awk у регулярні
вирази rust; це просто не те, що я встиг зробити.
- *Порівняння рядків.* Порівняння одного рядка з іншим завжди
використовує лексикографічне впорядкування. Порівнюючи два рядки,
Awk спочатку перевіряє, чи обидва рядки є числами, а потім порівнює
їх чисельно, якщо вони є. Я вважаю цю семантику досить
неінтуїтивною: з одного боку, це означає, що два «рівних» рядки
можуть хешувати різні значення в масиві. Це також означає, що досить
важко чітко вибрати лексикографічне порівняння. З іншого боку,
вибрати числове порівняння досить легко: просто додайте один з
операндів до 0. Щоб зберегти деякі ідіоми, frawk приводить усі
операнди до чисел, якщо один з їхніх операндів є числом; це зберігає
звичайний варіант використання (наприклад) фільтрації числового
стовпця за числовою константою. Я виявив, що ця семантика є більш
передбачуваною, а також більш простою у реалізації.
- *Нульові значення та точки з\'єднання.* Нульові значення у frawk
іноді можуть бути приведені до цілих чисел. Наприклад
`if (0) { x = 5 }; printf "[%s]", x;`, буде друкувати `[]` в
Awk і друкуватиме `[0]` у frawk. Це основна причина, з якої підхід
frawk до типів може «протікати» в реальні програми.
- *UTF-8* frawk може приймати довільні байти, але регулярні вирази та
printf підтримують UTF-8. frawk не перевіряє введення за
замовчуванням, але прапорець `--utf8 `дозволяє ефективну перевірку
UTF-8 для всіх введених даних.
- *Пакетування пакетів frawk* для читання та запису даних досить
агресивне в порівнянні з більшістю реалізацій Awk, з якими я
стикався. Це робиться в основному з міркувань продуктивності і
відображає передбачуваний випадок використання «пакетних» сценаріїв
обробки даних.
- frawk підтримує створення підоболонки через синтаксис
`<string> | getline`, або `print[f] ... | <string>,` а також вбудовану
функцію `system`. Наскільки я розумію, подібні функції (де довільний
рядок передається оптом в оболонку) вважаються антишаблонами, і [в деяких мовах](https://www.python.org/dev/peps/pep-0324/%23id14)
їх визнали застарілими, оскільки вони полегшують несанкціонованому
введенню користувача в оману, щоб перетворити його дані в
підоболонку, та потенційно робити з машиною користувача недобрі чи
небажані дії. Щоб пом'якшити це, frawk реалізує [статичний аналіз](https://github.com/ezrosent/frawk/blob/master/src/input_taint.rs)
дір, який суттєво обмежує набір рядків, які можна передати в
оболонку. frawk також забезпечує обхід для випадків, коли вхідні
дані є довіреними або аналіз є занадто консервативним: Прапорець
`-A` виключає користувачів із аналізу дір. Я відкритий для відгуків
щодо розширення або модифікації цієї функції.
