# CHAMELEON: OutSystems Live Bidirectional Transformations

Hugo Lourenço  OutSystems
<EMAIL_ADDRESS>João Costa Seco  NOVA University Lisbon
<EMAIL_ADDRESS>Carla Ferreira  NOVA University Lisbon
<EMAIL_ADDRESS>Tiago Simões  OutSystems
<EMAIL_ADDRESS>Vasco Silva  OutSystems
<EMAIL_ADDRESS>Filipe Assunção  OutSystems
<EMAIL_ADDRESS>André Menezes  OutSystems
<EMAIL_ADDRESS>
###### Abstract

In model-driven engineering, the bidirectional transformation of models plays
a crucial role in facilitating the use of editors that operate at different
levels of abstraction. This is particularly important in the context of
industrial-grade low-code platforms like OutSystems, which feature a
comprehensive ecosystem of tools that complement the standard integrated
development environment with domain-specific builders and abstract model
viewers.

We introduce CHAMELEON, a tool that enables the dynamic definition of a live
bidirectional model transformation in a declarative manner by leveraging
simple and intuitive component patterns. Through this approach, we can
gradually define the view and synthesis paths to an abstract model built on
top of a low-code metamodel.

We devise a standard parser-generating technique for tree-like models that
builds upon extended grammar definitions with constraints and name binders. We
allow for a greater overlap of model patterns that can still be disambiguated
for a clear lens-like behaviour of the transformation.

CHAMELEON is evaluated in the fragment of the OutSystems language targeting
the definition of user interfaces. To assess performance we used a large set
of real OutSystems applications, with approximately 200K UI widgets, and a
database of curated widget patterns. We found a worst-case processing time of
92ms for complete models in our benchmark, which is still suitable for the
operation of an interactive model editor.

###### Index Terms:

low-code, model transformation, virtualization

##  I Introduction

The holy grail of low-code frameworks is to serve a wide set of skilled
professionals. Low-code allows non-expert developers to build software with a
smooth learning curve, and provide experienced developers with a more
productive environment.

Low-code platforms usually work in a specific domain by leveraging the full
power of a given platform or domain-specific language (DSL). However, the
adoption of a DSL or low-code approach is many times accompanied by a limited
expressive power [1], thus forcing a set of programming patterns onto the
developers. Model-based approaches and DSLs with unidirectional model
transformations typically have a write-once nature where changes can only be
done at the higher abstract level. When changes can also be performed on a
more concrete level, they get lost if the higher abstract level evolves. In a
scenario where an abstract representation is shown to the users of the higher
abstract levels, they are usually kept in the dark about the parts of the
concrete model not captured in the more abstract model. In prior work, we
defined a bidirectional approach to “application builders” [2, 3, 4] that does
not have this write-once limitation [5], but still ignores the parts of the
concrete model that application builders do not produce and do not fit the
defined abstractions. The approach we followed in [5] is to define fixed
transformations between abstract models. The transformations are specific to
each “application builder” and the actual OutSystems application metamodel.
For example, there is a builder for the design of business processes [3] and a
builder that uses existing application screens to define the navigation of an
application [2]. Such an approach is only suitable for an asynchronous editing
process where a model is loaded onto a builder, modified, and then transformed
back into the original metamodel.

In this paper, we present a multi-layered bidirectional model-based design
that efficiently abstracts the concrete (native) model using a gradual
approach. Although our approach can be applied to any part of the model, this
paper focuses on the user interface, where concrete components are called
(native) widgets and abstract components are called virtual widgets. We start
with the current OutSystems application model and abstract a set of widget
patterns, progressively defined by experts in a back-office application of the
platform. The abstract model presented to the user, in a virtual widget tree,
is considerably smaller than the native widget tree but, nevertheless,
captures all the components that are not matched to any specified virtual
widget pattern. This set of components left unmatched and not abstracted, are
not hidden away, but remain visible to the user in the form of properly
bounded native widgets. Our approach thus supports a gradual model
transformation that allows the definition of new virtual widget patterns to
capture more and more parts of the concrete model. Step by step, the complex
widget tree of the native model is abstracted into a more intuitive and
simpler virtual widget tree.

We specially focus on the efficiency of the parsing process to allow for
changes in the application model to be immediately seen at the abstract level
and vice-versa. We use parsing generator techniques to efficiently scan and
abstract a tree-like model. Unlike traditional bidirectional transformation
engines that work by querying single graph-based patterns on a model one by
one [6, 7], we use a parsing approach that tackles all patterns in a single
pass. By improving on an existing, and slower, detection approach, we aim at
having a live editing experience of the model that can support changes at
different levels of abstraction.

CHAMELEON improves state-of-the-art virtualization techniques at OutSystems
that take several tens of seconds to load and process a typical application
model. In comparison, the new virtualization process takes less than 100 ms
per application model and less than 10 ms per application screen. Furthermore,
our approach can operate in smaller increments, parsing and showing only the
screen that is currently relevant to the user. The overall objective is to
support model editors to operate live at different levels of abstraction while
covering the entirety of the low-code metamodel, and allow model visualization
and edition by diverse developer profiles.

We introduce a metamodel for the virtual widgets that simultaneously defines
the patterns to be captured in the abstract layer and the synthesis process
for virtual widgets into the native model. We use component identifiers to
bind different definitions and express the connection between properties of
the native and abstract models. From the virtual widgets definition, we
generate an attribute grammar with conditions [8, 9]. A virtual widget may
consist of several different patterns, for instance a ”Boolean Input” virtual
widget can be represented either as a checkbox, a switch, or a group of two
buttons representing the True and False alternatives. Pattern definitions may
overlap - two grouped buttons may also be seen as a specific case of an ”Enum
Input” used to select between a fixed set of alternatives.

The grammar produced is inherently ambiguous, which we tackle by building a
custom-defined generalized LR parser [10]. Noticeably, Tomita’s GLR parsers
[10] explore all alternatives in parallel, but we explore alternatives in
sequence giving priority to shift-reduce conflicts to obtain the longest
sequence (ensuring a higher level of virtualization). Our implementation
incorporates backtracking as a way of recuperating from parsing errors and
following to the next alternative.

To capture the substitution process of native widgets by virtual widgets, the
original (native) metamodel is dynamically extended with additional classes to
represent virtual widgets. The abstract metamodel is thus a proper extension
of the native metamodel as it can fully represent native widget applications.
Editors of the abstract model can still represent and preview native widgets,
by using a complete widget tree and a preview functionality for native
widgets, respectively.

We evaluate CHAMELEON using a benchmark with 239 application modules and
approximately 4K screens containing around 200K UI widgets. We used a database
of 106 patterns grouped in 31 virtual widgets. We found linear trends in both
the efficiency and effectiveness of the approach when considering full
application modules. In practice, the parsing of one screen constitutes a
negligible constant pass in the virtualization of individual screens with
parsing times smaller than 10 ms, which enables its integration in an
interactive and collaborative editor of abstract models.

In summary, the main contributions of this work are:

  * •

The system architecture, described in section II, that allows the gradual
definition of new patterns with dynamic extensions to the original metamodel
and allows model editions at multiple levels of abstraction.

  * •

A language to define virtual widgets that simultaneously defines patterns to
be captured and the synthesis process for new components, also described in
section III.

  * •

A multi-layered bidirectional model-based design that efficiently abstracts
the native model in a gradual approach. This means that the parsing process is
a best-effort process that uses all the virtual widgets definitions available
(section IV)

  * •

A synthesis technique that allows the interchangeable use of the widget
patterns of a virtual widget (section V).

We finalize the paper by using a benchmark in section VI to evaluate our
approach and presenting a list of open problems that we leave for future work
(section VIII).

In conclusion, the measure of impact is given by the fact that it is in the
company’s roadmap to be integrated into its main product.

##  II System Architecture

Figure 1: Overview of the proposed approach

The components of the system are shown in the overall architecture diagram
(Fig. 1) and cover the functionalities for three different personas: an
OutSystems Developer that uses the current development environment and the
native model to create applications; a Pattern Designer that uses the native
model to define patterns to group and parametrize them to define virtual
widgets; and the Citizen Developer [11, 12]. Citizen Developers, central to
our work, create applications using virtual widgets. They use a virtual model
editor that presents a simplified but loss-free widget tree that allows the
editing and creation of new virtual widgets instances, the read-only preview
of native widgets (part of the virtual metamodel), and also makes available
selected operations that transform the native model directly and are encoded
into the editor. Such low-level hard-coded operations are available for
pragmatic and historical reasons to support basic construction operations in
the virtual model editor that do not concern the creation of widgets (e.g.
changing the data model in predefined ways.)

The virtual metamodel is generated having as input the definition of the
native metamodel and the set of virtual widgets defined by the pattern
designer. This is represented by the thick arrow on the left-hand side of the
diagram. The virtual metamodel is then used by the virtual model editor to
support its interactions. As expected, the native metamodel is the basis for
the native model editor operations. The virtual widgets definitions are also
used to generate the virtualization (parsing) and synthesis operations.

