Canonical XML Version 2.0

1.1 Terminology

The key words "must", "must not", "required", "shall", "shall not", "should", "should not", "recommended", "may", and "optional" in this document are to be interpreted as described in RFC 2119 [RFC2119].

See [XML-NAMES] for the definition of QName.

document subset

A document subset is a portion of an XML document that may not include all of the nodes in the document.

canonical form

The canonical form of an XML document is physical representation of the document produced by the method described in this specification

canonical XML

The term canonical XML refers to XML that is in canonical form. The XML canonicalization method is the algorithm defined by this specification that generates the canonical form of a given XML document or document subset. The term XML canonicalization refers to the process of applying the XML canonicalization method to an XML document or document subset.

subtree

Subtree refers to one XML element node, and all that it contains. In XPath terminology it is an element node and all its descendant nodes

DOM

DOM or Document Object Model is a model of representing an XML document in tree structure. The W3C DOM standard [DOM-LEVEL-2-CORE] is one such DOM, but this specification does not require this particular set of DOM APIs, any similar model can be used as long as it has a tree representation of the XML document, whose root is a document node, and the document node's descendants are element nodes, attribute nodes, text nodes etc.

DOM parser

An software module that reads an XML document and constructs a DOM tree.

Stream parser

A software module that reads an XML document and constructs a stream of XML events like "beginElement", "text", "endElement". [StAX] is an example of a stream parser.

1.2 Applications

Since the XML 1.0 Recommendation [XML10] and the Namespaces in XML 1.0 Recommendation [XML-NAMES] define multiple syntactic methods for expressing the same information, XML applications tend to take liberties with changes that have no impact on the information content of the document. XML canonicalization is designed to be useful to applications that require the ability to test whether the information content of a document or document subset has been changed. This is done by comparing the canonical form of the original document before application processing with the canonical form of the document result of the application processing.

For example, a digital signature over the canonical form of an XML document or document subset would allow the signature digest calculations to be oblivious to changes in the original document's physical representation, provided that the changes are defined to be logically equivalent by the XML 1.0 or Namespaces in XML 1.0. During signature generation, the digest is computed over the canonical form of the document. The document is then transferred to the relying party, which validates the signature by reading the document and computing a digest of the canonical form of the received document. The equivalence of the digests computed by the signing and relying parties (and hence the equivalence of the canonical forms over which they were computed) ensures that the information content of the document has not been altered since it was signed.

Note: Although not stated as a requirement on implementations, nor formally proved to be the case, it is the intent of this specification that if the text generated by canonicalizing a document according to this specification is itself parsed and canonicalized according to this specification, the text generated by the second canonicalization will be the same as that generated by the first canonicalization.

1.3 Limitations

Two XML documents may have differing information content that is nonetheless logically equivalent within a given application context. Although two XML documents are equivalent (aside from limitations given in this section) if their canonical forms are identical, it is not a goal of this work to establish a method such that two XML documents are equivalent if and only if their canonical forms are identical. Such a method is unachievable, in part due to application-specific rules such as those governing unimportant whitespace and equivalent data (e.g. <color>black</color> versus <color>rgb(0,0,0)</color>). There are also equivalencies established by other W3C Recommendations and Working Drafts. Accounting for these additional equivalence rules is beyond the scope of this work. They can be applied by the application or become the subject of future specifications.

The canonical form of an XML document may not be completely operational within the application context, though the circumstances under which this occurs are unusual. This problem may be of concern in certain applications since the canonical form of a document and the canonical form of the canonical form of the document are equivalent. For example, in a digital signature application, it cannot be established whether the operational original document or the non-operational canonical form was signed because the canonical form can be substituted for the original document without changing the digest calculation. However, the security risk only occurs in the unusual circumstances described below, which can all be resolved or at least detected prior to digital signature generation.

The difficulties arise due to the loss of the following information not available in the data model:

1. base URI, especially in content derived from the replacement text of external general parsed entity references
2. notations and external unparsed entity references
3. attribute types in the document type declaration

