Розбір XML зі швидкістю світла (2012)

Передмова

XML — це стандартизована мова розмітки, яка визначає набір правил для кодування ієрархічно структурованих документів у текстовий формат, зрозумілий людині. XML широко використовується: від дуже коротких і простих документів (таких як запити SOAP) до багатогігабайтних документів (OpenStreetMap) із складними зв’язками даних (COLLADA). Для обробки XML-документів користувачам зазвичай потрібна спеціальна бібліотека: аналізатор XML, який перетворює документ із тексту у внутрішнє представлення. XML — це компроміс між продуктивністю синтаксичного аналізу, зручністю для читання людиною та складністю коду аналізу. Таким чином, швидкий аналізатор XML може зробити більш кращим вибір XML як основного формату для моделі даних програми.

У цьому розділі описуються різноманітні прийоми підвищення продуктивності, які дозволили автору написати дуже потужний синтаксичний аналізатор на C++: pugixml. Незважаючи на те, що методи використовувалися для синтаксичного аналізатора XML, більшість із них можна застосувати до аналізаторів інших форматів або навіть до непов’язаного програмного забезпечення (наприклад, алгоритми керування пам’яттю широко застосовуються до інших парсерів).

Оскільки існує кілька суттєво різних підходів до синтаксичного аналізу XML, і синтаксичний аналізатор має виконувати додаткову обробку, про яку не знають навіть люди, знайомі з XML, важливо спочатку повністю описати поставлене завдання, перш ніж занурюватися в деталі реалізації. .

Моделі аналізу XML

Кожен із різних шаблонів синтаксичного аналізу XML підходить у різних ситуаціях і впливає на продуктивність і споживання пам’яті. Широко використовуються такі моделі:

За допомогою синтаксичних аналізаторів SAX (Simple API for XML) користувач надає синтаксичному аналізатору вхідний потік документів і кілька зворотних викликів, наприклад «початковий тег», «кінцевий тег», «символьні дані всередині маяка». Синтаксичний аналізатор викликає зворотні виклики на основі даних документа. Контекст, необхідний для аналізу, обмежений глибиною поточного дерева елементів, що означає, що вимоги до пам’яті значно зменшуються. Цей тип аналізу можна використовувати для розповсюдження документів, якщо в певний час доступна лише частина документа. Синтаксичний аналіз за витягуванням подібний до SAX у процесі аналізу, тобто документ обробляється по одному елементу, але керування зворотним: у SAX аналіз контролюється аналізатором через зворотні виклики, тоді як у аналізі за запитом користувач контролює процес аналізу. через ітератор-подібний об'єкт. За допомогою аналізаторів об’єктної моделі документа (DOM) користувач надає аналізатору весь документ як текстовий потік/буфер, з якого аналізатор генерує об’єкт документа – представлення в пам’яті всього дерева документа, яке має окрему об’єкт для кожного конкретного елемента або атрибута XML і набір дозволених операцій (наприклад, «отримати всі дочірні елементи цього вузла»). Pugixml слідує цій моделі.

Вибір моделі аналізу зазвичай залежить від розміру та структури документа. Оскільки Pugixml є аналізатором DOM, він ефективний для документів, які:

достатньо малі, щоб поміститися в пам’яті, мають складну структуру з посиланнями між вузлами, які потрібно обійти, або необхідність складних перетворень документів.

Pugixml зосереджується на проблемі синтаксичного аналізу DOM в основному тому, що, хоча швидкі та легкі парсери SAX (такі як Expat) були доступні, усі готові до виробництва аналізатори XML DOM на момент створення pugixml (2006) були або не дуже легкий, не дуже швидкий, або - зазвичай - ні те, ні інше. Таким чином, основна мета pugixml — бути дуже швидкою та легкою бібліотекою обробки XML на основі DOM.

XML визначається рекомендацією W3C, яка визначає два різні типи синтаксичного аналізу: перевіряючий і неперевіряючий (іншими словами, аналізатори без перевірки перевіряють синтаксис XML, а аналізатори перевірки також можуть перевіряти семантику даних). Навіть неперевіряючий синтаксичний аналізатор має виконувати відносно ресурсомістку перевірку.

Якщо головною метою є продуктивність, необхідно знайти компроміс між продуктивністю та відповідністю. Для pugixml компроміс такий: будь-який добре сформований XML-документ буде повністю проаналізований, включаючи всі необхідні перетворення, окрім декларацій типу документа. Оскільки перевіряються лише правила швидкої перевірки, неправильно сформований документ іноді можна успішно проаналізувати.

Дані в XML-документі часто потрібно певним чином трансформувати, перш ніж вони досягнуть користувача. Перетворення включають обробку закінчення рядка, нормалізацію значення атрибута та розширення посилань на символи. Ці перетворення мають пов’язану вартість продуктивності; pugixml максимально оптимізує їх, надаючи можливість вимкнути їх для досягнення максимальної продуктивності.

Поставленим завданням є створення швидкого синтаксичного аналізатора DOM, який успішно аналізує відповідні XML-документи за допомогою необхідних передач...