Balisage Paper: Flattening and unflattening XML markup: a Zen garden of XSLT and other tools

Basic sample

A sample of the basic input format in its original form is:

<p> 
    <cit> 
        <quote> 
            <lg> 
                <l> Like one who, on a lonely road, </l>
                <l> Doth walk in fear and dread, </l>
                <l> And, having once turn’d round, walks on, </l>
                <l> And turns no more his head; </l>
                <l> Because he knows a frightful fiend </l>            
                <l> Doth close behind him tread*. </l>
            </lg>
        </quote>
        <note> * 
        <bibl> 
            Coleridge’s “Ancient Mariner.” 
        </bibl>
        </note>
    </cit>
</p>

Flattening

To test the method on our Simplified sample data, we first flatten the original XML with the following XSLT, which converts all tags except the root (which must be preserved as a container element to ensure that the XML is well formed) to Trojan milestones. We modify the Trojan milestone markup method described in DeRose 2004 by putting the @sID and @eID attributes in a namespace, for which we bind the prefix th: to the URI http://www.blackmesatech.com/2017/nss/trojan-horse (following Sperberg-McQueen 2018). The original generic identifier is retained, the start-tag is replaced by an empty element that adds a @th:sID attribute with a generated value, and the end-tag is replaced by an empty element that adds a th:eID attribute with the same generated value:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:th="http://www.blackmesatech.com/2017/nss/trojan-horse"
    xmlns:math="http://www.w3.org/2005/xpath-functions/math"
    exclude-result-prefixes="#all"
    version="3.0">
    <xsl:output method="xml" indent="no"/>
    <xsl:template match="/*">
        <xsl:copy>
          <xsl:namespace name="th"
            select="'http://www.blackmesatech.com/2017/nss/trojan-horse'"/>
            <xsl:apply-templates/>
        </xsl:copy>
    </xsl:template>
    <xsl:template match="*">
        <xsl:element name="{name()}">
            <xsl:copy-of select="@*"/>
            <xsl:attribute name="th:sID" select="generate-id()"/>
        </xsl:element>
        <xsl:apply-templates/>
        <xsl:element name="{name()}">
            <xsl:attribute name="th:eID" select="generate-id()"/>
        </xsl:element>
    </xsl:template>
</xsl:stylesheet>