In the first case, note that a document containing a relative URI [URI] is only operational when accessed from a specific URI that provides the proper base URI. In addition, if the document contains external general parsed entity references to content containing relative URIs, then the relative URIs will not be operational in the canonical form, which replaces the entity reference with internal content (thereby implicitly changing the default base URI of that content). Both of these problems can typically be solved by adding support for the xml:base attribute [XMLBASE] to the application, then adding appropriate xml:base attributes to document element and all top-level elements in external entities. In addition, applications often have an opportunity to resolve relative URIs prior to the need for a canonical form. For example, in a digital signature application, a document is often retrieved and processed prior to signature generation. The processing should create a new document in which relative URIs have been converted to absolute URIs, thereby mitigating any security risk for the new document.

In the second case, the loss of external unparsed entity references and the notations that bind them to applications means that canonical forms cannot properly distinguish among XML documents that incorporate unparsed data via this mechanism. This is an unusual case precisely because most XML processors currently discard the document type declaration, which discards the notation, the entity's binding to a URI, and the attribute type that binds the attribute value to an entity name. For documents that must be subjected to more than one XML processor, the XML design typically indicates a reference to unparsed data using a URI in the attribute value.

In the third case, the loss of attribute types can affect the canonical form in different ways depending on the type. Attributes of type ID cease to be ID attributes. Hence, any XPath expressions that refer to the canonical form using the id() function cease to operate. The attribute types ENTITY and ENTITIES are not part of this case; they are covered in the second case above. Attributes of enumerated type and of type ID, IDREF, IDREFS, NMTOKEN, NMTOKENS, and NOTATION fail to be appropriately constrained during future attempts to change the attribute value if the canonical form replaces the original document during application processing. Applications can avoid the difficulties of this case by ensuring that an appropriate document type declaration is prepended prior to using the canonical form in further XML processing. This is likely to be an easy task since attribute lists are usually acquired from a standard external DTD subset, and any entity and notation declarations not also in the external DTD subset are typically constructed from application configuration information and added to the internal DTD subset.

While these limitations are not severe, it would be possible to resolve them in a future version of XML canonicalization if, for example, a new version of XPath were created based on the XML Information Set [XML-INFOSET] currently under development at the W3C.

1.4 Requirements for 2.0

Canonical XML 2.0 solves many of the major issues that have been identified by implementers with Canonical XML 1.0 [XML-C14N] and 1.1 [XML-C14N11].

2.1 Data Model

The input to the canonicalization algorithm consists of an XML document subset, and set of options. The XML document subset can be expressed in two ways, with a DOM model or a Stream model.

In the DOM model the XML subset is expressed as:

• Inclusion List: Either the document Node D or a list of one or more element nodes E1, E2, ... En.
  (If out of this list, one element node Ei is a descendant of another Ej, then that element node Ei is ignored.)
• Exclusion List (optional): A list of zero or more element nodes E1, E2, ... Em and a list of zero or more attribute nodes A1, A2, ... AM.
  These attribute nodes should not be namespace declaration or attributes in the xml namespace.

The element nodes in the Inclusion list are also referred as apex nodes.

Note:This input model is a very limited form of the generic XPath Nodeset that was the input model for Canonical XML 1.x. It is designed to be simple and allow for a high performance algorithm, while still supporting the most essential use cases. Specifically:

• This model does not support re-inclusion; i.e. all the exclusions are applied after all the inclusions. It is effectively a simplified form of the XPath Filter 2 model [XMLDSIG-XPATH-FILTER2] with one intersect followed by one optional subtract operation. Re-inclusion complicates the canonicalization algorithm, especially in the areas of namespace and xml attribute inheritance.
• Exclusion is limited to complete subtrees and attribute nodes. Other kinds of nodes (text, comment, PI) cannot be excluded.
• Attribute exclusion is also limited, such that namespace declaration and attributes from the xml namespace cannot be excluded.
• Some examples of subsets that were were permitted in the Canonical XML 1.x, but not in this new version:
  • A subset consisting of a single attribute all by itself.
  • A subset consisting of an attribute without its owner element.
  • A subset consisting of a text node all by itself.
  • A subset consisting of a text node without its parent node.
  • A subset consisting of an element without some of its text node children.

Note: Canonical XML 2.0, unlike earlier versions, does not support direct input of an octet stream. The transformation of such a stream into the input model required by this specification is application-specific and should be defined in specifications that reference or make use of this one.

2.2 Parameters