In section III we present a case study that will support the detailed
description of our parsing method (described in section IV) and the synthesis
process (in section V).

##  III Case Study: UI Patterns

Our work focuses on simplifying the construction of user interfaces via the
introduction of higher-level constructs that are simpler to manipulate and
understand than the underlying model, the low-code OutSystems application
model. In this section, we present a running example containing a simple form
to edit a request in an imaginary corporate application (Fig. 2). The form
allows the introduction of the description of the request along with approval
information. In Fig. 3 we present the metamodel for defining forms, which is a
subset of the actual OutSystems metamodel. A Form consists of a tree of
Widgets. Input widgets are used to obtain data from the user and bind it to a
state variable in the low-code application. Input widgets are specialized
according to the data type: type TextArea is used for textual data, types
Checkbox and Switch are tailored to boolean data, and type ButtonGroup is used
for multiple alternatives, each represented by a ButtonGroupItem widget. The
widget Container is a layout widget used to group other widgets. Widget Label
is used for accessibility purposes, describing an associated input widget.

Figure 2: Request edit form Figure 3: Widgets Metamodel

(a) Native tree

(b) Virtual tree.

Figure 4: Widget trees Figure 5: Three ways of representing a boolean input

In 1 we present the model of Fig. 2, and in 4(a) we depict the visual
representation of the widget tree. For reasons which will become clear in the
next section, we opted to present all models in XML notation.

In our example, the input ”Approved” in the form is used to obtain boolean
data. The developer chose a user-friendly representation ButtonGroup widget
with two alternatives (Yes or No), but it would also be possible to use either
a Checkbox widget or a Switch widget. This simple example illustrates that, in
general, there is more than one equivalent way to represent the same
information (see Fig. 5).

Listing 1: Form model

⬇

1<Form Id="f">

2 <Container Id="c1">

3 <Label Id="l1" Widget="ta">

4 <Text Id="t1" Style="bold" Value="Request description"/>

5 </Label>

6 <TextArea Id="ta" Variable="Request.Description"/>

7 </Container>

8 <Container Id="c2">

9 <Label Id="l2" Widget="bg">

10 <Text Id="t2" Style="bold" Value="Approved by Manager"/>

11 </Label>

12 <ButtonGroup Id="bg" Variable="Request.Approved">

13 <ButtonGroupItem Id="g1" Value="true">

14 <Text Id="t3" Value="Yes"/>

15 </ButtonGroupItem>

16 <ButtonGroupItem Id="g2" Value="false">

17 <Text Id="t4" Value="No"/>

18 </ButtonGroupItem>

19 </ButtonGroup>

20 </Container>

21</Form>

A quick inspection of 1, containing the native model for the example form,
reveals a lot of repetition and unnecessary detail that the developer should
not be concerned about. Each of the two inputs follows the same basic pattern:
a Label containing a Text widget with a descriptive text, followed by an Input
widget of arbitrary complexity bound to a variable. We can reduce the
developer’s effort by introducing higher-level elements, which we denote
virtual widgets, with a simplified API: the developer should only have to
decide which variable to bind to. The specific widget representation can then
be chosen from a set of alternatives, manually or automatically, and, when
needed, the initial value for the label text can be inferred from the
variable.

In Fig. 6 we present the metamodel for virtual widgets, which is an extension
of the native metamodel in Fig. 3. Whenever necessary and to avoid confusion,
we refer to the concrete metamodel and its widgets as native metamodel and
native widgets. In our example, the virtual metamodel includes three new
classes111The new classes are depicted with a yellow background in the
metamodel diagram.: TextInput, BooleanInput, and EnumInput. Each of these
widgets represent a labelled input, and thus contain the Variable and Label
attributes. Each element may correspond to one of several different concrete
patterns, which are identified by the Pattern property. The virtual metamodel
contains slightly modified versions of the classes in the native metamodel
where aggregation relations are relaxed to refer to the Widget base class
instead of one of its subclasses222The modified relations are depicted in
red.. For instance, compare the ButtonGroup virtual widget (Fig. 6) with its
native counterpart (Fig. 3). The next section explains in detail why this
change allows for the gradual transition between native and virtual models.

Taking advantage of the new virtual widgets TextInput and BooleanInput, we
obtain a simplified virtual model (2). A side-by-side comparison of the native
and virtual widget trees as they would be displayed in an IDE (Fig. 4) further
highlights the reduction in complexity.

Figure 6: Virtual Widgets Metamodel Listing 2: Form virtual model

⬇

1<Form Id="f">

2 <Container Id="c1">

3 <TextInput Id="v1" Label="Request description" Pattern="1"
Variable="Request.Description"/>

4 </Container>

5 <Container Id="c2">

6 <BooleanInput Id="v2" Label="Approved by Manager" Pattern="3"
Variable="Request.Approved"/>

7 </Container>

8</Form>

A virtual widget is defined by a list of properties and one or more patterns
(see Table I). These patterns are used for representing virtual widgets in the
virtual model, for viewing/parsing from native to virtual widgets, and for the
synthesis of native widgets. Each pattern consists of a simplified native
widget tree in which we only include the properties that must have a specific
value for the pattern to be matched. Properties whose name is prefixed by
Default are used only during the synthesis phase and do not contribute to the
pattern matching phase. The pattern must also specify the binding of virtual
widget properties to native widget properties. The last line in Table I, which
provides a visual depiction of an instance of the pattern, was added for the
convenience of the reader but is not part of the pattern definition.

In Table I we present the definition of the BooleanInput virtual widget. This
virtual widget declares two properties: Variable and Label, and consists of
three different patterns. A property is made optional by providing a default
value expression, which is used exclusively during synthesis operations. In
our example, the default value for property Label is obtained from the Value
property, as specified by the GetLabelFor(Value) expression333The GetLabelFor
function calculates a suitable human-readable label from a model expression..
Pattern #1 consists of a Label widget containing a Text widget with identifier
t, followed by a Checkbox widget with identifier i. The pattern specifies that
the virtual property Variable is bound to the checkbox’s variable (i.e.
Variable = i.Variable), and the Label property is bound to the text’s value
(i.e., Label = t.Value). Notice that we do not specify the Value of any of the
Text widgets because any value is acceptable444We do provided default values
for two of the Text widgets of Pattern #3 but these, as explained, do not
affect the pattern matching phase.. However, for the two ButtonGroupItem
widgets of Pattern #3 we have explicitly specified their value to be true and
false, respectively, because we only want to recognize that pattern in that
particular case.

We check that patterns are well-formed with respect to the virtual widget
definition (the pattern must provide bindings for each of the virtual widget
properties) and the native metamodel, in order to ensure that the result of
instantiating a virtual widget definition always results in correct native
model.

This representation for virtual widgets is flexible enough to allow for easy
and safe model transformation. For instance, the native model may have been
initially defined with a set of widgets that match Pattern#3, then parsed onto
the virtual model as a BooleanInput virtual widget. The developer can
iteratively choose to use Pattern#1 instead, which is finally transformed back
to the native model as a completely different set of native widgets. This
allows the user to construct an application in more abstract terms, which
allows for configuration steps that do not require complex weaving of
properties, values, and widgets.

TABLE I: Boolean input patterns BooleanInput(Expression Variable, string Label
= GetLabelFor(Value))
---
Pattern#1 | Pattern#2 | Pattern#3
Variable = i.Variable |  Variable = i.Variable |  Variable = i.Variable
Label = t.Value |  Label = t.Value |  Label = t.Value
⬇ <Label> <Text Id="t"/> </Label> <ButtonGroup Id="i"> <ButtonGroupItem
Value="true"> <Text Default.Value="Yes"/> </ButtonGroupItem> <ButtonGroupItem
Value="false"> <Text Default.Value="No"/> </ButtonGroupItem> </ButtonGroup>
|  |

##  IV The basic model parser