The flattened version looks roughly like the following (line breaks have been added within tags here, to shorten the lines:

<?xml version="1.0" encoding="UTF-8"?><p 
        xmlns:th="http://www.blackmesatech.com/2017/nss/trojan-horse"> 
    <cit th:sID="d1e3"/> 
        <quote th:sID="d1e5"/> 
            <lg th:sID="d1e7"/> 
                <l th:sID="d1e9"
	        /> Like one who, on a lonely road, <l th:eID="d1e9"/>
                <l th:sID="d1e12"
		/> Doth walk in fear and dread, <l th:eID="d1e12"/>
                <l th:sID="d1e15"
		/> And, having once turn’d round, walks on, <l th:eID="d1e15"/>
                <l th:sID="d1e18"
		/> And turns no more his head; <l th:eID="d1e18"/>
                <l th:sID="d1e21"
		/> Because he knows a frightful fiend <l th:eID="d1e21"/>            
                <l th:sID="d1e25"
		/> Doth close behind him tread*. <l th:eID="d1e25"/>
            <lg th:eID="d1e7"/>
        <quote th:eID="d1e5"/>
        <note th:sID="d1e30"/> * 
        <bibl th:sID="d1e32"/> 
            Coleridge’s “Ancient Mariner.” 
        <bibl th:eID="d1e32"/>
        <note th:eID="d1e30"/>
    <cit th:eID="d1e3"/>
</p>

The output of raising must match the original XML.

Extended basic sample

The basic sample contains no non-Trojan empty elements and no non-Trojan attributes. We can test whether those features are handled properly with the following slightly more complicated sample:

<?xml version="1.0" encoding="UTF-8"?><p
    xmlns:th="http://www.blackmesatech.com/2017/nss/trojan-horse"> 
  <cit xml:id="fThomas_C10-cit_1" th:sID="d1e3"/> 
  <quote xml:id="fThomas_C10-quote_1" th:sID="d1e5"/> 
  <lg xml:id="fThomas_C10-lg_1" th:sID="d1e7"/> 
  <l xml:id="fThomas_C10-l_1" th:sID="d1e9"
  /> Like one who, on a lonely road, <l th:eID="d1e9"/>
  <l xml:id="fThomas_C10-l_2" th:sID="d1e12"
  /> Doth walk in fear and dread, <l th:eID="d1e12"/>
  <l xml:id="fThomas_C10-l_3" th:sID="d1e15"
  /> And, having once turn’d round, walks on, <l th:eID="d1e15"/>
  <l xml:id="fThomas_C10-l_4" th:sID="d1e18"
  /> And turns no more his head; <l th:eID="d1e18"/>
  <l xml:id="fThomas_C10-l_5" th:sID="d1e21"
  /> Because he knows a frightful fiend <l th:eID="d1e21"/>            
  <l xml:id="fThomas_C10-l_6" th:sID="d1e25"
  /> Doth close behind him tread*. <l th:eID="d1e25"/>
  <lg th:eID="d1e7"/>
  <quote th:eID="d1e5"/>
  <note xml:id="fThomas_C10-note_1" th:sID="d1e30"/> * 
  <bibl xml:id="fThomas_C10-bibl_1">
    Coleridge’s “Ancient Mariner.” 
  </bibl>
  <note th:eID="d1e30"/>
  <cit th:eID="d1e3"/>
</p>

The extended basic sample adds the following features:

Overlapping markers

To test the behavior of the methods with input that cannot be fully raised without creating overlap, we use the following sample (some whitespace added for legibility):

<!--* Example adapted from LMNL sawtooth syntax
    * at http://piez.org/wendell/LMNL/lmnl-page.html
    *-->
<excerpt xmlns:th="http://www.blackmesatech.com/2017/nss/trojan-horse">
    <source th:sID="source"/>The Housekeeper<source th:eID="source"/>
    <author th:sID="author"/>Robert Frost<author th:eID="author"/>
    <s th:sID="s1"/>
    <l th:sID="L144" n="144"/>
    He manages to keep the upper hand
    <l th:eID="L144"/>
    <l n="145" th:sID="L145"/>
    On his own farm.
    <s th:eID="s1"/>
    <s th:sID="s2"/>
    He's boss.
    <s th:eID="s2"/>
    <s th:sID="s3"/>
    But as to hens:
    <l th:eID="L145"/>
    <l n="146" th:sID="L146"/>
    We fence our flowers in and the hens range.
    <l th:eID="L146"/>
    <s th:eID="s3"/>
</excerpt>

This consists of a few lines of verse, marked up with both the metrical structure (verse lines) and the division into sentences; both the first and third sentences span verse boundaries.

Frankenstein markers

The Frankenstein Variorum encoding represents an overlapping virtual hierarchy, so we need a way of distinguishing one set of elements participating in one hierarchy from the other set. The virtual elements participating in the first hierarchy hold trojan markers with attributes in the form of @th:sID and @th:eID. The second hierarchy is signalled with an alternative marker style used only on the <seg> elements. Here there is an @xml:id bearing a flag indicating the start or end position of a variant passage. These markers cannot be raised in exactly the way they were placed, since in some cases a variant passage may start inside a paragraph or chapter, and end in the next one. In this project, the decision to raise the <seg> elements necessitates a process of splitting them into pieces within structural boundaries, so that the original virtual element becomes two elements, with part one inside one structural unit and part two inside the next. Different styles of markers here facilitates handling these elements at different moments in the raising process.

Order of raising the elements

Figure 11 through Figure 20 illustrate some stages in the process of raising the virtual elements in the sample document by progressing through the flat sequence of siblings which makes up most of the input.

Figure 11

Illustration of left-right handling of input by a recursive-descent parser or by the left-right method described in the text. Initial state.

The input is shown arrayed along the bottom of the diagram: ovals filled with gray denote start- and end-markers, rectangles denote text nodes. The gray ovals above denote the logical hierarchy which is to be constructed (visible to human observers even if not visible to the software).

Figure 12

The first input node is read and recognized as the start-marker for the p element. Both the start-marker and the element node constructed are shown in red, as is the arc connecting them.

Figure 13

The second input node is read and recognized as the start-marker for the citation element cit.

The start-marker for the enclosing p element has served its purpose and is omitted from the diagram. The node for the p element is still incomplete, as indicated by its pink background.

Figure 14

The third input node is read and recognized as the start-marker for the citation element cit.

Between Figure 14 and Figure 15, we elide several stages. Figure 15 through Figure 17 illustrate the complete recognition of the second line of verse.

Figure 15

The eighth input node is read and recognized as the start-marker for the second line of verse.

The first line of verse is now complete and its node is now shown with black oval and white background instead of pink.

Figure 16

The ninth input node is the text for the second line of verse.

Figure 17

End-marker for second line of verse.

Figure 18 through Figure 20 illustrate the recognition of the last two end-markers and the final state of processing.

Figure 18

End-marker for cit element.

Figure 19

End-marker for paragraph.

Figure 20

Final state: all markers are gone, and all elements have been raised.

Outline of XSLT code

As described above, the right-sibling traversal idiom in XSLT proceeds one element at a time along the following-sibling axis. In the general case, each template for a content element calls <xsl:apply-templates> not on all its children but only on its first child. Every template (for content elements, marker elements, text nodes, comments, or processing instructions) concludes with a call to <xsl:apply-templates select="following-sibling::node()[1]"/>, thus passing control to the template for its immediate right sibling. In the flattening case, the outermost element of the document may be the only content element and its template the only one that applies templates to its children.

For our simple test cases, processing begins with the template for the outermost element.^[6]

<xsl:template match="*[*]">
    <xsl:copy copy-namespaces="no">
      <xsl:copy-of select="@*"/>
      <xsl:apply-templates mode="raising"
                           select="child::node()[1]"/>
    </xsl:copy>    
  </xsl:template>

The template for start-markers constructs a content element for the corresponding virtual element; it has the following structure:

<xsl:template match="*[@th:sID]" mode="raising">
    
    <!--* 1: handle this element *-->
    <xsl:copy>
      <xsl:copy-of select="@* except @th:sID"/>
      <xsl:apply-templates select="following-sibling::node()[1]"
                   mode="raising">
      </xsl:apply-templates>
    </xsl:copy>
      
    <!--* 2: continue after this element *-->
    <xsl:apply-templates select="following-sibling::*
                         [@th:eID = $sID 
                         and namespace-uri()=$ns
                         and local-name()=$ln]
                         /following-sibling::node()[1]"
                 mode="raising"/>

</xsl:template>

Note that there are two calls to <xsl:apply-templates>. The first call to <xsl:apply-templates> occurs within an <xsl:copy> element (which constructs an element with the name and attributes given by the start-marker); it selects the immediately following sibling node, which will in the normal run of things become the first child node of the new content element. The second call to <xsl:apply-templates> occurs after the new content element and it does not select the start-marker’s immediately following sibling, but instead selects the node immediately to the right of the end-marker.

Each child of the virtual element copies itself into the content element being created. The templates for text() nodes, comments, processing instructions, and any content elements present in the input all have essentially the same structure:

<xsl:template match="text() | comment() | processing-instruction | *[not(@th:*)]"
        mode="raising">
    <xsl:copy-of select="."/>
    <xsl:apply-templates 
        select="following-sibling::node()[1]"
        mode="raising"/>
</xsl:template>

If content elements can contain further markers at other levels of the tree, the <xsl:copy-of> should be replaced by a shallow copy and a recursive <xsl:apply-templates select="child::node()[1]>. That is not the case with our test data.

When an end-marker is encountered, the contents of the virtual element whose end it marks have now all been accumulated, and the right-sibling traversal of the input should stop. The template for end-markers will thus look like this:

<xsl:template match="*[@th:eID]" mode="raising">
        
    <!--* No action necessary *-->
    <!--* We do NOT recur to our right.
        * We leave it to our parent to do that.
        *-->      
    
</xsl:template>

The code shown here is simplified by assuming that the start- and end-markers in its input correspond to the start- and end-tags of a well-formed XML document. The template for end-markers, for example, does not check to see that the end-marker found is the one that matches the element on the top of the current element stack. When confonted with the overlapping virtual elements of some of our sample input, therefore, the code shown here will behave as if start- and end-markers were paired up by position, without regard for co-indexing or element type.

Better behavior in the presence of overlapping virtual elements or errors in the input can be achieved by passing parameters on each call to apply-templates in mode raising, which keep a stack of co-indexing IDs and element types.

Resource consumption

A few notes on resource consumption may be in order.

The templates shown each handle a single node and then call <xsl:apply-templates>, selecting the next node to be processed. The template activation stack in the XSLT processor thus contains no sets of nodes waiting to be processed, but the call stack may become rather deep: in our sample data, the maximum depth of the template stack is the number of nodes in the flattened portion of the input. An XSLT processor that does not eliminate tail-recursive template calls may thus run out of stack space (at least in theory—in practice, we have never seen a right-sibling recursion blow the stack on real, well-formed input).

Because the right-sibling idiom visits each node in the flattened input just once, the cost of the process should be linear in the size of the input. (In practice, preliminary measurements suggest that with the Saxon HE processor, the rise in cost is sub-linear to the rise in input size.)

Despite its virtues, the right-sibling traveral idiom is needed rarely enough in XSLT programming that many XSLT authors have never used it; some find it difficult.^[7] The inside-out algorithm described below (Inside-out recursion) can be regarded as an alternative which is closer to conventional XSLT usage. The implementation using XSLT 3.0 accumulators is another approach worth learning.

Raising Frankenstein

For raising Frankenstein using right-sibling traversal, we adapt the code lightly to apply to its project markup in the following template rules:

     <xsl:template match="div[@type='collation']">
     <xsl:apply-templates select="child::node()[1]" mode="raising"/>
 </xsl:template>  
    <xsl:template match="*[@th:sID]" mode="raising">     
        <xsl:variable name="ln" as="xs:string" select="name()"/>
        <xsl:variable name="sID" as="xs:string" select="@th:sID"/>
        
        <!--* 1: handle this element *-->
        <xsl:copy>
           <xsl:attribute name="xml:id">
               <xsl:value-of select="$sID"/>
           </xsl:attribute>
            <xsl:apply-templates select="following-sibling::node()[1]" mode="raising">
            </xsl:apply-templates>
        </xsl:copy>
        
        <!--* 2: continue after this element *-->
      <xsl:apply-templates select="following-sibling::*
            [@th:eID= $sID 
            and name()=$ln]
            /following-sibling::node()[1]"
            mode="raising">
        </xsl:apply-templates>
    </xsl:template>
  <xsl:template match="text() | comment() | processing-instruction | *[not(@loc)]"
        mode="raising">
        <xsl:copy-of select="."/>
        <xsl:apply-templates 
            select="following-sibling::node()[1]"
            mode="raising"/>
    </xsl:template>
    <xsl:template match="*[@th:eID]" mode="raising"/>
                

Raising

The output of the preceding transformation is included in the Simplified sample data section, above. We then reconstruct the hierarchy using the inside-out recursive function th:raise() in the following XSLT stylesheet:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="3.0"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:th="http://www.blackmesatech.com/2017/nss/trojan-horse"
    exclude-result-prefixes="#all">
    <xsl:output method="xml" indent="no"/>

    <!--* Set $debug parameter to any non-null value to output messages *-->
    <xsl:param name="debug" static="yes" required="no"/>

    <xsl:key name="end-markers" match="*[@th:eID]" use="@th:eID"/>

    <!-- 
        Identity template of anything lower than grandchildren of the root
        Just copy; they cannot contain markers
    -->
    <xsl:template match="/*/*/descendant::node()" mode="#all">
        <xsl:sequence select="."/>
    </xsl:template>

    <!-- Traditional identity template for root and its children -->
    <xsl:template match="@* | node()" mode="#all">
        <xsl:copy copy-namespaces="no">
            <xsl:apply-templates select="@* | node()"/>
        </xsl:copy>
    </xsl:template>

    <!-- 
        th:raise(.):  raise all innermost elements within the document
        messages controlled by $debug stylesheet parameter
    -->
    <xsl:function name="th:raise">
        <xsl:param name="input" as="document-node()"/>
        <xsl:message use-when="$debug">raise() called with 
            <xsl:value-of select="count($input//*)"/>-element document 
            (<xsl:value-of select="count($input//*[@th:sID])"
            /> Trojan pairs)</xsl:message>
        <xsl:choose>
            <xsl:when test="exists($input//*
                           [@th:sID eq following-sibling::*[@th:eID][1]/@th:eID])">
                <!-- If we have more work to do, do it -->
                <xsl:variable name="result" as="document-node()">
                    <xsl:document>
                        <xsl:apply-templates select="$input" mode="loop"/>
                    </xsl:document>
                </xsl:variable>
                <xsl:sequence select="th:raise($result)"/>
            </xsl:when>
            <xsl:otherwise>
                <!-- We have no more work to do, return the input unchanged. -->
                <xsl:message use-when="$debug">raise() returning.</xsl:message>
                <xsl:sequence select="$input"/>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:function>

    <xsl:template match="/">
        <xsl:sequence select="th:raise(.)"/>
    </xsl:template>

    <xsl:template match="/" mode="loop">
        <xsl:apply-templates/>
    </xsl:template>

    <!--
        Innermost start-markers
        @priority needed here and below because otherwise ambiguous with identity templates
    -->
    <xsl:template match="*[@th:sID eq following-sibling::*[@th:eID][1]/@th:eID]" priority="1">
        <xsl:copy copy-namespaces="no">
            <xsl:copy-of select="@* except @th:sID"/>
            <xsl:variable name="end-marker" as="element()" select="key('end-markers', @th:sID)"/>
            <xsl:copy-of select="following-sibling::node()[. &lt;&lt; $end-marker]"/>
        </xsl:copy>
    </xsl:template>

    <!-- nodes inside new wrapper: suppress, since they have alredy been copied -->
    <xsl:template
        match="node()[preceding-sibling::*[@th:sID][1]/@th:sID eq following-sibling::*[@th:eID][1]/@th:eID]"
        priority="1"/>

    <!-- end-tag for new wrapper; suppress because it has already been copied -->
    <xsl:template match="*[@th:eID eq preceding-sibling::*[@th:sID][1]/@th:sID]" priority="1"/>