Instead of separate algorithms for each variant of canonicalization, this specification takes the approach of a single algorithm subject to a variety of parameters that change its behavior to address specific use cases.

The following is a list of the logical parameters supported by this algorithm. The actual serialization that expresses the parameters in use may be defined as appropriate to specific applications of this specification (e.g., the <ds:CanonicalizationMethod> element in [XMLDSIG-CORE2]).

The defaults are chosen for equivalence to Canonical XML 1.1 with comments ignored.

2.3 Processing Model

The basic canonicalization process consist of traversing the tree and outputting octets for each node.

Input: The XML subset consisting of an Inclusion list and an Exclusion list.

Processing

• Sort inclusion list by document order: If inclusion list only has the document node D there is nothing to sort. Otherwise remove all element nodes Ei that are descendants of some other element node in the inclusion list. Then sort the remaining element nodes E1, E2, ...En by document order.
• Canonicalize each subtree For each element node Ei or document node D in the sorted list, do a depth first traversal to visit all the descendant nodes in the Ei subtree, and canonicalize each one of them. While traversing, if the current node is an element and that element is in the exclusion list, prune the traversal, i.e skip over that element and all its descendants.

During traversal of each subtree, generate the canonicalized text depending on the node type as follows:

• Root Node- Ignore the byte order mark, XML declaration, nor anything from within the document type declaration. Traverse through the children.

• Element Nodes- The canonicalized result is an open angle bracket (<), the element QName, the result of processing the namespaces, the result of processing the attributes, a close angle bracket (>), traverse the child nodes of the element, an open angle bracket (<), a forward slash (/), the element QName, and a close angle bracket (>). Note if the prefix rewriting parameter is set, the QNames will be written with the changed prefixes.

• Attribute Nodes- a space, the node's QName, an equals sign, an open quotation mark (double quote), the modified string value, and a close quotation mark (double quote). The string value of the node is modified by replacing all ampersands (&) with &, all open angle brackets (<) with <, all quotation mark characters with ", and the whitespace characters #x9, #xA, and #xD, with character references. The character references are written in uppercase hexadecimal with no leading zeroes (for example, #xD is represented by the character reference 
).

  If the prefix rewriting parameter is set, and the attribute name has a namespace prefix, the prefix is changed to the rewritten prefix. Also with prefix rewriting enabled, the attribute content is treated specially if the attribute is among those enumerated for the QNameAware option. If so, the QName or [CURIE] value of the attribute is rewritten with the new prefix.

• Namespace Nodes- Take the ordered list of namespace nodes resulting from namespace processing, and process each of the namespace node N in the same way as an attribute node.

• Text Nodes- the string value, except all ampersands are replaced by &, all open angle brackets (<) are replaced by <, all closing angle brackets (>) are replaced by >, and all #xD characters are replaced by 
.
  If parameter TrimTextNodes is true and there is no xml:space="preserve" declaration in context, trim the leading and trailing space. E.g. trim <A> <B/> to <A><B/> and trim <A> this is text </A> to <A>this is text</A>.

  Note: The DOM parser might have split up a long text node into multiple adjacent text nodes, some of which may be empty. Be aware when trimming whitespace in such cases; the net result should be equivalent to doing so as if the adjacent text nodes were concatenated.

  If the prefix rewriting parameter is set, and if the parent element node is among those enumerated for the QNameAware option, then the QName or CURIE value of the text node is rewritten with the new prefix.

• Processing Instruction (PI) Nodes- The opening PI symbol (<?), the PI target name of the node, a leading space and the string value if it is not empty, and the closing PI symbol (?>). If the string value is empty, then the leading space is not added. Also, a trailing #xA is rendered after the closing PI symbol for PI children of the root node with a lesser document order than the document element, and a leading #xA is rendered before the opening PI symbol of PI children of the root node with a greater document order than the document element.

• Comment Nodes- Nothing if generating canonical XML without comments. For canonical XML with comments, generate the opening comment symbol (<!--), the string value of the node, and the closing comment symbol (-->). Also, a trailing #xA is rendered after the closing comment symbol for comment children of the root node with a lesser document order than the document element, and a leading #xA is rendered before the opening comment symbol of comment children of the root node with a greater document order than the document element. (Comment children of the root node represent comments outside of the top-level document element and outside of the document type declaration).

