Анализ обработки событий в объектно-событийной модели документа. Полевой Д.В.
Существующие средства создания и языки представления электронных форм позволяют внедрять в документ правила контроля заполнения. Взаимодействие с пользователем при этом осуществляется с использованием объектно-событийной модели, что может приводит к зацикливанию исполнения правил. Эта работа посвящена проблеме создания документов с прогнозируемым ацикличным поведением. Построенная математическая модель обработки событий, связанных с изменением (редактированием) документа, и запуска процедур, контролирующих заполнение, может легко адаптироваться к конкретной модели документа и особенностям реализации среды исполнения правил.
1. Введение
Одним из возможных способов увеличения эффективности работы с документами является использование интерактивных возможностей современных технологий [1]. Применительно к документообороту – это возможность создавать документы, которые сами проверяют правильность вводимых данных при заполнении и подсказывают, как исправить ошибки. По оценкам некоторых экспертов [13] до трети бумажных документов требуют повторного заполнения в связи с ошибками. Использование “умных” документов позволяет значительно сократить затраты времени и средств, поскольку автоматический контроль используется на самом раннем этапе – при создании документа. Заполнив и, например, распечатав такой документ, можно быть уверенным, что реквизиты указаны в соответствии с правилами и инструкциями. Существующие форматы представления, средства создания и манипулирования ЭД позволяют внедрять в документ исполняемый код. Таким образом, форма может нести в себе контроль целостности вводимых данных.
ГОСТ Р 51141-98 [3] определяет документ следующим образом: “зафиксированная на материальном носителе информация с реквизитами, позволяющими ее идентифицировать”, где реквизит документа – это “обязательный элемент оформления официального документа”. Далее под документом (документом в узком смысле слова, структурированным документом, формой) подразумевается именно так определенный объект.
Реквизиты документа в соответствии с ГОСТом делятся на следующие части:
постоянная часть реквизита документа - неизменяемая часть реквизита документа, содержащаяся в бланке документа, наносимая при его изготовлении. Назовем ее статической частью документа. Она формируется при создании электронного документа и в дальнейшем не изменяется.
переменная часть реквизита документа - изменяемая часть реквизита документа, вносимая в бланк документа при его заполнении. Назовем ее динамической частью документа. Обычно, электронное представление позволяет использовать ЭВМ непосредственно для заполнения бланка. Поля ввода - элементы программного интерфейса, позволяющие изменять данные.
Один реквизит соответствует одному или нескольким полям ввода.
2. Объектно-событийная модель электронного документа.
Одной из широко используемых моделей документа является Document Object Model (DOM) [9], [10]. DOM – это интерфейс прикладного программирования (API) для “правильных” HTML [11] и XML документов [8], [12]. Он определяет логическую структуру документов, способы доступа и манипулирования данными. Используя DOM, программист может строить документы, перемещаться по структуре, добавлять, изменять и удалять элементы и их содержимое.
Одной из главных целей создания DOM было обеспечение программистов стандартным API взаимодействия с документом. Важно, что этот API стандартизирован и спроектирован для использования с любым языком программирования в широком круге приложений и сред.
В DOM документ имеет логическую структуру очень похожую на дерево, а точнее, на лес деревьев. Каждый документ имеет ноль или один узел тип документа, один узел элемент документа и ноль или более комментариев или инструкций. Элемент документа используется как корень для дерева элементов документа. Однако, спецификация не определяет, что документ должен быть реализован именно как дерево (лес деревьев). Она так же не накладывает никаких ограничений на реализацию взаимоотношений между объектами. DOM – это логическая модель, которая может быть реализована любым удобным способом.
Заметим, что непосредственно значения реквизитов в древовидной модели документа является данными объектов, которые в свою очередь обеспечивают манипуляции с этой информацией.
Логическая модель документа в другом широко распространненом формате формате PDF [6],[4] не соответствует DOM, но имеет очень много схожего. Документ может быть представлен как иерархия объектов с определенными свойствами и методами, точнее, внутри документа существует несколько различных иерархий. Документ представлен как дерево страниц. Каждая страница содержит описание визуального представления и набор аннотаций, часть которых может быть полями ввода.
Общим для таких достаточно развитых форматов является возможность использования скриптов, т.е. документ может содержать набор инструкций, выполняющих ту или иную деятельность: изменять данные и свойства элементов документа, выводить диалоги, и т.д.
Назовем контекстом исполнения конкретную программу-интерпретатор, обеспечивающую взаимодействие с пользователем и исполняющую код скрипта (Internet Explorer,Netscape, Acrobat Reader).
В результате действий пользователя или работы скриптов может наступить выполнение какого-то условия – такую ситуацию назовем событие. Если существует написанный пользователем обработчик этого события, то он исполняется, если такого нет, то система действует на свое усмотрение (в т.ч. порождая новые события). Таким образом, обработкой события назовем вызов пользовательского скрипта, а обработчиком события – непосредственно сам скрипт. Более подробно останавливаться на реализациях внутреннего механизма обработки и диспетчеризации событий контекстом не будем.
Обычно для каждого класса объектов в спецификации формата определено, какие события для него возможны. В документе конкретным событиям объектов формы назначаются обработчики (чаще всего, как вызов функций).
3. Проблемы прогнозирования поведения событийной системы.
Можно рассматривать состояние ЭД, в виде совокупности значений всех реквизитов и вспомогательных переменных - т.е. всех переменных, участвующих в условиях переходов. Тогда изменение значения одной из управляющих переменных будет означать изменение состояния документа, а число состояний будет определяться максимально возможным количеством комбинаций значений управляющих переменных, возникающим при работе. Событийная система, которой является электронный документ в момент заполнения, сильно отличается от обычных программ – действиями пользователя могут быть созданы практически любые переходы между состояниями. Поведение же программы при непредусмотренном переходе может быть различным: от нарушения защиты памяти до продолжения функционирования с созданием различного рода побочных эффектов.
4. Формальная модель обработки событий.
Определение 1. Назовем событием выполнение некоторого условия.
Определение 2. Назовем обработчиком события процедуру, которая выполняется при наступлении события.
Определение 3. Правильным считается такой обработчик события, который не содержит внутри себя бесконечных циклов, т.е. его работа завершается за конечное число шагов (выполнения элементарных операций и вызова подпрограмм).
Определение 4. Правильным называется документ с правильным обработчик событий.
Далее рассматриваются только правильные обработчики.
В событийных системах обработка событий обычно организуется с помощью той или иной разновидности очереди. Обозначим очередь
Q={q1,..,qn},
множество упорядоченных вызовов обработчиков событий. Из ii обрабатывается раньше, чем событие qj. Помещение события в очередь означает то, что в очередь помещается вызов обработчика этого события.
Обозначим через Qt состояние очереди после обработки первых t элементов, если Qt-1. Q0 – состояние очереди до начала обработки.
Аксиома 1.
События из очереди обрабатываются последовательно и если в процессе исполнения обработчика генерируются новые события, то они помещаются в конец очереди.
Это соответствует обычной работе очереди без приоритетов.
Аксиома 2.
Исполнение одной команды скрипта приводит помещению в очередь конечного числа событий.
Под командой понимается элементарная конструкция языка или вызов функции.
Утверждение 1.
Обработка события приводит к помещению в очередь не более чем счетного и конечного множества событий.
Обработчик считается “правильным”, т.е. его работа заканчивается за конечное число исполнения команд скрипта. Обработка каждой инструкции по аксиоме 1 приводит к помещению в очередь не более, чем конечного числа событий, следовательно, утверждение верно.
Аксиома 3.
В результат обработки одного события в очередь не попадают одинаковые события.
Последняя аксиома практически всегда выполняется при правильно спроектированном обработчике.
На обработку события требуется некоторое время, поэтому события в очереди могут накапливаться. Пусть начиная с некоторого момента времени пользователь больше не производит действий, приводящих к генерации новых событий. Обозначим состояние очереди Q0 и рассмотрим ее дальнейшее поведение.
Назовем зацикливанием такую ситуацию, когда обработка очереди не заканчивается за конечное число шагов.
Документ состоит из конечного и счетного числа объектов, для каждого из которых определено не более чем счетное и конечное число событий. Поэтому для конкретной формы существует не более чем конечное и счетное множество E всех событий e.
 (1)