$\begin{array}[]{llll}\textit{Form}&::=&\texttt{<Form>}\;\textit{Widget}^{*}\;\texttt{</Form>}\\\
\textit{Widget}&::=&\textit{VirtualWidget}\\\ &|&\textit{NativeWidget}\\\
\textit{VirtualWidget}&::=&\texttt{<Label>}\;\texttt{<Text/>}_{t}\;\texttt{</Label>}\;\texttt{<TextArea/>}_{i}&\mbox{(TextInput.1)}\\\
&|&\texttt{<Label>}\;\texttt{<Text/>}_{t}\;\texttt{</Label>}\;\texttt{<Checkbox/>}_{i}&\mbox{(BooleanInput.1)}\\\
&|&\texttt{<Label>}\;\texttt{<Text/>}_{t}\;\texttt{</Label>}\;\texttt{<Switch/>}_{i}&\mbox{(BooleanInput.2)}\\\
&|&\texttt{<Label>}\;\texttt{<Text/>}_{t}\;\texttt{</Label>}\\\
&&\texttt{<ButtonGroup>}_{i}\\\ &&\texttt{<ButtonGroupItem>}^{\textit{Value =
"true"}}\;\texttt{<Text/>}\;\texttt{</ButtonGroupItem>}\\\
&&\texttt{<ButtonGroupItem>}^{\textit{Value =
"false"}}\;\texttt{<Text/>}\;\texttt{</ButtonGroupItem>}\\\
&&\texttt{</ButtonGroup>}&\mbox{(BooleanInput.3)}\\\
&|&\texttt{<Label>}\;\texttt{<Text/>}_{t}\;\texttt{</Label>}\;\texttt{<ButtonGroup>}_{i}\\\
&&(\texttt{<ButtonGroupItem>}\;\texttt{<Text/>}\;\texttt{</ButtonGroupItem>})^{*}\;\texttt{</ButtonGroup>}&\mbox{(EnumInput.1)}\\\
\textit{NativeWidget}&::=&\texttt{<ButtonGroup>}\;\textit{Widget}^{*}\;\texttt{</ButtonGroup>}&\mbox{(ButtonGroup)}\\\
&|&\texttt{<ButtonGroupItem>}\;\textit{Widget}^{*}\;\texttt{</ButtonGroupItem>}&\mbox{(ButtonGroupItem)}\\\
&|&\texttt{<Checkbox/>}&\mbox{(Checkbox)}\\\
&|&\texttt{<Container>}\;\textit{Widget}^{*}\;\texttt{</Container>}&\mbox{(Container)}\\\
&|&\texttt{<Label>}\;\textit{Widget}^{*}\;\texttt{</Label>}&\mbox{(Label)}\\\
&|&\texttt{<Switch/>}&\mbox{(Switch)}\\\ &|&\texttt{<Text/>}&\mbox{(Text)}\\\
&|&\texttt{<TextArea/>}&\mbox{(TextArea)}\end{array}$ Figure 7: Virtual Widget
Grammar

The virtualization process is accomplished using a parser-based approach. In
this work, we produce a parser generator that takes as input a grammar that
joins the virtual metamodel and a set of virtual widget definitions to produce
a general parser [10] for concrete models. The input grammar for our running
example is depicted in Fig. 7. The grammar is mechanically created from the
definition of the virtual metamodel (Fig. 6) and the definitions for virtual
widgets. Notice that this context-free grammar contains ambiguities between
rules BooleanInput.3 and EnumInput.2. Given the grammar ambiguity, it is
necessary to use a parsing algorithm that explores all possible derivation
trees of a word [13]. We adapted the parser generator algorithm proposed by
Tomita [10] which provides an efficient parsing algorithm for this kind of
grammar.

In the grammar definition presented in Fig. 7, the non-terminal symbols are
represented in italics. The terminal symbols represent native model instances
and are denoted by XML tags, and have an optional subscript identifier and an
optional superscript condition. Besides the structure of the main elements of
the metamodel, the grammar includes rules for each one of the patterns of each
virtual widget (rules TextInput.1, BooleanInput.1, BooleanInput.2,
BooleanInput.3, and EnumInput.1), as well as rules for each of the extended
native widgets.

The rules for virtual widgets are directly obtained from their definition. The
definitions of Table I lead to rules BooleanInput.1, BooleanInput.2, and
BooleanInput.3. For simplicity, we have omitted the definitions of the
TextInput and EnumInput virtual widgets but included the corresponding rules
in the grammar. Patterns can capture the identifiers of model widgets they
match by providing an Id attribute, which corresponds to the terminal symbols
subscripts in grammar rules, and bind it to variables in the semantic actions.
Property value restrictions result in conditions that need to be met during
parsing. Conditions are represented as superscripts in the grammar. For
instance, in the BooleanInput.3 rule the first occurrence of the
<ButtonGroupItem> terminal is annotated with Value = "true". When parsing, if
the condition is not satisfied by the current token then the rule is
immediately rejected. If no other rule is active at that point, the parser
will backtrack to the previous most recent decision point. This approach is
similar but less restrictive than the predicates of pred-LR(k) parsers [8],
which requires exactly one predicate to true when there is more than one
predicate in the currently active rules.

The grammar also includes rules for (extended) native widgets to enable the
gradual extension of the virtual widget set. This ensures that every native
model can be parsed into a virtual model, and the patterns that match the
virtual widgets already defined are abstracted. Looking at our virtual model
example (2), it can be seen that we have a mix of extended native widgets
(Form and Container) and virtual widgets (TextInput.1 and BooleanInput.3) in
the same model.

The patterns in the definition of virtual widgets are allowed to overlap. In
conjunction with the inclusion of rules for the native widgets, this leads to
grammars with a high degree of ambiguity. As an example, consider the widget
sequence of lines 9 to 19 of 1. This sequence can be parsed in several
different ways, namely using either rule BooleanInput.3, EnumInput.1, or
<Label> followed by <ButtonGroup>. As mentioned before, we follow an approach
inspired by Tomita’s GLR parsers [10]. While Tomita explores all parsing trees
in parallel, we keep an active parse tree at each time but remember past
decisions in shift-reduce and reduce-reduce conflict situations, and thus
allow backtracking. Notice that our goal is to find a parse tree as quickly as
possible instead of finding all possible parse trees. According to our
benchmark (detailed in section VI), backtracking happens at a rate of 2.6% per
processed token which in pratice leads to the parser converging quickly. When
encountering a shift-reduce conflict we explore the shift route first and thus
give priority to longer sequences. For reduce-reduce conflicts, we explore the
higher priority rule first, according to an explicit order fixed when defining
the virtual widgets. Additionally, rules for virtual widgets have higher
priority than rules for native widgets.

The semantic action for each virtual widget rule (which we are not
representing in Fig. 7) amounts to creating an instance of the corresponding
virtual widget. The properties for the instance are extracted from the native
widgets according to the pattern property bindings. E.g., rule Boolean.3 is
used to reduce the widget sequence of lines 9 to 19 of 1. Given the property
bindings specified in Pattern #3 (Table I) we obtain the following mapping
between terminals and model widgets: $\\{\texttt{\small
t}\mapsto\texttt{\small t1},\texttt{\small i}\mapsto\texttt{\small bg}\\}$.
Moreover, this association results in the following values for the virtual
widget properties (line 6 of 2):

  * •

Variable = Request.Description

  * •

Label = "Request description"

The value for Variable is calculated as follows:  1. Pattern#3 specifies the
binding Variable = i.Variable,  2. pattern widget i is matched with native
widget bg,  3. replacing i by bg in the binding we Variable = bg.Variable 4.
the value of bg.Variable is Request.Description.

Given the special circumstances of processing a concrete low-code model and
having special conflict resolution policies and backtracking, we have
developed our own GLR parser generator. The characteristics of our specific
use case that made it difficult to directly use any of the widely available
parser generators are the following:

  * •

Grammar ambiguity: most parsers require the grammar to be non ambiguous. As
explained above, our grammars are always ambiguous, by design.

  * •

Ambiguity resolution and backtracking: shift-reduce and reduce-reduce
conflicts are not solved in a single way. Instead, they represent alternatives
that are explored in sequence and from which we may need to backtrack.

  * •

Adapting to new virtual widget definitions: our grammar and the corresponding
parser are generated on the fly (in memory). When a model is loaded in the IDE
the most recent definitions are fetched.

  * •

Conditions in terminal symbols: property value restrictions in the patterns
are represented as conditions in the associated terminal symbols. Hard
restrictions on the parsing time demand these conditions to be evaluated as
soon as possible, instead of waiting until the semantic action (potentially)
rejects the rule.

The inclusion of conditions in terminal symbols is crucial to the conciseness
of our grammars and the efficiency of the parser. Conditions could be
alternatively represented by cloning the relevant terminal symbols. E.g.,
given the existing conditions for terminal ButtonGroupItem, we can split it
into three different terminals <ButtonGroupItem_true>,
<ButtonGroupItem_false>, and <ButtonGroupItem_other> (plus the corresponding
close tags), representing the three relevant cases for the value of the Value
property: true, false, and any other expression. Rule BooleanInput.3 can be
readily converted to use the new terminal symbols, but rule ButtonGroupItem
needs to be split into three different rules, each using one of the new
terminals. Cloning terminal symbols would lead to a combinatorial explosion of
the grammar, and an exponential increase in the number of states in the
parser.

Notice that by construction the conditions on terminal symbols are always of
the form property = value. Our parser generator takes advantage of this fact
to efficiently generate the parser tables. An entry in the parser table
specifies the actions to take (shift / reduce / none) for each terminal / non-
terminal symbol based on the current token. In our representation, each action
may include a decision table like the ones depicted in Table II showing a
fragment of the parser table for our example grammar. When in state 32 of
Table II we have processed the sequence