Note although some XML models such as DOM don't distinguish namespace declarations from attributes, Canonicalization needs to treat them separately. In this document, attribute nodes that are actually namespace declarations are referred as "namespace nodes", other attributes are called "attribute nodes".

2.4 The Need for Exclusive XML Canonicalization

In some cases, particularly for signed XML in protocol applications, there is a need to canonicalize a subdocument in such a way that it is substantially independent of its XML context. This is because, in protocol applications, it is common to envelope XML in various layers of message or transport elements, to strip off such enveloping, and to construct new protocol messages, parts of which were extracted from different messages previously received. If the pieces of XML in question are signed, they need to be canonicalized in a way such that these operations do not break the signature but the signature still provides as much security as can be practically obtained.

<n1:elem1 xmlns:n1="http://b.example">
    content
</n1:elem1>

<n0:pdu xmlns:n0="http://a.example">
   <n1:elem1 xmlns:n1="http://b.example">
       content
   </n1:elem1>
</n0:pdu>

/descendant::n1:elem1

<n1:elem1 xmlns:n0="http://a.example"
          xmlns:n1="http://b.example">
    content
</n1:elem1>

<n0:local xmlns:n0="foo:bar" xmlns:n3="ftp://example.org">
   <n1:elem2 xmlns:n1="http://example.net">
       <n3:stuff xmlns:n3="ftp://example.org"/>
   </n1:elem2>
</n0:local>

<n2:pdu xmlns:n1="http://example.com" xmlns:n2="http://foo.example">
   <n1:elem2 xmlns:n1="http://example.net">
       <n3:stuff xmlns:n3="ftp://example.org"/>
   </n1:elem2>
</n2:pdu>

/descendant::n1:elem2

<n1:elem2 xmlns:n0="foo:bar" xmlns:n3="ftp://example.org" xmlns:n1="http://example.net">
    <n3:stuff></n3:stuff>
</n1:elem2>

<n1:elem2 xmlns:n1="http://example.net" xmlns:n2="http://foo.example">
    <n3:stuff xmlns:n3="ftp://example.org"></n3:stuff>
</n1:elem2>

<n1:elem2 xmlns:n1="http://example.net">
    <n3:stuff xmlns:n3="ftp://example.org"></n3:stuff>
</n1:elem2>

2.5 Namespace Processing

As part of the canonicalization process, while traversing the subtree, use the following algorithm to look at all the namespace declarations in an element, and decide which ones to output.

<wsse:Security  
  xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd"
  xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
    <wsse:UserName wsu:Id="i1">
        ...
    </wsse:UserName>
    <wsse:Timestamp wsu:Id="i2">
        ...
    </wsse:Timestamp>
<wsse:Security>

<wsse:Security 
  xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
    <wsse:UserName
      xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
      wsu:Id="i1">
        ...
    </wsse:UserName>
    <wsse:Timestamp
      xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
      wsu:Id="i2">
        ...
    </wsse:Timestamp>
</wsse:Security>

<n0:Security
  xmlns:n0="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
    <n0:UserName
      xmlns:n1="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
      n1:Id="i1">
        ...
    </n0:UserName>
    <n0:Timestamp
      xmlns:n2="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd"
      n2:Id="i1">
        ...
    </n0:Timestamp>
</n0:Security>

<n533be3d902dc7f54d5027ddd5917639d584e9d38:Security 
  xmlns:n533be3d902dc7f54d5027ddd5917639d584e9d38:="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd">
    <n533be3d902dc7f54d5027ddd5917639d584e9d38:UserName
      xmlns:ne2891a804ace8fbcc4a500f1dbc94cf01e38e023="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd" 
      ne2891a804ace8fbcc4a500f1dbc94cf01e38e023:Id="i1">
        ...
    </n533be3d902dc7f54d5027ddd5917639d584e9d38:UserName>
    <n533be3d902dc7f54d5027ddd5917639d584e9d38:Timestamp
      xmlns:ne2891a804ace8fbcc4a500f1dbc94cf01e38e023="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd" 
      ne2891a804ace8fbcc4a500f1dbc94cf01e38e023:Id="i2">
        ...
    </n533be3d902dc7f54d5027ddd5917639d584e9d38:Timestamp>