</xsl:stylesheet>

We turn off indentation (line 5) to avoid deforming the whitespace and set up a debug option (line 8), controlled by a $debug parameter.

The traditional identity template walks the entire tree, but because any descendant nodes lower than children of the root are guaranteed not to be or contain Trojan markers, we set up one identity template for those lower nodes, which just copied them to the output (lines 16–18). The regular identity template (lines 21–25) applies only to the root element and its children. @exclude-result-prefixes="#all" is not enough to avoid writing the th: namespace onto the root element of the output, even though the namespace in question is not used in the output. An unused namespace declaration is informationally harmless, but also needlessly distracting, so we suppress it by specifying @copy-namespaces="no" on <xsl:copy> in the identity template that deals with Trojan markers (line 22).

Our recursive raising operation (the th:raise() function, lines 31–52) operates on document nodes, and we need to process the original document node of the input file differently from the new document nodes that we create on each pass through the recursive function. For that reason, we match the original document node in no mode (<xsl:template match="/">, lines 54–56) and pass it into the raising function (<xsl:sequence select="th:raise(.)"/>, line 55).

The raising function checks for the presence of @th:sID attributes in the input that are candidates for raising (<xsl:when test="exists($input//*[@th:sID eq following-sibling::*[@th:eID][1]/@th:eID])">, line 137 see the discussion of this test in Inside-out recursion challenges). If there aren’t any (<xsl:otherwise>, lines 46–50), the recursion is finished, and the function returns the result (<xsl:sequence select="$input"/>, line 49). If there are still @th:sID attributes that can be raised in the text, we create a variable $result (lines 39–43) of type document and apply templates inside the newly created document node (line 41). After the application of templates is finished, we recur and pass the result into another invocation of th:raise() (<xsl:sequence select="th:raise($result)"/>, line 44).