<Label> <Text/> </Label> <ButtonGroup>

At this point, and according to the parse table, the only expected tokens are
</ButtonGroup> and <ButtonGroupItem>555Any other token results in a parsing
error and the parser backtracking to the most recent decision point.. The
first token results in a reduction action using rule Enum.Input.1 and the
creation of an EnumInput virtual widget. The second token is more interesting.
Recall that the ButtonInput.3 rule has attached the condition Value = "true"
for the first ButtonGroupItem. The parser table in Table II captures this
information by specifying that a shift will happen and that the target state
is determined by the value of the Value property: if the value is true it
shifts to state 37, whereas any other value shifts to state 36.

TABLE II: A fragment of the parser table | Token
---|---
State |  $<\\!\\!/$ButtonGroup$>$ |  $<$ButtonGroupItem$>$
32 | Reduce(EnumInput.1) |  Shift(Value:{ true $\mapsto$ 37,
|  |  other $\mapsto$ 36 })
48 | Reduce(EnumInput.1) |  Shift(Value:{ false $\mapsto$ 50,
|  |  other $\mapsto$ 36 })

##  V Native model synthesis

The virtual widget definitions are twofold, as depicted in Table I: they
define the patterns used to produce the parser that virtualizes the native
model and instantiates virtual widgets, and define how each virtual widget is
mapped back to the native model, in this case, assigning several alternative
mappings to the same virtual widget. The virtual model is transformed back
into the native model (i.e. native model must be synthesized) in the following
circumstances:  1. instantiation of virtual widgets,  2. switching the pattern
of a virtual widget,  3. and changing the value of a virtual widget property
.

Definitions of virtual widgets contain a set of property definitions, which
are bound to the properties of native widgets using annotations in the native
widget patterns and equations in each pattern to relate them. In the case of
the virtual widget BooleanInput defined in Table I, the parameters are
Variable of type Expression and Label of type string. Equations in this
definition can be read in both ways – from the virtual widget to the native
widget and vice-versa. During the virtualization phase, the equation
$\texttt{\small Variable}=i.\texttt{\small Variable}$ in Pattern#1 means that
the value of the Variable property of the virtual widget is set with the value
of the Variable property of the native widget Checkbox identified by $i$.
During synthesis (which occurs when new virtual widget instances are created
or the developer changes the pattern of an existing virtual widget), the same
equation specifies that the value of the Variable property of the (newly
created) native widget Checkbox identified by $i$ is set with the value of the
Variable property of the virtual widget.

The equations provide the value for some of the properties of the synthesized
native widgets. The remaining properties are set if they have been specified
in the pattern, either as matching values or default values. For instance,
when instantiating Pattern#3 of BooleanInput, the Value for the first
ButtonGroupItem widget is set to true, and the Value of its Text widget is set
to Yes.

Additionally, all native widget properties are preserved when changing
patterns if there is a corresponding widget in the target pattern. For
instance, consider the virtual model 2 and changing the BooleanInput instance
with id v2 from Pattern#3 to Pattern#1. The widget with id $t$ in Pattern#3
corresponds to the native widget with id $t3$ (1). Pattern#1 also contains a
widget with id $t$. Consequently, the synthesized Text widget will have a non-
empty value for property Style even though the pattern provides no value for
the property. 3 displays the resulting native model.

Listing 3: Result of changing BooleanInput from Pattern#3 to Pattern#1
(snippet)

⬇

9 <Label Id="l2" Widget="bg">

10 <Text Id="t2" Style="bold" Value="Approved by Manager"/>

11 </Label>

12 <Checkbox Id="bg" Variable="Request.Approved"/>

Of course, this bidirectional reading capability limits the kind of equations
that can be used in the definition. At this point, we limit equations to
directly reading/setting properties of virtual widgets and native widgets.

##  VI Evaluation

We designed a performance benchmark with a set of large examples to test the
efficiency and effectiveness of our method. In this batch, we used the real
OutSystems metamodel (consisting of 30 native widget classes) augmented with
$31$ virtual widget definitions and $106$ patterns in total, which corresponds
to the totality of the gradually defined database of patterns at the time of
testing. We used this set of virtual widget definitions to further assess the
correctness of the parser generator process and also to sample the correctness
of the synthesis process that consisted of switching between patterns. We ran
a warmup process and repeated the experiments $9$ times for each module, to
drop the $2$ highest and the $2$ lowest values, thus reducing noise, and
obtaining the parsing time in isolation. As can be seen in Table III, the
generated parser is highly ambiguous.

TABLE III: Generated parser statistics for the OutSystems metamodel augmented with 31 virtual widgets Grammar rule count | 188
---|---
Parser state count | 926
Shift-reduce conflicts count | 216
Reduce-reduce conflicts count | 982

To assess the efficiency and effectiveness of our approach we designed a
simple experiment to use the virtual widget definitions in a large code base.
Our sample consists of $239$ OutSystems modules containing $3~{}718$ screens,
summing up a total of $198~{}072$ native widgets. Fig. 8 shows the
virtualization (parsing) time per number of native widgets in every module
using a double logarithmic scale, to allow depicting small and large
applications simultaneously. We found a clear linear trend
($t=0.0336*n-0.0277$) in the parsing time in milliseconds ($t$) with a
$33.6\mu s$ increase in parsing time for every new widget parsed ($n$). The
coefficient of determination of the linear regression ($R^{2}=0.611$), with
$\mathit{p{-}value}<0.001$, shows that there is a good fit, but there are
still several cases where the time is not linearly related to the number of
native widgets. The chart of Fig. 8 shows that about $14\%$ of cases are
slower than the trendline, which is visible by the existence of outliers
visible in the chart. In our raw data, we observe that the longest parsing
time for a module is about $92ms$, which is still within the range of
acceptable times for an interactive system, where $100ms$ is the reference
number for the time limit for a user to feel that they are manipulating
objects live in a user interface [14]. In most cases, the time is quite short,
and the reasons for the outliers are related to extreme cases of ambiguity
that triggers excessive backtracking in the parsing process. Most of the more
direct ambiguous cases are immediately dealt by the GLR parsing algorithm that
is set to select the longest sequence of native widgets.

Figure 8: Parsing time per number of native widgets (log-log)

As far as effectiveness is concerned, we observe, in Fig. 9, that the average
number of widgets that is abstracted ($v$) is even steadier with a linear
trend ($v=0.444*n+1.3$) with a high coefficient of determination
($R^{2}=0.977$) and $\mathit{p{-}value}<0.001$. The ratio is mostly constant
and close to $1{:}2$, which means that on average the number of widgets is
reduced to half in the abstract model with only 31 virtual widgets
definitions. It is expected that this ratio increases with the gradual
addition of new virtual widgets definitions.

As depicted in Table III, the parser that we generated for our benchmark is
highly ambiguous. The large number of reduce-reduce conflicts is due to the
overlap of virtual widget and native widget rules. However, the high degree of
ambiguity has a very low practical impact on the parser performance. The
statistics of Table IV back our claim. The parser processes a total of 307 884
tokens when running our full benchmark. In an ideal scenario where
backtracking never occurs, an equal amount of shift operations is expected,
i.e. each token is processed exactly once. As can be seen, the total number of
shift operations is higher (318 515), but not by a large margin - on average
the parser runs 1.035 shift operations per input token. Conflicts are
encountered at 7.95% of the tokens. Notice that a conflict corresponds to the
availability of multiple parser actions for the same lookahead token, which
our parser handles by prioritizing one of the rules and keeping track of the
remaining ones in case it needs to backtrack. Bactracking occurs at a lower
rate of 2.57%. A lower value is expected because not all conflicts lead to
backtracking. The impact of backtracking is low. A total of 10 631 of tokens
had to be backtracked, i.e. reprocessed. On average, backtracking results in
going back 1.341 tokens.

In summary, these results show that our gradual approach is suitable for a
live bidirectional transformation of models that allows simultaneous editing
of application models at different levels of abstraction without overriding or
losing any detail in the model visualization or synthesis.

Figure 9: Number of virtual widgets parsed per number of initial native widgets (log-log) TABLE IV: Benchmark parsing statistics Total input token count | 307 884
---|---
Shift operations count | 318 515
Total conflict count | 24 477
Backtracking operations count | 7 927
Total backtracked tokens | 10 631
Average shift operations per input token | 1.035
Conflict rate per input token | 7.95%
Backtracking rate per input token | 2.57%
Average backtracked tokens per backtracking operation | 1.341

##  VII Related Work

Bidirectional transformations have been applied in a variety of contexts [15].
For instance, in the database community there is an extensive body of work
regarding the view-update mechanism [16, 17, 18, 19]. Hence, there are
multiple scenarios where a focus on the efficiency of these transformations is
crucial.