</n533be3d902dc7f54d5027ddd5917639d584e9d38:Security>

2.6 Attribute processing

Note: namespace declarations are not considered as attributes, they are processed separately as namespace nodes.

Processing the attributes of an element E consists of the following steps:

• If E is an apex node, then examine all ancestor element nodes of E for the nearest occurrences of simple inheritable attributes in the xml namespace, such as xml:lang and xml:space that are not already present in E's attributes. Then temporarily add these attributes to E's attribute list.
  (Do this step only if the parameter XmlAncestors is set to "inherit".)

  The xml:base attribute is not a simple inheritable attribute and requires special processing beyond a simple redeclaration. Collect the values of xml:base for all of E's ancestors, starting with the document root element, and including E itself into an ordered list. If there are two or more values in the list, combine them two at a time starting from the beginning, using the join-URI-references function. E.g. if the list has X1,X2, ... Xm, then join X1 and X2 first, then join the result with X3 and so on.
  (Do this step only if the parameter XmlAncestors is set to "inherit").

• Ignore any attributes that are present in the exclusion list. However note that namespace nodes and xml: attributes cannot be excluded.
• Sort all the attribute in increasing lexicographic order with namespace URI as the primary key and local name as the secondary key (an empty namespace URI is lexicographically least).
• If the PrefixRewrite option is set to other than "none", modify the QNames for the attribute name to use the new prefixes. Also, if the attribute is among those enumerated for the QNameAware option, then change its QName or CURIE value to use the new prefix.

2.7 join-URI-References function

The join-URI-References function takes xml:base attribute values from all the ancestor elements and combines them to create a value for an updated xml:base attribute. A simple method for doing this is similar to that found in sections 5.2.1, 5.2.2 and 5.2.4 of RFC 3986 with the following modifications:

• Perform RFC 3986 section 5.2.1. "Pre-parse the Base URI" modified as follows.
  • The scheme component is not required in the base URI (Base). (i.e. Base.scheme may be null)
  • Replace a trailing ".." segment with "../" segment before processing.
• Section 5.2.4. "Remove Dot Segments" is modified as follows:
  • Keep leading "../" segments
  • Replace multiple consecutive "/" characters with a single "/" character.
  • Append a "/" character to a trailing ".." segment
• The "Remove Dot Segments" algorithm is modified to ensure that a combination of two xml:base attribute values that include relative path components (i.e., path components that do not begin with a '/' character) results in an attribute value that is a relative path component.
• Perform RFC 3986 section 5.2.2. "Transform References" modified as follows to ignore the fragment part of R
  • After parsing R set R.fragment = null

• "abc/" and "../" should result in ""
• "../" and "../" are combined as "../../" and the result is "../../"
• ".." and ".." are combined as "../../" and the result is "../../"

3.1 Use of Canonical XML 2.0 in XML Signature 2.0

Exclusive Canonicalization may be used as a canonicalization algorithm in XML Digital Signature [XMLDSIG-CORE2], via the <ds:CanonicalizationMethod>.

Identifier:

http://www.w3.org/2010/xml-c14n2