Пусть Q0={q}, т.е. в очереди только одно событие q. Обозначим через M1q последовательность событий, порождаемых обработкой события q. Если M1q не пусто, то процесс обработки пойдет дальше. Вообще, Mnq – последовательность событий, порождаемых при обработке последовательности Mn-1q , если таковая не пуста и пустая последовательность в противном случае.
Для математического описания воспользуемся рекурсивным соотношением.
 (2)
, где k – порядковый номер события в последовательности.
Такое определение Mnq нетрудно обобщить на случай, когда Q0 содержит более одного элемента.
 (2)
Обработка событий заканчивается, если
 (4)
Определение 5. Скажем, что событие e1 порождает событие e2, если в результате обработки события e1 событие e2 попадает в очередь.
Утверждение 2.
Зацикливание обработки событий возможно тогда и только тогда, когда в очереди появляется событие, пораждающее само себя, т.е.
 (5)
Возможность зацикливания при выполнении условия очевидна. Покажем обратное.
Пусть условие не выполняется, т.е.
 (6)
покажем, что очередь может быть обработана за конечное число шагов.
Для этого рассмотрим вспомогательный алгоритм.
Алгоритм 1.
Назовем n-м слоем все вершины дерева, построенные на n-м шаге алгоритма, и обозначим Ln. Вершинам дерева припишем соответствующие события.
Шаг 0. Выбрать одно событие q, которое станет корнем дерева. L0 = {q}
Шаг n. Для каждой вершины sLn-1 : M1s добавить в качестве потомков элементы последовательности M1s. Ребра будем ориентировать от потомков к предкам.
Пример.
M1q = {e,v,u}, M1e = {v,t}, M1v = {}, M1u = {v}, , M1t = {…}
Пример первых 3-х слоев дерева, построенных по алгоритму.
Рис. 1
Видно, что Ln= Mnq. Для произвольной вершины v слоя Lk можно построить путь до корня дерева. Из событий, соответствующих проходимым вершинам, образуется последовательность k уникальных элементов. Действительно, если в этой последовательности есть повторяющиеся события, то условие (6) не выполняется. Таким образом в дереве не может быть более |E| слоев, а для v, по аксиоме 3 и условию (6), существует не более |E|-k потомков. Соответственно в каждом слое содержится не более, чем
 (7)