In the context of Model-Driven Engineering (MDE) bidirectional transformations
play a critical role [6, 20] where it is the cornerstone to define flexible
Model-to-Model transformations (M2M). Guerra et al. [20] argue that M2M
transformations are usually expressed through specialised M2M transformation
languages and are mostly focused on the implementation phase. Their work [20]
addresses this issue by proposing a family of languages to cover the full
transformation development life cycle. Our approach can be seen as an instance
of the methodology proposed in [20] as we cover the whole lifecycle phases of
the transformation development in our tool, from the requirements to the
design and validation. By providing a back office and a metamodel to define
virtual widgets, we are enabling pattern designers to extend the
transformation, and by providing validations in this editor we are ensuring
that the produced transformation is correct every step of the way.

Comparing CHAMELEON with M2M approaches as EMF [21] or MPS [22, 23] the
disadvantage is that those approaches define transformations as external to
the language itself (cf. ATL [24, 25]). CHAMELEON uses the native metamodel,
extended with name binders and equations to express the patterns for
virtualization and synthesis.

Triple Graph Grammars (TGGs) [26, 27] are a rule-based approach proposed to
define transformations between graph-based languages while maintaining the
bidirectional relationships between input and output elements. TGGs are
particularly useful to synchronise different models and determine the
compatibility of source and target models, which in CHAMELEON is (mostly)
ensured by construction as the metamodel for virtual widgets subsumes the
metamodel for native virtual widgets. But a more critical issue with TGGs is
efficiency, as parsing algorithms for TGGs are complex and naive solutions may
lead to an exponential analysis [27]. Even by constraining TGG expressivity,
at best, dedicated parsers have polynomial complexity. In contrast, CHAMELEON
has a linear parsing algorithm, which is possible since it deals with abstract
syntax trees. In the low-code setting of CHAMELEON there are graph-based
structures similar to flow charts (action flows) that can nevertheless be
expressed as structured (tree-like code) and thus processed efficiently.

Viatra [28, 29] uses formal mathematical techniques of graph transformation
and abstract state machines. This framework can perform complex
transformations by using an incremental pattern matching approach that enables
the determination and updating of matches after modifications are made
incrementally. Nevertheless, the execution time of the transformations can be
significant for large models, hindering their use in interactive systems.

QVT [30, 31, 32] is a family of MDE languages that provide a standard for
(mainly) defining model transformations between different types of models. QVT
relations [30] supports complex object pattern matching and object template
creation with correspondences between domains are specified as relations. In
particular, QVT relational uses a strategy where it applies simultaneously all
matches of translation rules to a given input model and then merges the
resulting output model elements. However, this approach tends to be prone to
errors and demands a deep understanding of how the rules match and interact
with each other [33]. As a result, available QVT relational tools can yield
significantly different outcomes when processing the same input [7].

The works [34, 35] address concurrent model synchronization, where
transformations may be applied simultaneously to source and target models.
Currently CHAMELEON does not support this feature, but we are exploring how to
include concurrent model synchronization in our solution.

##  VIII Future Work

While CHAMELEON represents a promising approach to model-driven engineering,
it is important to note that it is not a fully general solution. Specifically,
CHAMELEON does not cover models that are intrinsically graph structures as
these scenarios do not typically arise in the OutSystems context.

One of the constraints we imposed in this work is that the model only uses
simple parser conditions on enumeration values. Although our implementation is
capable of handling general conditions, we found that this restriction can
lead to a combinatorial explosion of states in the parser, which hinders the
interactivity of the system. However, in practice, this restriction has shown
it is not a limitation in the definition of virtual widgets.

In the present proposal, one open issue that may influence the results is the
amount of backtracking that occurs during the parsing process. In the future,
we plan to deeply study the cases where backtracking is necessary and find
ways to avoid or optimize it.

We also identify possible extensions of this work to integrate it further. One
of the most important extensions is to allow the definition of virtual widgets
using prior developed template language OSTRICH [36, 37, 38]. The
visualization of the model using templates allows for greater reuse of code
and links this system with a database of curated patterns that already exist
in the platform. Also, the binding mechanism would benefit from using template
parameters instead of the direct binding of names to the model.

##  IX Conclusions

In this work, we studied the application of standard parsing techniques to
implement model abstraction and the definition of linked native patterns to
define a virtual widget. Virtual widgets, defined in a metamodel as an
extension of the native metamodel, lead to a simplified visualization of the
model in widget trees without discarding any part of the model.

By allowing the incremental definition of the correspondence between virtual
widgets with native widget patterns and name binders with equations, we
support a gradual approach to the virtualization of a low-code metamodel thus
raising even further the abstraction level of the native language.

The virtual metamodel we introduce is dynamic, produced from a set of virtual
widget definitions, and then instantiated in an efficient model parser. We
evaluated the resulting system according to efficiency and effectiveness
parameters using a significantly large benchmark of real (low) code. All in
all, the approach is shown suitable for collaborative and interactive editing
of the low-code at different abstraction levels simultaneously.