Canonical XML 2.0 supports a set of parameters, as enumerated in Canonicalization Parameters. All parameters are optional and have default values. When used in conjunction with the <ds:CanonicalizationMethod> element, each parameter is expressed with a dedicated child element. They can be present in any order. A schema definition for each parameter follows:

  Schema Definition:
  <schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
           xmlns="http://www.w3.org/2010/xml-c14n2"
           targetNamespace="http://www.w3.org/2010/xml-c14n2"
           version="0.1" elementFormDefault="qualified">

    <xs:element name="ExclusiveMode" type="xs:boolean"/>
    
    <xs:element name="InclusiveNamespaces">
      <xs:complexType>
        <xs:attribute name="PrefixList">
          <xs:simpleType>
            <xs:list itemType="string" /> 
          </xs:simpleType>
        </xs:attribute>
      </xs:complexType>
    </xs:element>
    
    <xs:element name="IgnoreComments" type="xs:boolean"/>
    
    <xs:element name="TrimTextNodes" type="xs:boolean"/>
    
    <xs:element name="Serialization">
      <xs:simpleType>
        <xs:restriction base="xs:string">
          <xs:enumeration value="XML"/>
          <xs:enumeration value="EXI"/>
        </xs:restriction>
      </xs:simpleType>
    </xs:element>
    
    <xs:element name="PrefixRewrite">
      <xs:simpleType>
        <xs:restriction base="xs:string">
          <xs:enumeration value="none"/>
          <xs:enumeration value="sequential"/>
          <xs:enumeration value="derived"/>
        </xs:restriction>
      </xs:simpleType>
    </xs:element>
    
    <xs:element name="SortAttributes" type="xs:boolean"/>
    
    <xs:element name="XmlAncestors">
      <xs:simpleType>
        <xs:restriction base="xs:string">
          <xs:enumeration value="none"/>
          <xs:enumeration value="inherit"/>
        </xs:restriction>
      </xs:simpleType>
    </xs:element>
     
    <xs:element name="QNameAware">
      <xs:complexType>
        <xs:choice maxOccurs="unbounded">
          <xs:element ref="Element"/>
          <xs:element ref="QualifiedAttr"/>
          <xs:element ref="UnqualifiedAttr"/>
        <xs:sequence>
      </xs:complexType>
    </xs:element>
    
    <xs:element name="Element">
      <xs:complexType>
        <xs:attribute name="Name" type="xs:NCName" use="required"/>
        <xs:attribute name="NS" type="xs:anyURI"/>
      </xs:complexType>
    </xs:element>
    
    <xs:element name="QualifiedAttr">
      <xs:complexType>
        <xs:attribute name="Name" type="xs:NCName" use="required"/>
        <xs:attribute name="NS" type="xs:anyURI"/>
      </xs:complexType>
    </xs:element>
    
    <xs:element name="UnqualifiedAttr">
      <xs:complexType>
        <xs:attribute name="Name" type="xs:NCName" use="required"/>
        <xs:attribute name="ParentName" type="xs:NCName" use="required"/>
        <xs:attribute name="ParentNS" type="xs:anyURI"/>
      </xs:complexType>
    </xs:element>


   </schema>

3.2 Use of Canonical XML 2.0 in XML Encryption 1.1

4.1 canonicalize()

canonicalize(list of subtree, list of exclusion elements and attributes, properties)
{
   put the exclusion elements and attributes in hash table for easier lookup
   
   sort the multiple subtrees by document order
   
   for each subtree
      canonicalizeSubtree(subtree) 
}

4.2 canonicalizeSubtree()

Canonicalize an individual subtree.

For efficiency the routines below maintain two contexts

• namespaceContext: namespaceContext is a hash table of prefix -> (uri, hasBeenOutput, newPrefix).
  • uri is the namespace URI that this prefix maps to.
  • hasBeenOutput a boolean flag that indicates whether that namespace declaration has been output
  • newPrefix the rewritten value of the prefix.
  At the beginning of the canonicalization initialize this to contain only entry - the default namespace mapped to an empty URI, and hasBeenOutput = true. A prefix value of "" can be used to denote the default namespace.
• xmlattribContext: xmlattribContext is a hash table of name -> value.

canonicalizeSubtree(node)
{
   initialize namespaceContext to contain the default prefix, mapped
   to an empty URI, and hasBeenOutput to true 
   
   if (node is the document node or a document root element) 
   {
      // (whole document is being processed, no ancestors to worry about)
      call processNode(node, namespaceContext)
   }
   else
   {
      starting from the element, walk up the tree to collect a list of
      ancestors 
    
      for each of this ancestor elements starting with the document
      root, but not including the element itself 
        addNamespaces(ancestorElem, namespaceContext)

      initialize xmlattribContext to empty

      for each of this ancestor elements starting with the document
      root, and also including the element itself 
        addXMLAttributes(ancestorElem, xmlattribContext)
      
      if there are any attributes in xmlattribContext 
         temporarily add/replace these XML attributes in node
            
      processNode(node, namspaceContext)
      
      restore the original XML attributes
   }   
}

4.3 processNode()

processNode(node, namespaceContext)
{
  call the appropriate function - processDocument, processElement, processTextNode, ... depending on the node type.
}

4.4 processDocument()

processDocument(document, namespaceContext)
{
  Loop through all child nodes and call
    processNode(child, namespaceContext)
}

4.5 processElement()