The application of templates within the recursive function begins by applying templates to the (newly created) document node in loop mode (<xsl:apply-templates select="$input" mode="loop"/>, line 41). The matching template (lines 58–60) simply applies templates to its children, unlike the template that matches the original document node (in no mode, lines 54–56), which passes the document into the th:raise() function (line 55), a difference in mode that is needed to avoid an endless loop. All other processing is the same for both the original document and the interim documents created inside th:raise(), so <xsl:template match="/" mode="loop"> (lines 58–60) is the only modal template, and it applies templates to its children in no mode.

There are three templates that do the actual processing of the innermost elements to be raised on each recursion: one that processes the start-marker, one that processes the content of the newly raised container element, and one that processes the corresponding end-marker. XSLT thinks that they have the same priority as the identity templates, so we specify a higher priority explicitly with priority="1".

When the simplified original document is flattened and then raised, as described above, the output of the raising operation matches the original input.

Raising Frankenstein

To raise the Frankenstein data, our process is run recursively over a collection of 165 files in the Frankenstein Variorum. The files have a TEI header that for project maintenance purposes needs to be updated after a version change, and only a portion of the document is to be raised. Here the most significant adaptation is that we supply an element node rather than a document node as the input parameter for the th:raise function.

      <?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet
    xpath-default-namespace="http://www.tei-c.org/ns/1.0"
    xmlns="http://www.tei-c.org/ns/1.0"  
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:th="http://www.blackmesatech.com/2017/nss/trojan-horse"
    exclude-result-prefixes="#all"
    version="3.0">
    <xsl:output method="xml" indent="no"/>
    <!--* This stylesheet works to raise "trojan
	elements" from the inside out, this time over a collection
	of Frankenstein files output from collation. It also adapts
	djb's function to process an element node rather than a
	document node in memory to perform its recursive
	processing. *-->
    <xsl:variable name="novel-coll"
        as="document-node()+"
        select="collection('../input/frankenstein/novel-coll/')"/>    
     
    <!--* In all modes, do a shallow copy, suppress namespace nodes,
	* and recur in default (unnamed) mode. *-->
    <xsl:template match="@* | node()" mode="#all">
      <xsl:copy copy-namespaces="no">
            <xsl:apply-templates select="@* | node()"/>
        </xsl:copy>
    </xsl:template>

    <!--* th:raise(.):  raise all innermost elements within the container element this time passed as parameter *-->
   <xsl:function name="th:raise">
       <xsl:param name="input" as="element()"/>
       <xsl:choose>
           <xsl:when test="exists($input//*[@th:sID eq following-sibling::*[@th:eID][1]/@th:eID])">
               <xsl:variable name="result" as="element()">
                   <div type="collation">
                       <xsl:apply-templates select="$input" mode="loop"/>                            
                   </div>
               </xsl:variable>
               <xsl:sequence select="th:raise($result)"/>
           </xsl:when>
           <xsl:otherwise>
               <!--* We have no more work to do, return the input unchanged. *-->
               <xsl:message>raise() returning.</xsl:message>
               <xsl:sequence select="$input"/>
           </xsl:otherwise>
       </xsl:choose>
   </xsl:function>
   
   <xsl:template match="/">
       <xsl:for-each select="$novel-coll//TEI">
           <xsl:variable name="filename">              
               <xsl:text>raised_</xsl:text><xsl:value-of select="tokenize(base-uri(), '/')[last()]"/>
           </xsl:variable>
           <xsl:variable name="chunk"
			 as="xs:string"
			 select="substring-before(tokenize(base-uri(), '/')[last()], '.') ! substring-before(., '_')"/> 
           <xsl:result-document method="xml"
				indent="yes"
				href="output/frankenstein/novel-coll/{$filename}">
               <TEI>
		   <xsl:apply-templates select="descendant::teiHeader"/>
		   <text>
		       <body>
			   <xsl:apply-templates select="descendant::div[@type='collation']"/>
		       </body>
		   </text>
               </TEI>
           </xsl:result-document>
       </xsl:for-each>  
   </xsl:template>
