A Shallow Algorithm for Correcting Nesting Errors and Other Well-Formedness Violations in XML-like Input

3.1 Missing Root Element

The last type of error (missing root) can only be fixed if the user specified the qualified name to use when a root element must be created (document in the example given above). If none is given and this type of error is detected, the algorithm gives up and declares the document as irreparable.

3.2 Widowed Start Tags

There are two options to process widowed start tags whose corresponding end tag is missing:

1. Either the missing end tag is created and inserted at a suitable position, e.g. immediately before the end tag of the embedding element.
2. Or the widowed tag is converted into an empty tag (this is equivalent to inserting a corresponding end tag immediately after the widowed tag).

Error                    First Option             Second Option
<paragraph>             <paragraph>             <paragraph>
<sentence>                <sentence>              <sentence/>
...                         ...                     ...
                          </sentence>
</paragraph>            </paragraph>            </paragraph>

To determine which option to use, a set of emptiable tags for which the second option should be used can be specified. The first option is used for widowed tags of all other types; in this case the missing end tag is inserted at the latest possible position (immediately before the embedding end tag).

3.3 Placement of Missing Start Tags

A simple heuristic for the placement of missing start tags is to place them immediately after the start tag of the embedding element (analogously to missing end tags). However if an element contains several widowed end tags of the same type (qualified name), the created start tags appear consecutively, resulting in a potentially deep nesting of same-type elements.

This might be appropriate in some cases, but more often same-type elements are arranged in succession within a common embedding element instead of being nested. Thus our heuristic is to place the first missing start tag of a type after the start tag of the embedding element, but to place any further start tags of the same type after the last end tag of this type.

Error                    Simple Heuristic         Our Heuristic
<paragraph>             <paragraph>             <paragraph>
                          <sentence>              <sentence>
                            <sentence>
...                           ...                   ...
</sentence>                 </sentence>           </sentence>
                                                  <sentence>
...                         ...                     ...
</sentence>               </sentence>             </sentence>
</paragraph>            </paragraph>            </paragraph>

To realize this we use the concept of tentative start tags. A tentative start tag is created after an end tag whose start tag was either missing or itself tentative if the next tag of the same type is also an end tag (which means that another start tag is missing).

3.4 Configuration of Character-level Errors

For some kinds of character-level errors there are different possibilities of resolving them depending on user preferences. This is discussed in Section 4.2.

4.1 First Pass

In the first pass, the XML-like input is tokenized into a sequence of constituents. XML documents can contain ten types of constituents:

1. XML declaration
2. Document type declaration
3. Processing instructions (PIs)
4. Start tags
5. End tags
6. Empty tags
7. Outer whitespace, i.e. whitespace preceding or following a tag or other markup
8. Textual content
9. CDATA sections
10. Comments

If there is text that doesn't fit any constituent type, the algorithm tries to fix this error at the character level, as described in Section 4.2. Tokenization is done via complex regular expressions, similar to the shallow XML parser described in [Cam98].

Constituents are either markup (declarations, PIs, tags, comments) or text (textual content, CDATA sections). Each markup constituent is assigned a markup series number—a markup series is a series of markup and outer whitespace not interrupted by non-whitespace text. The concept of markup series is used to distinguish between simple and hard nesting errors. Simple nesting errors can be resolved by moving tags within the same markup series.

In addition to a (doubly linked) list of all constituents, a data structure containing all unprocessed tags is built which initially contains all start and end tags (but no empty tags).

4.2 Repairs at the Character Level

These repairs are performed prior to the the detection of nesting errors to allow a correct tokenization.