processElement(element, namespaceContext)
{
  if this exists in the exclusion hash table
    return
    
  make of copy of xmlattribContext and namespaceContext
  //(by copying, any changes made can be undone when this function returns)
  
  nsToBeOutputList = processNamespaces(element, namespaceContext)
  
  output('<')
  if PrefixRewrite is sequential or digest, temporatily modify the QName to have the new prefix value as determined from the namespaceContext
 
  output(element QName)  

  for each of the namespaces in the nsToBeOutputList
    output this namespace declaration 
    
  sort each of the non namespaces attributes by URI first then attribute name.
  output each of these attributes with original QName or a modifiedQName if PrefixRewrite is true
  
  output('>')
  
  Loop through all child nodes and call
    processNode(child, namespaceContext)
  
  output('</')
  output(element QName)
  output('>')
  
  restore xmlattribContext and namespaceContext
}

4.6 processText()

processText(textNode)
{
  if this text node is outside document root
     return
     
  in the text replace 
    all ampersands by &, 
    all open angle brackets (<) by &lt;, 
    all closing angle brackets (>) by &gt;, 
    and all  #xD characters by &#xD;.
    
  If TrimTextNodes is true and there is no xml:space="preserve" declaration in scope
    trim leading and trailing space
      
  output(text)
}                    

Note: The DOM parser might have split up a long text node into multiple adjacent text nodes, some of which may be empty. In that case be careful when trimming the leading and trailing space - the net result should be same as if it the adjacent text nodes were concatenated into one

4.7 processPI()

processPI(piNode)
{
  if after document node
    output('#xA')
    
  output('<?')
  output(the PI target name of the node)
  output(a leading space)
  output(the PI string value)
  output('?>') 

  if before document node
    output('#xA')
}                     

4.8 processComment()

processComment(commentNode)
{
  if ignoreComments
    return
    
  if after document node
    output('#xA')
    
  output('<!--')
  output(string value of node)
  output('-->')

  if before document node
    output('#xA')
}

4.9 addNamespaces()

addNamespaces(element, namespaceContext)
{
  for each the explicit and implicit namespace declarations in the element
  {
     if there is already a declaration for this prefix, and this
     declaration is different from existing declaration 
     overwrite the URI , and set hasBeenOutput to false
      
     if there is no entry for this prefix
     add an entry for this URI, and hasBeenOutout to false
         
  } 
}

4.10 processNamespaces()

processNamespaces(element, namespaceContext)
{
  addNamespaces(element, namespaceContext)
  
  initialize nsToBeOutputList to empty list
  
  for each prefix in the namespaceContext for which hasBeenOutput is false
  {
     if ExclusiveMode and this prefix is not in the inclusiveNamespacesList
     {
         if the prefix is visibly utilized by this element
             add the prefix to the nsToBeOutputList and set
            hasBeenOutput to true 
     }
     else
         add the prefix to the nsToBeOutputList and set hasBeenOutput to true    
  }
  
  if (PrefixRewrite is none)
  {
    sort the nsToBeOutputList by the prefix
  }
  else if (PrefixRewrite is sequential) 
  {
    sort the nsToBeOutputList by URI
    assign new prefix values "nN" to each prefix in this
    nsToBeOutputList where N represents an incremented counter value ,
    i.e. n0, n1, n2 .. 
    // the counter should be set to 0 in the beginning of the canonicalization
    // note: prefix numbers are assigned in the order that the
    prefixes are present in nsToBeOutputList 
  }
  else if (PrefixRewrite in digest)
  {
    sort the nsToBeOutputList by URI
    assign new prefix values "nD" to each prefix in this nsToBeOutputList where
      D represents the SHA1 digest of the URI represented as a hex string
  }
  
  return nsToBeOutputList    
}

4.11 addXMLAttributes()

addXMLAttributes(element, xmlattribContext)
{
   for each of the xml: attributes of this element
   {

      case xml:lang attribute 
        if XmlAncestors is inherit then store this attribute value, else do nothing

      case xml:space attribute 
        if XmlAncestors is inherit then store this attribute value, else do nothing

      case xml:base attribute 
        if XmlAncestors is inherit, and there is a previous value of xml:base
           then do a "join-URI-References" to combine the new value and the old value 
        else do nothing
   } 
}