<!--* Template rules for altering the TEI header, otherwise uninvolved in the raising process: *-->   
   <xsl:template match="teiHeader">
       <teiHeader>
           <fileDesc>
               <titleStmt><xsl:apply-templates select="descendant::titleStmt/title"/></titleStmt>
               <xsl:copy-of select="descendant::publicationStmt" copy-namespaces="no"/>
               <xsl:copy-of select="descendant::sourceDesc" copy-namespaces="no"/>
	   </fileDesc>
       </teiHeader>
   </xsl:template>  
   <xsl:template match="titleStmt/title">
       <title>
           <xsl:text>Bridge Phase 4:</xsl:text><xsl:value-of select="tokenize(., ':')[last()]"/>
       </title>
   </xsl:template>
    
    <!--* On the input container element node, call th:raise() *-->
   <xsl:template match="div[@type='collation']">
       <xsl:sequence select="th:raise(.)"/>
   </xsl:template>
    <!--* Loop mode (applies to container element only). *-->
    <!--* Loop mode for container element:  just apply templates in default unnamed mode. *-->  
   <xsl:template match="div[@type='collation']" mode="loop">
       <xsl:apply-templates/>
   </xsl:template>  
    <xsl:template match="*[@th:sID eq
        following-sibling::*[@th:eID][1]/@th:eID]">
       <xsl:variable name="currNode" select="current()" as="element()"/>
       <xsl:variable name="currMarker" select="@th:sID" as="xs:string"/>
       <xsl:element name="{name()}">
           <xsl:copy-of select="@* except @th:sID"/>
           <xsl:attribute name="xml:id">
               <xsl:value-of select="@th:sID"/>
           </xsl:attribute>
           <xsl:variable name="end-marker" as="element()" select="following-sibling::*[@th:eID = current()/@th:sID]"/>
           <xsl:copy-of select="following-sibling::node()[. &lt;&lt; $end-marker]"/>
       </xsl:element>
   </xsl:template>

   <!--suppressing nodes that are being reconstructed, including the old end marker. -->
    <xsl:template
        match="node()[preceding-sibling::*[@th:sID][1]/@th:sID eq following-sibling::*[@th:eID][1]/@th:eID]"/>
   
    <xsl:template match="*[@th:eID eq preceding-sibling::*[@th:sID][1]/@th:sID]"/>
        </xsl:stylesheet>
                    

The adaptation to the raising function to process a container element node allows for us to make changes to our TEI header. Beyond this, there are few differences between our generic inside-out raising example and the Frankenstein stylesheet. One minor difference is that we use only one identity-transformation template, and have not set a priority on the template rule to process the innermost elements. We convert the Trojan marker attributes into an xml:id with an element constructor:

<xsl:element name="{name()}">
    <xsl:attribute name="xml:id" select="@th:sID"/>
    <xsl:copy-of
        select="following-sibling::node()[following-sibling::*[@th:eID eq current()/@th:sID]]"/>
</xsl:element>

Code outline

The default handling for all nodes is a shallow copy, as specified in the mode declaration for the default mode:

<xsl:mode on-no-match="shallow-copy"/>

For content nodes, the function th:raise-sequence() is called on their children. In the simple inputs we are dealing with, this template will match only the document's outermost element; for the Frankenstein data, it will match several others. At the time of this writing, we have not experimented to see whether it would be faster to test for start- and end-marker children here.

<xsl:template match="*[exists(node())]">
  <xsl:copy>
    <xsl:sequence 
      select="@*,
             th:raise-sequence(child::node())"/>
  </xsl:copy>
</xsl:template>

The core of the implementation is the th:raise-sequence function.

The function begins by creating lists of start- and end-markers (identified by their co-indexing IDs), so that we can find not just the leftmost start-marker but the leftmost start-marker with a matching end-marker in the sequence. If there are no matching pairs in the sequence, the sequence is returned without change. (This makes this implementation slightly more robust in the presence of overlap than the implementation shown above of the right-sibling traversal approach; we have not yet had time to update our method of right-sibling traversal to rectify the inconsistency in implementation philosophy.)

In the normal case, however, the function will select the leftmost start-marker with a matching end-marker, find the positions of the start- and end-markers in the input, and then partition the input sequence into three parts. A call to apply-templates processes nodes preceding the selected start-marker; a recursive call to th:raise-sequence() from within the raised elements processes the nodes between the selected start- and end-markers; a second recursive call processes the remainder of the original sequence.

<xsl:function name="th:raise-sequence" as="node()*">
    <xsl:param name="ln" as="node()*"/>

    <!--* lidStarts, lidEnds:  lists of IDs
        * for start- and end-markers *-->
    
    <xsl:variable name="lidStarts"
      as="xs:string*"
      select="for $n in $ln[th:start-marker(.)]
        return th:id($n)"/>
    <xsl:variable name="lidEnds"
      as="xs:string*"
      select="for $n in $ln[th:end-marker(.)]
        return th:id($n)"/>
    
    <xsl:choose>
      <!--* base case:  no start-marker / end-marker
          * pairs present *-->
      <xsl:when test="empty($lidStarts[. = $lidEnds])">
        <!--* The sequence may contain elements 
            * with markers inside, so we apply 
            * templates, instead of just returning $ln *-->
        <xsl:apply-templates select="$ln"/>
      </xsl:when>

      <!--* 'normal' case: take first start-marker 
          * with matching end-marker *-->
      <xsl:otherwise>
        <!--* find ID of first start-marker
           * with matching end-marker *-->
         <xsl:variable name="id"
           as="xs:string"
           select="$lidStarts[. = $lidEnds][1]"/>
        <!--* find position of start- and
            * end-markers with that ID *-->
        <xsl:variable name="posStartEnd"
          as="xs:integer+"
          select="for $i in 1 to count($ln) return
                      if ($ln[$i]
                          [(th:start-marker(.) 
                          or th:end-marker(.)) 
                          and th:id(.) eq $id])
                          then $i else ()"/>
                          
        <xsl:variable name="posStart" 
          as="xs:integer"
          select="$posStartEnd[1]"/>
        <xsl:variable name="posEnd" 
          as="xs:integer"
          select="$posStartEnd[2]"/>

        <!--* Apply templates to all items to 
            * left of start. These may include
            * markers, but if so they are not 
            * matched and not raisable. They 
            * may also include elements which
            * contain markers, so we need to apply
            * templates, not just return them.
            *-->
            
        <xsl:apply-templates
          select="$ln[position() lt $posStart]"/>
        
        <!--* Raise the element and 
            * call raise-sequence() on its
            * content. *-->
        <xsl:copy select="$ln[$posStart]">
          <!--* copy the attributes
              * (filtering as needed) *-->
          <xsl:sequence 
            select="$ln[$posStart]/(@* except @th:*)"/>

          <!--* handle children *-->      
          <xsl:sequence 
            select="th:raise-sequence(
                   $ln[position() gt $posStart 
                       and position() lt $posEnd])"/>    
        </xsl:copy>
        
        <!--* call raise-sequence() on all items 
            * to right of end *-->
        <xsl:sequence
          select="th:raise-sequence(
                 $ln[position() gt $posEnd]
                 )"/>
      </xsl:otherwise>
    </xsl:choose>
</xsl:function>

A number of ancillary functions are defined in the stylesheet and used in the code shown above. They are shown briefly here.