## References

  * [1] E. Visser, “WebDSL: A case study in domain-specific language engineering,” in _Generative and Transformational Techniques in Software Engineering (GTTSE 2007)_ , ser. Lecture Notes in Computer Science, R. Lammel, J. Saraiva, and J. Visser, Eds. Springer, 2008.
  * [2] OutSystems. (2019) Experience builder. [Online]. Available: https://www.outsystems.com/low-code-platform/experience-builder/
  * [3] ——. (2019) Workflow builder. [Online]. Available: https://www.outsystems.com/low-code-platform/workflow-builder/
  * [4] ——. (2019) Integration builder. [Online]. Available: https://www.outsystems.com/low-code-platform/integration-builder/
  * [5] J. Ramalho, H. Lourenço, and J. C. Seco, “From builders to editors: Bidirectional transformations of low-code models,” in _ACM/IEEE International Conference on Model Driven Engineering Languages and Systems Companion, MODELS 2021 Companion, Fukuoka, Japan, October 10-15, 2021_. IEEE, 2021, pp. 108–117. [Online]. Available: https://doi.org/10.1109/MODELS-C53483.2021.00022
  * [6] N. Kahani, M. Bagherzadeh, J. R. Cordy, J. Dingel, and D. Varró, “Survey and classification of model transformation tools,” _Softw. Syst. Model._ , vol. 18, no. 4, pp. 2361–2397, 2019.
  * [7] J. Greenyer and E. Kindler, “Comparing relational model transformation technologies: implementing query/view/transformation with triple graph grammars,” _Softw. Syst. Model._ , vol. 9, no. 1, pp. 21–46, 2010.
  * [8] T. J. Parr, R. Quong, and H. Dietz, “The use of predicates in LL (k) and LR (k) parser generators (technical summary),” Purdue University, Tech. Rep. 7-1-1993, 1993.
  * [9] T. J. Parr and R. W. Quong, “ANTLR: A predicated- _LL(k)_ parser generator,” _Softw. Pract. Exp._ , vol. 25, no. 7, pp. 789–810, 1995.
  * [10] M. Tomita, “An efficient augmented-context-free parsing algorithm,” _Comput. Linguistics_ , vol. 13, no. 1-2, pp. 31–46, 1987.
  * [11] OutSystems. (2022) What is citizen developer? [Online]. Available: https://www.outsystems.com/glossary/what-is-citizen-developer/
  * [12] ——. (2022) Low-code vs. traditional development: An architect’s perspective. [Online]. Available: https://www.outsystems.com/blog/posts/low-code-vs-traditional-development/
  * [13] D. E. Knuth, “On the translation of languages from left to right,” _Inf. Control._ , vol. 8, no. 6, pp. 607–639, 1965.
  * [14] S. K. Card, G. G. Robertson, and J. D. Mackinlay, “The information visualizer, an information workspace,” in _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , ser. CHI ’91. New York, NY, USA: Association for Computing Machinery, 1991, p. 181–186. [Online]. Available: https://doi.org/10.1145/108844.108874
  * [15] K. Czarnecki, J. N. Foster, Z. Hu, R. Lämmel, A. Schürr, and J. F. Terwilliger, “Bidirectional transformations: A cross-discipline perspective,” in _Theory and Practice of Model Transformations - 2nd International Conference, ICMT@TOOLS 2009, Zurich, Switzerland, June 29-30, 2009\. Proceedings_ , ser. Lecture Notes in Computer Science, R. F. Paige, Ed., vol. 5563. Springer, 2009, pp. 260–283. [Online]. Available: https://doi.org/10.1007/978-3-642-02408-5_19
  * [16] F. Bancilhon and N. Spyratos, “Update semantics of relational views,” _ACM Trans. Database Syst._ , vol. 6, no. 4, p. 557–575, dec 1981.
  * [17] Y. Masunaga, “A relational database view update translation mechanism,” in _Tenth International Conference on Very Large Data Bases, August 27-31, 1984, Singapore, Proceedings_ , U. Dayal, G. Schlageter, and L. H. Seng, Eds. Morgan Kaufmann, 1984, pp. 309–320. [Online]. Available: http://www.vldb.org/conf/1984/P309.PDF
  * [18] G. Gottlob, P. Paolini, and R. Zicari, “Properties and update semantics of consistent views,” _ACM Trans. Database Syst._ , vol. 13, no. 4, p. 486–524, oct 1988.
  * [19] A. Bohannon, B. C. Pierce, and J. A. Vaughan, “Relational lenses: a language for updatable views,” in _Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA_ , S. Vansummeren, Ed. ACM, 2006, pp. 338–347. [Online]. Available: https://doi.org/10.1145/1142351.1142399
  * [20] E. Guerra, J. de Lara, D. S. Kolovos, R. F. Paige, and O. M. dos Santos, “ _trans_ ml: A family of languages to model model transformations,” in _Model Driven Engineering Languages and Systems - 13th International Conference, MODELS 2010, Oslo, Norway, October 3-8, 2010, Proceedings, Part I_ , ser. Lecture Notes in Computer Science, D. C. Petriu, N. Rouquette, and Ø. Haugen, Eds., vol. 6394. Springer, 2010, pp. 106–120.
  * [21] D. Steinberg, F. Budinsky, M. Paternostro, and E. Merks, _EMF: Eclipse Modeling Framework_ , 2nd ed., ser. Eclipse Series. Upper Saddle River, NJ: Addison-Wesley, 2009.
  * [22] JetBrains, “Jetbrains meta programming system,” 2020, http://github.com/JetBrains/MPS. Last visited in 2022-05-11.
  * [23] V. Pech, A. Shatalin, and M. Voelter, “JetBrains MPS as a tool for extending Java,” in _Proceedings of the 2013 International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools, Stuttgart, Germany, September 11-13, 2013_. ACM, 2013, pp. 165–168. [Online]. Available: https://doi.org/10.1145/2500828.2500846
  * [24] F. Jouault, F. Allilaire, J. Bézivin, and I. Kurtev, “ATL: A model transformation tool,” _Sci. Comput. Program._ , vol. 72, no. 1-2, pp. 31–39, 2008. [Online]. Available: https://doi.org/10.1016/j.scico.2007.08.002
  * [25] “Atlas transformation language,” 2015, https://wiki.eclipse.org/ATL/User_Guide. Last visited in 2022-05-11.
  * [26] A. Schürr, “Specification of graph translators with triple graph grammars,” in _Graph-Theoretic Concepts in Computer Science, 20th International Workshop, WG ’94, Herrsching, Germany, June 16-18, 1994, Proceedings_ , ser. Lecture Notes in Computer Science, E. W. Mayr, G. Schmidt, and G. Tinhofer, Eds., vol. 903. Springer, 1994, pp. 151–163.
  * [27] A. Anjorin, E. Leblebici, and A. Schürr, “20 years of triple graph grammars: A roadmap for future research,” _Electron. Commun. Eur. Assoc. Softw. Sci. Technol._ , vol. 73, 2015.
  * [28] I. Ráth, G. Bergmann, A. Ökrös, and D. Varró, “Live model transformations driven by incremental pattern matching,” in _Theory and Practice of Model Transformations - 1st International Conference, ICMT@TOOLS 2008, Zurich, Switzerland, July 1-2, 2008, Proceedings_ , ser. Lecture Notes in Computer Science, A. Vallecillo, J. Gray, and A. Pierantonio, Eds., vol. 5063. Springer, 2008, pp. 107–121.
  * [29] D. Varró, G. Bergmann, Á. Hegedüs, Á. Horváth, I. Ráth, and Z. Ujhelyi, “Road to a reactive and incremental model transformation platform: three generations of the VIATRA framework,” _Softw. Syst. Model._ , vol. 15, no. 3, pp. 609–629, 2016.
  * [30] “Atlas transformation language,” 2016, https://www.omg.org/spec/QVT. Last visited in 2023-04-11.
  * [31] P. Stevens, “Bidirectional model transformations in QVT: semantic issues and open questions,” in _Model Driven Engineering Languages and Systems, 10th International Conference, MoDELS 2007, Nashville, USA, September 30 - October 5, 2007, Proceedings_ , ser. Lecture Notes in Computer Science, G. Engels, B. Opdyke, D. C. Schmidt, and F. Weil, Eds., vol. 4735. Springer, 2007, pp. 1–15.
  * [32] ——, “Bidirectional model transformations in QVT: semantic issues and open questions,” _Softw. Syst. Model._ , vol. 9, no. 1, pp. 7–20, 2010.
  * [33] F. Klar, “Efficient and compatible bidirectional formal language translators based on extended triple graph grammars,” Ph.D. dissertation, Technische Universität, Darmstadt, February 2012. [Online]. Available: http://tuprints.ulb.tu-darmstadt.de/2894/
  * [34] F. Hermann, H. Ehrig, C. Ermel, and F. Orejas, “Concurrent model synchronization with conflict resolution based on triple graph grammars,” in _Fundamental Approaches to Software Engineering - 15th International Conference, FASE 2012, Tallinn, Estonia, March 24 - April 1, 2012. Proceedings_ , ser. Lecture Notes in Computer Science, J. de Lara and A. Zisman, Eds., vol. 7212. Springer, 2012, pp. 178–193.
  * [35] Y. Xiong, H. Song, Z. Hu, and M. Takeichi, “Synchronizing concurrent model updates based on bidirectional transformation,” _Softw. Syst. Model._ , vol. 12, no. 1, pp. 89–104, 2013.
  * [36] H. Lourenço, C. Ferreira, and J. C. Seco, “OSTRICH - A type-safe template language for low-code development,” in _24th International Conference on Model Driven Engineering Languages and Systems, MODELS 2021, Fukuoka, Japan, October 10-15, 2021_. IEEE, 2021, pp. 216–226. [Online]. Available: https://doi.org/10.1109/MODELS50736.2021.00030
  * [37] J. C. Seco, H. Lourenço, J. Parreira, and C. Ferreira, “Nested OSTRICH: hatching compositions of low-code templates,” in _Proceedings of the 25th International Conference on Model Driven Engineering Languages and Systems, MODELS 2022, Montreal, Quebec, Canada, October 23-28, 2022_ , E. Syriani, H. A. Sahraoui, N. Bencomo, and M. Wimmer, Eds. ACM, 2022, pp. 210–220. [Online]. Available: https://doi.org/10.1145/3550355.3552442
  * [38] H. Lourenço, C. Ferreira, J. Costa Seco, and J. Parreira, “OSTRICH: a rich template language for low-code development (extended version),” _Software and Systems Modeling_ , vol. 72, no. 1-2, pp. 1–19, 2022.


# Document Navigability: A Need for Print-Impaired

Anukriti Kumar Tanuja Ganu Saikat Guha
Microsoft Research, India
{t-anukumar, tanuja.ganu, saikat<EMAIL_ADDRESS>
###### Abstract

Printed documents continue to be a challenge for blind, low-vision, and other
print-disabled (BLV) individuals. In this paper, we focus on the specific
problem of (in-)accessibility of internal references to citations, footnotes,
figures, tables and equations. While sighted users can flip to the referenced
content and flip back in seconds, linear audio narration that BLV individuals
rely on makes following these references extremely hard. We propose a vision
based technique to locate the referenced content and extract metadata needed
to (in subsequent work) inline a content summary into the audio narration. We
apply our technique to citations in scientific documents and find it works
well both on born-digital as well as scanned documents.

##  1 Introduction

Bookshare [3] and Sugamya Pustakalaya [9] are libraries of accessible content
used by blind, low-vision, and otherwise print-disabled (BLV) individuals.
Volunteers for the non-profit scan and digitize books requested by its
members. However, it currently takes volunteers close to one month to create
accessible books despite the availability of highly-accurate cloud-based OCR
services [5, 2]. This slow pace of making content accessible naturally results
in an acute lack of accessible content for BLV individuals. Our goal in this
paper is to design tools that empower volunteers to make content accessible an
order of magnitude faster.

Making OCR output _navigable_ is the primary time-consuming task volunteers
perform. This includes extracting chapter, heading and subheading structure,
necessary for directly navigating to sections of interest or to skip over
content. Automatically detecting heading levels is, in principle, easy using
heuristics on font size and weight. A significantly harder problem in making
content navigable is resolving internal references such as citations,
footnotes, and references to tables, images, and equations in a form that
screen-readers can make accessible to BLV individuals.

To illustrate the (in-)accessibility of internal references, consider the
following sentence from a research paper: “[52] presents a breakthrough
result”. A sighted reader can effortlessly flip to the references at the back,
look up reference [52], and continue reading within just a few seconds. This
effortless lookup is not possible using screen-readers that, in general, do
not have a notion of internal references. While internal hyperlinks can be
used to approximate the task of jumping to the references, and then navigating
back, the interaction disrupts the flow of reading. A better approach is to
replace the original sentence with: “XYZ presents a breakthrough result”.

In order to automatically replace internal references, one must be able to  i)
identify internal references in text,  ii) resolve them to the destination
content,  iii) construct a short readable representation, and  iv) replace the
original reference with the short representation in a grammatically correct
manner.  In this paper, we focus on solving the first two problems, that of
identifying and resolving internal references to citations, tables and
figures, and footnotes. In doing so, we discover the lack of tools and
datasets for training the necessary models.