1. Escape illegal ampersands: Any "&" characters occurring in textual content or attribute values (of start and empty tags) that do not start an entity reference or a decimal or hexadecimal character reference are escaped. The algorithm does not use a DTD, so it doesn't know whether or not entity references such as — are declared and thus legal. By default all possible entity references are accepted but the algorithm can also be configured to allow only character references and the five predefined entity references (& < > ' "), while any other "&" characters are escaped even if starting a potential entity reference.
2. Fix unquoted attribute values: Attribute values whose start and/or end quotes are missing (name=value) or do not match each other (name="value') are recognized and fixed (by enclosing them in full quotes and escaping any full quotes within the value). Unquoted values can contain any characters except "<", ">" and "=", they can even contain whitespace.
3. Optionally delete "pseudo-tags": We use the term "pseudo-tag" for character sequences that look similar to XML tags but are none. More formally, "pseudo-tags" start with a "<" character followed by any printable character, end with a ">" character, do not contain any embedded "<" or ">" and are not valid tags according to the XML 1.0 [XML1.0] or 1.1 [XML1.1] Specification. For example, <0.05.12.91> would be a "pseudo-tag". Optionally (off by default) "pseudo-tags" are deleted. Otherwise they are processed in the next step, i.e. the starting "<" character is escaped.
4. Escape illegal characters: Any remaining illegal characters (typically un-escaped "<" characters) are escaped.
5. Optionally delete restricted control characters: Optionally restricted characters (control characters in the ranges [#x1-#x8#xB-#xC#xE-#x1F]) are deleted. These characters are prohibited in XML 1.0 and discouraged in XML 1.1. This step is configurable and off by default.

4.3 Second Pass

A start tag is said to have a corresponding end tag if and only if the unprocessed tags data structure contains an end tag of the same type (qualified name), not preceded by a start tag of the same type.

A start tag is said to be missing its end tag iff the next unprocessed appearance is not an end tag and the number of unprocessed start tags of this type is equal to or greater than the number of unprocessed end tags of this type.

The second pass traverses the list of constituents created in the first pass. Each encountered start tag is moved from unprocessed tags to a stack of open tags. When an end tag is encountered, the algorithm iterates the following loop until the end tag has been processed (a match has been found):

1. Check match: If the end tag and the last open tag have the same qualified name, they match each other. The start tag is popped from open tags. When the matching start tag is a tentative tag and the next tag of this type is another end tag, we create a new tentative start tag of the same type and insert it after the matched end tag. Exit loop (done).
2. Move tentative tag: If the last open tag is tentative, it is moved after the current end tag (removing it from open tags and re-adding it to unprocessed tags). Go to step 1 (try to match preceding open tag).
3. Find matching end tag: If a corresponding end tag exists for the last open tag within the current markup series, it is moved before the current end tag. This is done only if a non-tentative start tag exists for the current end tag, otherwise we'll go to the next step (move or insert start tag for current end tag) to avoid unnecessary tag movements. Start tag and matching end tag are popped from open tags resp. unprocessed tags. Go to step 1 (try to match preceding open tag).
   This step fixes a simple nesting error.
4. Find matching start tag: If open tags contains a non-root tag matching the current end tag (either within the markup series of the last open tag or a tentative appearance anywhere), it is moved after the last open tag. The found start tag is popped from open tags. Exit loop (done).
   This step fixes a widowed tag (if the found tag is tentative) or a simple nesting error (otherwise).
5. Insert missing start tag: If open tags does not contain a start tag with the same type (qualified name) as the current end tag, we know that the start tag is missing and needs to be supplied. Thus a start tag of the same type (and without any attributes) is created and inserted after the last open tag.
   If the next appearance of this type is also an end tag, another start tag is missing—to provide it we create a tentative start tag and insert it after the processed end tag. Exit loop (done).
   This step fixes a widowed tag.
6. Move premature start tag: If the last open tag is within the current markup series and not missing its end tag, it is moved after the current end tag (moving it from open tags to unprocessed tags). Go to step 1.
   This step fixes a simple nesting error.
7. Complete start tag: If the last open tag is missing its end tag, it is convert into an empty tag (preserving any attributes) if it is emptiable; otherwise a matching (same-type) end tag is created and inserted before the current end tag. Pop start tag from open tags and go to step 1.
   This step fixes a widowed tag.
8. Split element: If none of the above conditions triggers, we know that the last open tag and the current end tag overlap. The only way to fix this is by splitting either of them in two parts. In the current implementation it is always the start tag (the last open tag) that is split. We split the last open tag by creating two new tags: (1) a matching (same-type) end tag that is inserted before the current end tag; (2) a copy of the start tag (including all attributes) that is inserted after the current end tag. Pop start tag from open tags and go to step 1.
   This step fixes a hard nesting error.

At the end of the document, end tags are created and added for remaining open tags, if any. They are inserted after the last root content (content that is only allowed within a single root element: tags, text except outer whitespace, CDATA sections), but before any trailing non-root content (outer whitespace, comments, PIs). This fixes widowed tags.

If the root element is missing, i.e. not all root content is enclosed within a single element and this cannot be fixed by moving tags within markup series, an root element of the configured type can be created. If the algorithm is not configured to create a root element (default), processing will stop with an exception in this case. The inserted root element will cover as little content as possible, i.e. all root content, but no preceding or following non-root content. This fixes a missing root element.

4.4 Serialization

After the two passes, any well-formedness violations that can be detected by our algorithm have been fixed. The repaired list of constituents is serialized into a document that in most cases will be well-formed XML (unless it contains errors that are not addressed by our algorithm, e.g. duplicate attributes).