The th:start-marker() and th:end-marker() functions encapsulate the recognition criteria for markers. (These forms are redundant with those given elsewhere in this paper; we have not yet eliminated the redundancy in our demonstration code.)

  <xsl:function name="th:start-marker" as="xs:boolean">
    <xsl:param name="e" as="node()"/>
    
    <xsl:value-of use-when="$th-style = 'th' "
	select="exists($e/@th:sID)"/>
    <xsl:value-of use-when="$th-style = 'xmlid' "
	select="ends-with($e/@xml:id,'_start')"/>
    
  </xsl:function>
  
  <xsl:function name="th:end-marker" as="xs:boolean">
    <xsl:param name="e" as="node()"/>
    
    <xsl:value-of use-when="$th-style = 'th' "
	select="exists($e/@th:eID)"/>
    <xsl:value-of use-when="$th-style = 'xmlid' "
		  select="ends-with($e/@xml:id,'_end')"/>
    
  </xsl:function>
  

The th:id() function returns the co-indexing identifier used for any given marker.

<xsl:function name="th:id" as="xs:string?">
    <xsl:param name="e" as="node()"/>
    
    <xsl:value-of use-when="$th-style = 'th' "
	select="($e/@th:sID, $e/@th:eID)"/>
    <xsl:value-of use-when="$th-style = 'xmlid' "
		  select="replace($e/@xml:id,'(_start|_end)$','')"/>
    
</xsl:function>

Resource consumption

The implementation shown calls the th:raise-sequence() function once for each virtual element. The cost of the process should thus be roughly linear in the number of virtual elements in the input; that seems consistent with our timings of XSLT processors.^[9]

Each node in the original flattened sequence is passed to the central as part of the argument sequence once for each level of its distance from the root of the virtual tree. In this, the outside-in approach is indeed the mirror image of the inside-out approach.

The implementation of outside-in shown here is not, however, demonstrably faster than our implementation of inside-out, despite the divide-and-conquer strategy. We have not been able to perform measurements to explain the differences in run time, but we can offer a couple of speculations. First, on our test data the inside-out approach reduces the number of nodes faster than the outside-in approach: in a typical XML tree there will be more leaf nodes than root nodes (and more than that: in our test data the fanout increases with distance from the root). Second, each call to the function traverses the input sequence several times: once to find all start-marker IDs, once to find all end-marker IDs, once to find the positions of the selected markers. Either or both of these could explain a slow run-time.

A bluffer's guide to accumulators

An accumulator is a sequence of values associated with the nodes of a tree. Each node has two values:

As a simple example, we can make an accumulator to keep track of the number of open virtual elements at any given point in the flattened input document: when we encounter a start-marker we will add one to the accumulated value, and when we encounter an end-marker we will subtract one. An accumulator is declared using an <xsl:accumulator> declaration, which contains a sequence of <xsl:accumulator-rule> elements describing how the accumulator’s values are calculated. Within an accumulator rule, the variable $value gives the value of the accumulator assigned by the immediately preceding node.

<xsl:accumulator name="level" as="xs:integer"
                   initial-value="0"
                   streamable="yes" >
    <xsl:accumulator-rule match="*[@th:sID]"
                          select="$value + 1"/>
    <xsl:accumulator-rule match="*[@th:eID]"
                          select="$value - 1"/>
</xsl:accumulator>

The pattern in the accumulator rules here assumes that start- and end-markers use the @th:sID and @th:eID attributes described above.

At any point in a tree to which this accumulator applies, we can refer to the current node’s before value of the accumulator with the expression accumulator-before('stack') and to the after value with accumulator-after('stack').^[10] Without accumulators, we could keep track of the relevant information by replacing references to accumlator-before('stack') with references to count(preceding::*[@th:sID]) - count(preceding::[@th:eID]).

Implementation strategy

To solve the raising problem with accumulators, we declare an accumulator whose value is an array (if the XPath 3.1 feature is supported) or a map, with which we maintain a stack of virtual elements that have been started, but not finished. The first member of the array will track the contents of the outermost element, the second member will track the contents of a second-level virtual element, and so forth. Each member of the array is a sequence of nodes containing a start marker (the first item in the sequence) and all the nodes seen so far that should be children of the raised content element.

The processing rules are relatively straightforward and may feel familiar to anyone who has ever constructed an in-memory tree from a SAX event stream:

Some utility functions

In order to allow the stylesheet to be used with either the th: attributes or with the ana="start|end" convention, we isolate the definition of start- and end-markers in two functions we place in the Trojan-Horse namespace:

<!--* th:trojan-start($e as element()):  true iff $e is a Trojan
    * start-tag we want to process.
    *-->
<xsl:function name="th:trojan-start" as="xs:boolean">
    <xsl:param name="e" as="element()"/>
    
    <xsl:value-of use-when="$th-style = 'th' "
        select="exists($e/@th:sID)"/>
    <xsl:value-of use-when="$th-style = 'xmlid' "
        select="ends-with($e/@xml:id,'_start')"/>
    
 </xsl:function>
  
<!--* th:trojan-end($e as element()):  true iff $e is a Trojan
    * end-tag we want to process.
    *-->
<xsl:function name="th:trojan-end" as="xs:boolean">
    <xsl:param name="e" as="element()"/>
    
    <xsl:value-of use-when="$th-style = 'th' "
        select="exists($e/@th:eID)"/>
    <xsl:value-of use-when="$th-style = 'xmlid' "
                  select="ends-with($e/@xml:id,'_end')"/>
    
</xsl:function>

These functions rely on a static parameter that identifies the idiom in use for markers.

<xsl:param name="th-style" select=" 'ana' " static="yes"/>

Marking the parameter as static allows the choice among definitions to be made during static analysis of the stylesheet (informally, at compile time) and not with a dynamic (run-time) choose/when construction.

Another function constructs a content element from a sequence of nodes beginning with a start-marker:

<!--* th:make-element($ln as node()+):  make an element out of
    * one stack entry *-->
<!--* We package this as a function because it's called from
    * two different locations in the stylesheet *-->
<xsl:function name="th:make-element" as="element()">
    <xsl:param name="ln" as="node()+"/>
    
    <xsl:copy select="$ln[1]">
      <!--* first copy (and filter) attributes *-->
      <xsl:sequence select="$ln[1]/(@* except @th:*)"
                    use-when="$th-style = 'th' "/>  
      <xsl:sequence use-when="$th-style='xmlid'">
        <xsl:sequence select="$ln[1]/@*"/>
        <xsl:attribute name="xml:id" 
            select="replace($ln[1]/@xml:id, '_start$','')"/>
      </xsl:sequence>
      
      <!--* then copy children *-->
      <xsl:sequence select="$ln[position() gt 1]"/>
    </xsl:copy>
    