Overall, this paper makes three contributions. First, we present our tool for
generating ground-truth data on internal references by analysing digital PDFs.
Second, we present a dataset for training computer vision models for internal
references by applying our tool to several thousand arXiv papers. And finally,
we train a vision model on this dataset and apply to a sampling of images of
scanned research papers to demonstrate viability of our approach.

##  2 Background and Related Work

PDF has established itself as the de facto standard for fixed-format document
exchange and publication but when it comes to reading these documents, a vast
majority (75.1 percent) of screen reader users believe that PDF documents are
extremely or moderately likely to cause severe accessibility concerns [11]. In
two earlier research studies, BLV users also reported inaccessible PDFs as a
huge barrier in understanding content within a document [30],[20] as assistive
technologies experience significant difficulty trying to interpret the
information when the PDF documents do not comply with accessibility standards.
Most PDF documents are intrinsically inaccessible, due to the combination of
visual layout information and semantic content.

The PDF Association has also created the Matterhorn Protocol [6], which
defines a precise list of 136 test requirements that PDF documents must meet
in order to be accessible. This contains detailed guidance for content authors
on how to add specifications to their documents and make them compatible with
assistive technologies [7]. Despite the existence of these thorough
guidelines, improving the accessibility of a PDF document remains a
challenging research problem due to a combination of limited tools, lack of
knowledge and the structure of PDF format itself. Although there are some
tools like PAC 3 [8], WebAIM’s WAVE [10] etc. which can identify the problems
related to accessibility, there are limited tools that can remediate the
issues identified. There are very few tools which are open-source and provide
a free version to the user. One of the most commonly used tools for
remediation is Adobe Acrobat Pro/DC but its accessibility toolkit is a part of
the paid version and hence, very few people have access to it.

Most research articles that are delivered today exist in PDF format, and a
recent study showed that only 2.4% of them are accessible to people with
disabilities [31]. Recent research has focused on addressing some important
aspects of paper accessibility, such as how screen readers should comprehend
and read mathematical equations [12, 16, 28, 29], generate figure captions
automatically [26, 13] and explain graphs and charts [23, 14, 15]. In the
recent work, a lot of traction is given upon improving accessibility of
various types of media content such as images [25, 18], videos [21] and
automatic classification of the content of figures [19]. Other work focused on
improving automatic text and layout detection in scanned documents [24] as
well as table content extraction [27, 17] within them. To date, not much work
has been done for introducing navigability within a document which enables
skimming and scanning [22], currently under-supported by PDF documents. Hence,
our work focuses on taking the first step towards automatically replacing the
internal references and hence, improving the reading experience of a wide
range of users.

##  3 Methodology

This section talks about the tool we created to generate ground-truth data on
internal references by analyzing digital PDFs. The process for building this
tool is divided into 3 phases: First, we segment the document into regions of
interest. Second, we identify explicit internal reference keys for these
regions. And finally, we infer implicit keys associated with references using
the hyperlink text. These three key elements are depicted in Fig. 2.

Regions. A research paper can be decomposed into the following elements:
headings, text blocks, figures, tables, lists and equations. For detecting
internal references within these elements, we need to first identify the
regions containing internal references and we pose this problem as an instance
segmentation task. We use a pre-trained model based on Mask R-CNN architecture
from Detectron2 model zoo to decompose a document into five categories: title,
text block, list, figure and table. The model is based on the ResNet50 feature
pyramid network (FPN) base config and is trained on the Publaynet dataset for
document layout analysis. Similarly, we use another instance segmentation
model of the same base config to detect equations but the only difference is
that it has been trained on MFD (Mathematical Formula Detection) dataset with
output layer modified to predict only one category: equation. The result
obtained from these models is depicted in Fig. 1.

Figure 1: Result from document segmentation model: A document page is
segmented into six categories: Text, Title, List, Table, Figure and
Equation.).

Explicit Keys. After extracting the regions of interest, our focus is to
extract explicit internal reference keys for each of these regions. This
involves identification of reference items, table captions, figure captions,
equation numbers and footnote markers. However, there is a dearth of tools and
data which makes it difficult to extract them directly. Hence, we use
different heuristics for extracting such elements. Since we already know
certain standardized keywords which mark the beginning of these elements, we
make use of OCR to extract text within the regions and hence, create
appropriate annotations for the internal references. These keywords are
extracted as explicit keys, used for resolving reference items later. For
instance, a table or figure is generally surrounded by its caption which can
be segmented as a text block from the document segmentation model. Now, doing
OCR on these text blocks and a simple keyword matching would give us the
appropriate caption. Similarly, superscript detection would provide us with
the footnote markers. Using the annotations obtained from this process, we
create a structured representation for all reference items with fields for
bounding box coordinates as well as text contained within them.

Figure 2: A document page decomposed into regions of interest (yellow box),
explicit keys (green box) and implicit keys (red box) for tables, figures,
references and footnotes.

Implicit Keys. Within a scientific document, there can be multiple hyperlinks
associated with the same internal reference. Since the objective of our work
is to create a dataset for resolving internal references with their
corresponding in-text citations and vice-versa, we need to obtain all
hyperlink texts which would act as implicit keys for internal references.
Firstly, we incorporate document’s metadata using a python module named fitz
[4] from an open source project PyMuPDF. This way we collect information
regarding the source location as well as the target point location for all
types of embedded links. For each target point location, we find the nearest
reference item from all the items extracted earlier. Also, we extract all
implicit keys by applying OCR at all hyperlink locations obtained from fitz.
Finally, a ground-truth dataset is created by combining source keys (implicit
and explicit keys) with the annotated reference bounding box and associated
text.

##  4 Experiments and Result

This section focuses on applying our tool to generate ground-truth annotated
data for bibliographic reference items present in scientific documents.
Further, we would also demonstrate the viability of our approach by training a
vision model on this data for bibliographic reference item detection and
applying it to both born-digital as well as scanned documents. The entire
pipeline is described in the following sub-sections.

###  4.1 Data

The first step is to construct a dataset of research papers by sampling PDFs
published in the years of 2016-2021 from arXiv dataset published on Kaggle
[1], stratified across subjects ranging from physics, computer science,
mathematics, physics, statistics, quantitative biology, economics and others.
We sampled papers from each field of study, with Physics on the minimum end
and Economics and Computer Science on the maximum end. The resulting dataset
consisted of around 22,081 papers. It is used for generating ground-truth
labels for bibliographic reference items and also, for training the vision
model to detect bibliographic reference items.

###  4.2 Ground-Truth Labels

This section talks about generating ground-truth labels for bibliographic
reference items by applying our tool to research paper dataset as mentioned in
section 4.1.

To identify the regions of interest for bibliographic references, we utilized
the document segmentation model as described in section 3 to detect two
classes of elements - Title and List blocks within a research paper. Then, we
extracted text within the title blocks using OCR to check for references
section. Further, a keyword search based heuristic is used to identify phrases
that are likely to appear as a title for the references section. Once we
detected the section, we segmented out list blocks within it and this way, we
extracted 88,786 list images containing references.

Next, we segmented reference items out of the list images by exploiting some
natural properties of reference items, such as the use of certain characters
that are used to mark the beginning of a reference item. We have also assumed
that they are written in a consistent manner as is required by most academic
venues. But since these items can span through multiple lines, the detection
becomes difficult. Hence, we used a heuristics based approach based on
identifying these start characters from references using OCR and further,
labeling the region between them as a reference item. Further, these start
characters are extracted as an explicit key for the reference.

To extract implicit keys, we obtained embedded links information using fitz
module. Then, we filtered out only those in-text hyperlinks which were
pointing to pages beyond reference section. For each hyperlink, we detected
its corresponding reference item by finding an annotated bounding box nearest
to hyperlink’s target point location. Also, we obtained implicit keys by
extracting hyperlink text from all the locations pointing to a bibliographic
reference. Finally, we combined all these key elements to generate annotated
ground-truth data for bibliographic reference items.

###  4.3 Model

To generalize the process of detecting all types of references and linking
them back to their in-text citations, we trained a vision based model for
extraction of bibliographic reference items along with their source keys. We
used the base config from the Faster-RCNN model present in the model zoo of
the Detectron2 library. It is pre-trained on COCO dataset for object detection
task and is based on the ResNet101 feature pyramid network (FPN) base config.
This backbone network is used to extract features from an image followed by a
Region Proposal Network for proposing region proposals and a box head for
tightening the bounding box. To train this model on our dataset, we first
divided our ground-truth dataset into two parts as train and validation set
with 0.85 as the split ratio. Out of 88,786 list images data and their
annotations, 75,468 were used for training and the remaining 13,318 were
utilized for evaluation purposes. The model was trained for 20k iterations.