элементов, а все дерево состоит не более, чем из
 (8)
вершин.
Построенное так дерево соответствует попаданию событий в очередь, следовательно, очередь будет обработана не более, чем за V шагов.
Для обобщения на случай многоэлементного Q0 можно ввести фиктивное событие ф, единственным результатом обработки является переход очереди в состояние Q0. Больше в очередь такое событие не попадет, т.е. условие для ф выполняется. Дополним множество Е событием ф и проведем рассуждения аналогичные вышеприведенным.
Требование выполнения аксиомы 3 не является очень жестким и от него можно отказаться. Достаточно заметить, что оно никак не влияет на максимальную глубину дерева и ограниченность количества узлов в каждом слое.
5. Граф зависимостей обработки событий.
Ориентированный граф обработки событий отражает возможные зависимости попадания событий в очередь.
 (9)
EG – множество событий, AG – множество зависимостей.
 (10)
 , означает, что при обработке u в очередь попадет v.
Рассмотрим произвольное правило r из множества всех правил документа R, rR.
К его активации могут привести события из множества Ein инициирующих событий а в результате работы скрипта сгенерироваться события из множества Eout порождаемых событий. Т.е. в терминах событий правило r определяет пару множеств
Er = { Erin, Erout } (11)
Следует заметить, что в результате выполнения правила в очередь обработки не обязательно попадут все или даже хотя бы одно событие из EOut . Однако точный подход требует анализа исходного кода и в общем случае не представляется возможным. Нас интересует самый “плохой” исход, чтобы выявить все потенциальные зацикливания.
Правило r задает подмножество связей событий
 (12)
одно событие может приводить к выполнению нескольких правил, поэтому множество связей событий для документа
  (13)
и множество событий для документа
 (14)
Подграф зависимостей, построенный для правила r.
Рис. 3
Нетрудно заметить, что
 (15)
с точностью до повторений событий, пораждаемых при обработке события.
Тогда состояние очереди событий может быть описана в терминах графа зависимостей событий
Mne = { qEG: путь в EG длинной n между q и e } (16)
По построению видно, что условие потенциального зацикливания обработки событий (5) эквивалентно наличию цикла в EG. Имея описание всех правил документа в форме (11), можно с помощью стандартных алгоритмов поиска циклов в графе [2] реализовать поиск подозрительных цепочек, где возможны зацикливания, и при наличии последних предъявить их пользователю.
6. Выводы
Описание правил в терминах множеств событий (инициирующих и пораждаемых) и последующий анализ графа зависимостей позволяет выявлять потенциально опасные места еще на этапе проектирования системы контроля логики заполнения электронного документа. Выявленные потенциальные циклы могут быть проанализированы более, тщательно для принятия решения о пересмотре правил. Так же на основании этой модели можно строить безопасные, с точки зрения зацикливания, системы интерактивного ввода информации.
Построенная в статье математическая модель обработки события была реализована для автоматизации построения скриптов электронных документов в форматах PDF и HTML.
Ссылки:
Арлазаров В.Л., Безмозгий И.М., Емельянов Н.Е. Проблемы перехода к безбумажному делопроизводству // Развитие безбумажной технологии в организационных системах. Сборник трудов Института системного анализа РАН, 1999 г.
В. Липский Комбинаторика для программистов // Москва “Мир” 1988.
М.Свами, К.Тхуласираман Графы, сети и алгоритмы // Москва “Мир”, 1985.
Государственный стандарт РФ ГОСТ Р 51141-98, ”Делопроизводство и архивное дело. Термины и определения”.
Acrobat JavaScript Object Specification, Version 5.0 // Adobe Systems Incorporated, 2001.
Adobe Portable Document Format, Version 1.4 // Adobe Systems Incorporated, 2002.
ECMAScript Language Specification // Standard ECMA-262.
Extensible Markup Language (XML) 1.0 (Second Edition) // W3C Recommendation 6 October 2000. // http://www.w3.org/TR/2000/REC-xml-20001006
Document Object Model (DOM) Level 3 Core Specification, Version 1.0 // W3C Working Draft 14 January 2002. // http://www.w3.org/TR/2002/WD-DOM-Level-3-Core-20020114/
Document Object Model (DOM) Level 3 Events Specification, Version 1.0 // W3C Working Draft 23 August 2001. // http://www.w3.org/TR/2001/WD-DOM-Level-3-Events-20010823/
HTML 4.01 Specification // W3C Recommendation 24 December 1999. // http://www.w3.org/TR/html401/
XForms 1.0 // W3C Working Draft 18 January 2002. // www.w3.org/TR/2002/WD-xforms-20020118/
Joyce E. Endres The Total Systems Approach to Forms Automation // http://enterprise.state.wi.us/static/forms/white_paper.htm
|