</xsl:function>

The functions just presented are not specific to the use of accumulators; they or analogous functions could be used in any of the XSLT stylesheets described here. But most of the other code shown in the current version of this paper does not use them; they are described here because the other code in this section uses them and would be hard to understand if they were not presented.

Declaring the accumulator and making it applicable

The overall pattern of accumulator declarations was shown above, and the declaration for an accumulator to be used as a stack follows the same pattern, though the rules are slightly more complex.

<!--* Declare stack accumulator to keep track of contents. *-->
<!--* Start with empty array. *-->
<xsl:accumulator name="stack" as="array(node()*)"
               initial-value="[]"
               streamable="yes"
               >
<!--* On Trojan start-tag, push the start-tag onto the stack *-->
<xsl:accumulator-rule match="*[th:trojan-start(.)]"
                      select="array:append($value, .)"/>

<!--* On Trojan end-tag, make the currently pending element,
    pop the stack, and insert the pending element at the
    end of the new top item. *-->
<xsl:accumulator-rule match="*[th:trojan-end(.)]"                     
                      phase="end">
  
  <xsl:variable name="level" as="xs:integer"
                select="array:size($value)"/>
  <xsl:variable name="e" as="element()"
                select="th:make-element($value($level))"/>
  <xsl:choose>
    <xsl:when test="$level eq 1">
      <!--* at outermost level, we have no previous
          level to add anything to, so we just pop the
          stack. *-->
      <xsl:sequence select="[]"/>
    </xsl:when>
    <xsl:otherwise>   
      <xsl:sequence select="array:put(
                            array:remove($value, $level),
                            $level - 1,
                            ($value($level - 1), $e))"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:accumulator-rule>

<!--* On any other node, append current node
    * to the top sequence in the stack *-->
<xsl:accumulator-rule
    match="node()[not(self::element())
            or (not(th:trojan-start(.)) 
            and not(th:trojan-end(.)))]"
    select="for $level in array:size($value) return
            if ($level eq 0)
            then []
            else array:put(
                 $value,
                 $level,
                 ($value($level), .))"/>
</xsl:accumulator>

Since accumulators were introduced largely to support the streaming processing of very large inputs, and since the pointless calculation of accumulator values would make that processing unnecessarily difficult, XSLT 3.0 requires that any accumulators be associated more or less explicitly with an input tree or a mode. If the accumulator is not made applicable to a given tree in this way, references to the accumulator-before() and accumulator-after() functions will raise errors. We handle that by declaring the default mode of the stylesheet and adding a @use-accumulators attribute naming the accumulators to be calculated:

<!--* declare default mode; we make it fail on no match
  * because it turns out we need templates for all nodes.
  *-->
<xsl:mode on-no-match="fail"
        use-accumulators="stack"
        streamable="yes"/>

Note that the streamable="yes" is not required unless streaming processing is to be requested.^[11]

Templates

The templates in this stylesheet have very little work to do: their primary task is to override the default templates and ensure that nodes are not copied unnecessarily to the output tree.

The template for start-markers does nothing; all the work is handled by the declaration of the accumulator.

<!--************************************************
  * 1.  Virtual start-tags 
  ************************************************-->
<xsl:template match="*[th:trojan-start(.)]" priority="10">
<!--* Nothing to do, all the work 
    * is done by the accumulator *-->
</xsl:template>

The template for end-markers is more complicated, because it must handle the case where the end-marker marks the end of an outermost virtual element. The normal accumulator rules cannot handle this case, because they write the newly constructed element into the new top member of the stack. But after we pop the stack at level one, the stack is empty and there is no top member. So we need to make the element and write it to the output tree ourselves. In all other cases, this template has no work to do.

<!--************************************************
  * 2.  Virtual end-tags 
  ************************************************-->  
<xsl:template match="*[th:trojan-end(.)]" priority="10">
<xsl:choose>
  <xsl:when
      test="array:size(accumulator-before('stack')) eq 1">  
    <!--* if this end-tag ends the outermost element,
        * emit the element *-->
    <xsl:sequence
      select="th:make-element(accumulator-before('stack')(1))"/>                
  </xsl:when>
  <xsl:otherwise>
    <!--* Otherwise, nothing to do *-->
  </xsl:otherwise>
</xsl:choose>
</xsl:template>

The template for the document node is identical to the default template; it is made necessary by the specification on-no-match="fail" on the mode declaration.

<!--************************************************
  * 3.  All other nodes 
  ************************************************-->
<!--* 3.1 Document node *-->
<xsl:template match="/">
<xsl:apply-templates/>
</xsl:template>

The templates for other nodes make the same distinction as that for end-markers: when the stack is empty, the node is copied to the output tree, and otherwise all the work is left to the accumulator.

<!--* 3.2 Non-marker element nodes *-->
<xsl:template match="node()[self::element()
                   and not(th:trojan-start(.))
                   and not(th:trojan-end(.)) ]">
<!--* If we are outside the flattened area, copy the node;
    * otherwise, do nothing and leave everything 
    * to the accumulator *-->
<xsl:choose>
  <xsl:when 
      test="array:size(accumulator-before('stack')) eq 0">
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:apply-templates/>
    </xsl:copy>
  </xsl:when>
  <xsl:otherwise/>
</xsl:choose>    
</xsl:template>

<!--* 3.3 Non-element nodes *-->
<xsl:template match="node()[not(self::element())]">
<!--* If we are outside the flattened area, copy the node;
    * otherwise, do nothing and leave everything 
    * to the accumulator *-->
<xsl:choose>
  <xsl:when
      test="array:size(accumulator-before('stack')) eq 0">
    <xsl:sequence select="."/>
  </xsl:when>
  <xsl:otherwise/>
</xsl:choose>    
</xsl:template>

String output

The following Python 3 code replaces markers with strings equivalent to real XML start- and end-tags:

import sys
from xml.dom.pulldom import CHARACTERS, START_ELEMENT, parseString, END_ELEMENT

def entities(input):
    return input.replace('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;')