Model | AP |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| APm | APl
---|---|---|---|---|---
Reference segmentation | 81.70 | 86.98 | 84.47 | 74.68 | 84.72
Table 1: Average precision values at different IoU thresholds

###  4.4 Results

We inferred the results by testing our model on validation dataset using hold-
out cross validation technique. Usually, object detection models are evaluated
following the COCO standards of evaluation. Hence, mAP (mean average
precision) is an important metric considered for evaluating the performance of
the model. The average precision values at different IoU thresholds are
present in Table 1.

Figure 3: Output for research paper image from born-digital PDF  Figure 4:
Output for scanned research paper image

We also validated our approach by applying it in two different settings - 1)
images from born-digital PDFs and 2) images from a flatbed scanner. The output
is shown in Fig. 3 and Fig. 4 respectively. In both cases, we were able to
extract reference items and their source keys successfully. This depicts the
viability of our approach and hence, it can be used to identify and resolve
other types of internal references as well.

##  5 Discussion

From Fig. 3 and Fig. 4, we observe that the performance of our model is
significantly better on images from born-digital PDF than a real-world scanned
image. Hence, one of the future directions is to make our model more robust to
data distribution shifts through data augmentation.

For some research paper images, we also observed false negatives for reference
items continuing from the previous page. We plan to handle this case by adding
more data annotations of this type in future.

Also, we found that exploiting some natural properties of reference items,
such as the use of certain keywords in the beginning of a reference item,
makes heuristic approaches very effective for our task. However, in future, we
plan to use a considerably expanded set of keywords to make our approach
effective against more kinds of papers.

##  6 Conclusion

In this paper we presented our ongoing work in making published documents
accessible to blind, low-vision, and print-disabled individuals. We
specifically focused on the problem of poor accessibility of internal
references like citations, footnotes, table and figure references. We
presented a vision based technique to extract metadata needed to make these
internal references accessible. We successfully applied our technique to
extract requisite metadata from the bibliography section. We continue to work
on summarizing the referenced content and inlining into the audio narration to
make internal references fully accessible to print-impaired individuals.

## References

  * [1] aarxiv dataset from kaggle.  https://www.kaggle.com/datasets/Cornell-University/arxiv.
  * [2] Azure cognitive servicess.  https://docs.microsoft.com/en-us/azure/cognitive-services/computer-vision/overview-ocr.
  * [3] Bookshare.  https://www.bookshare.org/cms/.
  * [4] Fitz module.  https://pymupdf.readthedocs.io/en/latest/module.html.  Fitz module.
  * [5] Google cloud vision api.  https://cloud.google.com/vision/docs/ocr.
  * [6] The matterhorn protocol.  https://www.pdfa.org/resource/the-matterhorn-protocol/.
  * [7] Pdf/ua-1 standards for accessibility.  https://www.loc.gov/preservation/digital/formats/fdd/fdd000350.shtml.
  * [8] Pdf/ua foundation.  https://pdfua.foundation/en/pdf-accessibility-checker-pac.
  * [9] Sugamya pustakalaya.  https://library.daisyindia.org/NALP/welcomeLink.action.
  * [10] Wave web accessibility evaluation tool.  https://wave.webaim.org/.
  * [11] Webaim: Screen reader user survey #8 results.  https://webaim.org/projects/screenreadersurvey8/.
  * [12] Dragan Ahmetovic, Tiziana Armano, Cristian Bernareggi, Doubrov, Anna Capietto, Sandro Coriasco, Kozlovskiy, and Nadir Murru.  Axessibility 2.0: creating tagged pdf documents with accessible formulae.  2019\.
  * [13] Charles Chen, Ruiyi Zhang, Sungchul Kim, Scott Cohen, Tong Yu, Ryan Rossi, and Razvan Bunescu.  Neural caption generation over figures.  In Adjunct Proceedings of the 2019 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2019 ACM International Symposium on Wearable Computers, UbiComp/ISWC ’19 Adjunct, page 482–485, New York, NY, USA, 2019. Association for Computing Machinery.
  * [14] Stephanie Elzer, Edward Schwartz, Sandra Carberry, Daniel L. Chester, Seniz Demir, and Peng Wu.  Accessible bar charts for visually impaired users.  2008\.
  * [15] Christin Engel.  Towards accessible charts for blind and partially sighted people.  02 2019.
  * [16] Silvia Fajardo-Flores, Maria Andrade-Arechiga, Alfonso Flores-Barriga, and Juan Lazaro-Flores.  Mathml to ascii-braille and hierarchical tree converter.  volume 6180, pages 396–402, 07 2010.
  * [17] Miao Fan and Doo Soon Kim.  Table region detection on large-scale PDF files without labeled data.  CoRR, abs/1506.08891, 2015.
  * [18] Cole Gleason, Amy Pavel, Emma McCamey, Christina Low, Patrick Carrington, Kris M. Kitani, and Jeffrey P. Bigham.  Twitter A11y: A Browser Extension to Make Twitter Images Accessible, page 1–12.  Association for Computing Machinery, New York, NY, USA, 2020.
  * [19] Edward Kim and Kathleen F. McCoy.  Multimodal deep learning using images and text for information graphic classification.  In Proceedings of the 20th International ACM SIGACCESS Conference on Computers and Accessibility, ASSETS ’18, page 143–148, New York, NY, USA, 2018. Association for Computing Machinery.
  * [20] Jonathan Lazar, Aaron Allen, Jason Kleinman, and Chris Malarkey.  What frustrates screen reader users on the web: A study of 100 blind users.  International Journal of Human–Computer Interaction, 22(3):247–269, 2007.
  * [21] Xingyu Liu, Patrick Carrington, Xiang ’Anthony’ Chen, and Amy Pavel.  What makes videos accessible to blind and visually impaired people?  In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems, CHI ’21, New York, NY, USA, 2021. Association for Computing Machinery.
  * [22] Martha J. Maxwell.  Skimming and scanning improvement: The needs, assumptions and knowledge base.  Journal of Literacy Research, 5:47 – 59, 1972.
  * [23] Silvia Mirri, Silvio Peroni, Paola Salomoni, Fabio Vitali, and Vincenzo Rubano.  Towards accessible graphs in html-based scientific articles.  2017 14th IEEE Annual Consumer Communications & Networking Conference (CCNC), pages 1067–1072, 2017.
  * [24] Azadeh Nazemi.  Practical segmentation methods for logical and geometric layout analysis to improve scanned pdf accessibility to vision impaired.  International Journal of Signal Processing, Image Processing and Pattern Recognition, 7, 08 2014.
  * [25] Ab Shaqoor Nengroo and K. S. Kuppusamy.  Accessible images (aims): A model to build self-describing images for assisting screen reader users.  Univers. Access Inf. Soc., 17(3):607–619, aug 2018.
  * [26] Xin Qian, Eunyee Koh, Fan Du, Sungchul Kim, and Joel Chan.  A formative study on designing accurate and natural figure captioning systems.  In Extended Abstracts of the 2020 CHI Conference on Human Factors in Computing Systems, CHI EA ’20, page 1–8, New York, NY, USA, 2020\. Association for Computing Machinery.
  * [27] Roya Rastan, Hye-young Paik, and John Shepherd.  Texus: A unified framework for extracting and understanding tables in pdf documents.  Information Processing and Management, 56:895–918, 05 2019.
  * [28] Petr Sojka, Michael Ruzicka, Maro _vs_. Kucbel, and Martin Jarmar.  Accessibility issues in digital mathematical libraries.  2013\.
  * [29] Volker Sorge, Charles Chen, T. V. Raman, and David Tseng.  Towards making mathematics a first class citizen in general screen readers.  In Proceedings of the 11th Web for All Conference, W4A ’14, New York, NY, USA, 2014. Association for Computing Machinery.
  * [30] Shannon M. Tomlinson.  Perceptions of accessibility and usability by blind or visually impaired persons: A pilot study.  In Proceedings of the 79th ASIS&T Annual Meeting: Creating Knowledge, Enhancing Lives through Information & Technology, ASIST ’16, USA, 2016. American Society for Information Science.
  * [31] Lucy Lu Wang, Isabel Cachola, Jonathan Bragg, Evie Yu-Yen Cheng, Chelsea Haupt, Matt Latzke, Bailey Kuehl, Madeleine van Zuylen, Linda Wagner, and Daniel S. Weld.  Improving the accessibility of scientific documents: Current state, user needs, and a system solution to enhance scientific PDF accessibility for blind and low vision users.  CoRR, abs/2105.00076, 2021.