output = []
with open(sys.argv[1], 'r') if len(sys.argv) > 1 else sys.stdin as input:
    for event, node in parseString(input.read()):
        if event == START_ELEMENT:
            if node.hasAttribute('th:eID'): 
                # Trojan end tag
                output.append('</')
            else: 
                # Trojan start tags and non-Trojan elements
                output.append('<')
            output.append(node.nodeName)
            for attname, attvalue in node.attributes.items(): 
                # remove Trojan attributes and namespace declaration
                if not (attname.startswith('th:') or attname == 'xmlns:th'):
                    output.append(' ' + attname + '="' + attvalue + '"')
            output.append('>')
        if event == END_ELEMENT:
            if not (node.hasAttribute('th:sID') or node.hasAttribute('th:eID')): 
                # non-Trojan only
                output.append('</' + node.nodeName + '>')
        elif event == CHARACTERS:
            output.append(entities(node.data))
print("".join(output))

We create an empty list to hold the output, read in the source, and examine each event. In this simplified example, we process only START_ELEMENT, END_ELEMENT, and CHARACTERS, as follows:

We are parsing the input XML in an XML-aware manner, which is reasonably robust, but we are constructing the output XML as a string, which is not. See below section “Pull parsing in Python” for a discussion of the limitations.

XML output

The general approach to parsing with pulldom and constructing output with minidom is similar to the Accumulators method described above. Specifically, the flattened XML is traversed in a single pass from left to right (technically a depth-first traversal, which is how pulldom sees it) and events (we focus on START_ELEMENT, END_ELEMENT, and CHARACTERS) are handled as they occur. The output is assembled in memory as a tree, using minidom to create and attach nodes as needed. Open elements are stored on a stack, the maximum depth of which is, therefore, equal to the maximum depth of the unflattened XML. The code is:

from xml.dom.pulldom import CHARACTERS, START_ELEMENT, parseString, END_ELEMENT
from xml.dom.minidom import Document


class Stack(list):
    def push(self, item):
        self.append(item)

    def peek(self):
        return self[-1]


open_elements = Stack()
d = Document()
open_elements.push(d)

with open('flattened.xml') as input:
    for event, node in parseString(input.read()):
        if event == START_ELEMENT:
            if not node.hasAttribute('th:eID'): # process pseudo-end-tags on END_ELEMENT event
                open_elements.peek().appendChild(node)
                open_elements.push(node)
        elif event == END_ELEMENT:
            if node.hasAttribute('xmlns:th'): # don't declare now-unused th: namespace
                node.removeAttribute('xmlns:th')
            if node.hasAttribute('th:sID'): # can't remove @start until we're done with the node
                node.removeAttribute('th:sID') 
            else: # pop only on container elements and Trojan end-tags
                open_elements.pop()
        elif event == CHARACTERS:
            t = d.createTextNode(node.data)
            open_elements.peek().appendChild(t)

                print(open_elements.pop().toxml())

Parsing is the same as described above, so we import the same items from pulldom. From minidom we import only the Document class, which we use to initialize our output XML document. Our Stack class is a Python list adorned with stack-idiomatic terminology: we alias append() as push() (lists already have a pop() method), and we add peek() to provide access to the item at the top of the stack. That top item is the most recently opened element, and we peek at it in order to append child elements and child text() nodes as we encouter them. We begin by pushing the document node onto the stack.

We handle START_ELEMENT, END_ELEMENT, and CHARACTERS events in an if/elif/elif structure, silently ignoring other events. There are three types of elements whose start and end events we need to process: start-markers, end-markers, and regular elements (whether empty or not).

Conceptually, the entire start-marker functions as if it were the START_ELEMENT event for a regular element, and the entire corresponding end-marker functions as if it were the END_ELEMENT event for the same regular element. This means that we push a start-marker on its START_ELEMENT event (ignoring its END_ELEMENT event, except to remove its Trojan attribute), and pop it on the corresponding end-marker’s END_ELEMENT event (ignoring its START_ELEMENT event). In tabular form:

Double processing

When a start-marker is matched and raised, the nodes that belong inside the new container are copied into it inside the template that matches the start-marker. Because the nodes being copied are also candidates for the application of templates in the current pass through the function, we need to match them (along with the end-marker) in an empty <xsl:template> in order to avoid outputting them twice. Otherwise they would be copied when the start-marker is matched and then processed again when templates are applied to them in their own right.

Endless recursion

Recursion requires an exit condition to avoid falling into an endless loop. In an early version of the code, the recursive function tested for the presence of Trojan milestone attributes, and if there weren’t any, it concluded that all raising had been completed and stopped the recursion. This test fails in situations where there are Trojan elements that cannot be raised without creating overlap. Avoiding the endless loop in such situations requires a more complex test, not just for the presence of Trojan attributes, but for the presence of those that can be raised without creating overlap. In our simplified sample, instead of testing for exists($input//@th:sID), we test for elements that can be raised without risk of overlap with:

exists($input//*[@th:sID eq following-sibling::*[@th:eID][1]/@th:eID])

Endless recursion is not an issue in situations where complete raising would not create overlap. This is the case with our original simplified sample, where the XML with Trojan markup was created by flattening original hierarchical XML, and since the original could not have had overlap, it can be reconstructed safely. Endless recursion is also not a problem when we raise only a subset of the markup that is guaranteed not to overlap. For example, if we have tessellated page and paragraph hierarchies over a prose text, where both pages and paragraphs have been flattened, we cannot fully raise all instances both types of elements if doing so would create overlap. But if our markup convention is that pages cannot overlap with pages and paragraphs cannot overlap with paragraphs, we can modify the raising routine to raise only the pages or only the paragraphs. See also Appendix A, where we discuss an alternative approach to raising with data of this type.

String output

Creating XML output as a string is a brittle strategy. Not only is it susceptible to writing overlapping tags for the same reason as the regex method described earlier, but we also explicitly wrap attribute values in double-quote characters ("), which will produce results that are not well-formed if the attribute value happens to have contained the double-quote character originally. Python has an escape mechanism that is capable of dealing with awkwardly nested single- and double-quote characters in strings, as does XML, but the Python escape strategy is different from the XML one, and the code to perform the string manipulation needed to mediate between the two is difficult to read and write. Furthermore, where output is created as a string, we have to replace reserved characters with character entities explicitly ourselves, while XML-aware output does that automatically. For those reasons, it is safer to use XML methods to create the XML output as a (necessarily well-formed) DOM tree, which can then be serialized, instead of creating the output directly as a string. The use of pulldom to parse the input XML also requires accommodations to the peculiarities of pulldom namespace handling, which are discussed immediately below, under Python XML output challenges.

XML output

Generating XML output with Python minidom is reasonably robust and straightforward, but potentially confusing for the following reasons: