W3C

Canonical XML Version 2.0

W3C Working Draft 04 March 2010

This Version:
http://www.w3.org/TR/2010/WD-xml-c14n2-20100304/
Latest Published Version:
http://www.w3.org/TR/xml-c14n2/
Latest Editor's Draft:
http://www.w3.org/2008/xmlsec/Drafts/c14n-20/
Previous version:
http://www.w3.org/TR/2009/WD-xml-c14n2-20091022/
Latest Recommendation:
http://www.w3.org/TR/xml-c14n2/
Editors:
John Boyer ( IBM (formerly PureEdge Solutions Inc.,Version 1.0) )
Glenn Marcy ( IBM (Version 1.1) )
Pratik Datta ( Oracle )
Frederick Hirsch ( Nokia )

Abstract

Canonical XML Version 2.0 is a major rewrite of Canonical XML Version 1.1 to address issues around performance, streaming, hardware implementation, robustness, minimizing attack surface, determining what is signed and more. It also incorporates an update to Exclusive Canonicalization, effectively a 2.0 version, as well.

Any XML document is part of a set of XML documents that are logically equivalent within an application context, but which vary in physical representation based on syntactic changes permitted by XML 1.0 [XML10] and Namespaces in XML 1.0 [XML-NAMES]. This specification describes a method for generating a physical representation, the canonical form, of an XML document that accounts for the permissible changes. Except for limitations regarding a few unusual cases, if two documents have the same canonical form, then the two documents are logically equivalent within the given application context. Note that two documents may have differing canonical forms yet still be equivalent in a given context based on application-specific equivalence rules for which no generalized XML specification could account.

Canonical XML Version 2.0 is applicable to XML 1.0. It is not defined for XML 1.1.

Status of This Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This is a W3C Working Draft of "Canonical XML Version 2.0".

This document is expected to be further updated based on both Working Group input and public comments.

This document was developed by the XML Security Working Group.

Please send comments about this document to public-xmlsec-comments@w3.org (with public archive).

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. The W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

This document was published by the XML Security Working Group as a Working Draft. This document is intended to become a W3C Recommendation. If you wish to make comments regarding this document, please send them to public-xmlsec@w3.org (subscribe, archives). All feedback is welcome.

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Table of Contents

1. Introduction

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

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

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

1.4.1 Performance

A major factor in performance issues noted in XML Signature is often C14N11 canonicalization. Canonicalization will be slow if the implementation uses the Canonical XML 1.1 specification as a formula without any attempt at optimization. This specification rectifies this problem by incorporating lessons learned from implementation into the specification. Most mature C14N implementations solve the performance problem by inspecting the signature first, to see if it can be canonicalized using a simple tree walk algorithm whose performance is similar to regular XML serialization. If not they fall back to the expensive nodeset based algorithm.

The use cases that cannot be solved by the simple tree walk algorithm are mostly edge use cases. This specification restricts the input of the canonicalization algorithm, so that implementations can always use the simple tree walk algorithm.

C14N 1.x uses an "XPath 1.0 Nodeset" to describe a document subset. This is the root cause of the performance problem and can be solved by not using a Nodeset. This version of the spec does not use a nodeset, visits each node exactly once, and it only visits the nodes that are being canonicalized.

1.4.2 Streaming

A streaming implementation is required to be able to process very large documents without holding it all in memory, i.e. it should be able to process the document one chunk at a time.

1.4.3 Robustness

Whitespace handling was a common cause of signature breakages. XML libraries allow one to "pretty print" an XML document, and most people wrongly assume that the white space introduced by pretty printing will be removed by canonicalization but that is not the case. This specification adds three techniques to improve robustness:

  1. Remove leading and trailing whitespace from text nodes,
  2. Allow for QNames in content especially in the xsi:type attribute,
  3. Rewrite prefixes

1.4.4 Simplicity

C14N 1.x algorithms are complex and depend a full XPath library. This makes it very hard for scripting languages to use XML Signatures. This specification addresses this issue by not using the complex nodeset model, and therefore not relying completely on XPath - also it introduces a minimal canonicalization mode.

2. XML Canonicalization

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 a DOM model the XML subset is expressed as

The XML subset is computed by at first taking all the nodes in the Inclusion list and their descendant. From this list remove all the nodes that are in the Exclusion list and their descendants.

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 a high performance algorithm, while still allowing the essential use cases. Specifically

2.2 Parameters

Instead of separate algorithms for each variant of canonicalization, this specification goes with the approach of a single algorithm, which does slightly different things depending on the parameters.

Name Values Description Default
exclusiveMode true or false whether to do inclusive or exclusive dealing of namespaces. In exclusive mode the inclusiveNamespacePrefixList parameter can be specified listing the prefixes that are to be treated in an inclusive mode false
inclusiveNamespacePrefixList space separated list of prefixes list of prefixes to be treated inclusively. Special token #default indicates the default namespace. empty
ignoreComments true or false whether to ignore comments during canonicalization true
trimTextNodes true or false whether to trim (i.e. remove leading and trailing whitespaces) all text nodes when canonicalizing. Adjacent text nodes must be coalesced prior to trimming. If an element has an xml:space="preserve" attribute, then text nodes descendants of that element are not trimmed regardless of the value of this parameter. false
serialization XML or EXI whether to do the normal XML serialization, or do an EXI serialization - which is useful if the original document to be signed is already in EXI format. XML
prefixRewrite none, sequential, derived with none, prefixes are not changed, with sequential prefixes are changed to n1, n2, n3 ... and with derived, each prefix is changed to nSuffix, where the suffix is derived by doing a digest of the namespace URI. none
sortAttributes true or false whether the attributes need to be sorted before canonicalization. In some environments the order of attributes changes in transit so sorting is important. true
ignoreDTD true or false if set to true, ignore the DTD completely, which means do not normalize attributes, do not look into entity definitions, do not add default attributes to each element false
expandEntities true or false if set to true ignore all entity declarations, and expand only the predefined entites (lt, gt, amp, apos, quot) and character references. (Entity declarations are potential attack points, [BradHill] mentions an entity that is 2 GB is length, also expanding external entities can lead to cross site scripting attacks) true
xmlBaseAncestors inherit, none, combine whether to inherit xml:base attributes from ancestors (like C14N 1.0) or not (like Exc C14n 1.0) or combine them (like C14n 1.1) combine
xmlIdAncestors inherit, none whether to inherit xml:id attributes from ancestors (like C14N 1.0) or not (like C14N 1.1 or Exc C14n 1.0) none
xmlLangAncestors inherit, none whether to inherit xml:lang attributes from ancestors (like C14N 1.0 and C14n 1.1) or not (Exc C14n 1.0) inherit
xmlSpaceAncestors inherit, none whether to inherit xml:space attributes from ancestors (like C14N 1.0 and C14n 1.1) or not (Exc C14n 1.0) inherit
xsiTypeAware true or false if set to true, looks for namespace prefix usages in xsi:type attributes as well, otherwise xsi:type attributes are treated just like regular attributes. false

The defaults are set to result in canonical 1.1 with no comments.

Implementation are not required to support all possible combinations of these parameters, instead these parameter are grouped into various "named parameter sets". Implementation can choose to support one or more of these.

2.3 Processing Model

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

Input: The XML subset conisting of an Inclusion list and an exlusion list.

Processing

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

Note although some xml models like 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.

2.4.1 A Simple Example

As a simple example of the type of problem that changes in XML context can cause for signatures, consider the following document:

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

this is then enveloped in another document:

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

The first document above is in canonical form. But assume that document is enveloped as in the second case. The subdocument with elem1 as its apex node can be extracted from this second case with an XPath expression such as:

 /descendant::n1:elem1

The result of performing inclusive canoicalization to the resulting xml subset is the following (except for line wrapping to fit this document):

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

Note that the n0 namespace has been included by inclusive canoncalization because it includes namespace context. This change which would break a signature over elem1 based on the first version.

2.4.2 General Problems with re-Enveloping

As a more complete example of the changes in canonical form that can occur when the enveloping context of a document subset is changed, consider the following document:

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

   </n0:local>

And the following which has been produced by changing the enveloping of elem2:

   <n2:pdu xmlns:n1="http://example.com"
           xmlns:n2="http://foo.example"
           xml:lang="fr"
           xml:space="retain">
      <n1:elem2 xmlns:n1="http://example.net"
                xml:lang="en">
          <n3:stuff xmlns:n3="ftp://example.org"/>

      </n1:elem2>
   </n2:pdu>

Assume an xml subset produced from each case by applying the following XPath expression:

 /descendant::n1:elem2

Applying inclusive canonicalization to the xml subset produced from the first document yields the following serialization (except for line wrapping to fit in this document):

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

       <n3:stuff></n3:stuff>
   </n1:elem2>

However, although elem2 is represented by the same octet sequence in both pieces of external XML above, the Canonical XML version of elem2 from the second case would be (except for line wrapping so it will fit into this document) as follows:

   <n1:elem2 xmlns:n1="http://example.net"
             xmlns:n2="http://foo.example"
             xml:lang="en"
             xml:space="retain">

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

Note that the change in context has resulted in lots of changes in the subdocument as serialized by the inclusive canonicalization. In the first example, n0 had been included from the context and the presence of an identical n3 namespace declaration in the context had elevated that declaration to the apex of the canonicalized form. In the second example, n0 has gone away but n2 has appeared, n3 is no longer elevated, and an xml:space declaration has appeared, due to changes in context. But not all context changes have effect. In the second example, the presence at ancestor nodes of an xml:lang and n1 prefix namespace declaration have no effect because of existing declarations at the elem2 node.

On the other hand, using Exclusive canonicalization with xmlLangAncestors="none" and xmlSpaceAncestors="none" the physical form of elem2 as extracted by the XPath expression above is (except for line wrapping so it will fit into this document) as follows:

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

in both cases.

2.5 Namespace Processing

The following concepts are used in Namespace processing:

Explicit and Implicit namespace declarations
In DOM, there is no special node for namespace declarations, they are just present as regular Attribute nodes. An "explicit" namespace declaration is an Attribute node whose prefix is "xmlns" and whose locaName is the prefix begin declared.
DOM also allows declaring a namespace "implicitly", i.e. if a new DOM element or attribute is constructed using the createElementNS and createAttributeNS methods, then DOM adds a namespace declaration automatically when serializing the document.
Apex nodes
An apex node is an element node in a document subset having no element node ancestor in the document subset.
Default namespace
The default namespace is declared by xmlns="...". To make the algorithm simpler this will be treated as a namespace declaration whose prefix value is "" i.e. an empty string.
Visibility utilized
This concept is required for exclusive canonicalization. An element E in the document subset visibly utilizes a namespace declaration, i.e. a namespace prefix P and bound value V, if
  • The element E itself has a qualified name that uses the prefix P. (Note if an element does not have a prefix, that means it visibily utilizes the default namespace.)
  • An attribute A of that element has a qualified name that uses the prefix P, and that attribute is not in the exclusion list. (Note: unlike elements, if an attribute doesn't have a prefix, its means it is a locally scoped attribute. It does NOT mean that the attribute visibily utilizes the default namespace.)
  • The parameter xsiTypeAware is true, and the element has an xsi:type attribute, and this attribute's value uses this prefix P.
  • (TBD) Some special attribute or text nodes maybe have an XPath, e.g. the IncludedXPath and ExcludedXPath attributes in an XML Signature 2.0 Transform. Any prefixes used in this XPath expression are considered to be visibility utilized.

Use the following algorithm to determine the namespaces to be output for an element E.

  1. Find a list of namespace declarations that are in scope for this element E by looking at namespace declarations in this element and its ancestors.
  2. If in this list, any of the namespace declaration has already been output during the canonicalization of one of the element E's ancestors, say E j, and has not been redeclared since then to a different value, i.e not been redeclared by an element between Ei and E, then remove it from this list.
  3. Of this list, check if there are any prefixes that are to be processed in exclusive mode. This is indicated by parameter exclusiveMode="true" and this prefix being absent from parameter inclusiveNamespacePrefixList. For the prefixes that are to be treated in exclusive mode, check if the prefix is visibily utilized by this element E, and if it is not then remove it.

If the prefixRewrite is specified, then compute new prefixes for all the namespaces declarations in this list, except the prefixes starting with "xml", as follows:

Note: with prefix rewriting the default namespace is never output, i.e. it is also rewritten into a new prefix.

Note: with exclusive canonicalization namespace declarations and output only when they are utilized, this may lead to one declaration being output multiple times, and if prefixRewrite parameter is set to sequential, it may be rewritten to a different value every time.

If sortAttributes="true" which is the default, then sort this list of namespaces by lexicographic(ascending) order of namespace URI.

Output each of these namespace nodes, as specified in the Processing model.

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 consist of

2.7 join-URI-References function

The join-URI-References function takes xml:base attribute values from all the ancestor elements and combines it 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:

The following examples illustrate the modification of the "Remove Dot Segments" algorithm:

3. Use in XML Security

Exclusive Canonicalization may be used as a CanonicalizationMethod algorithm in XML Digital Signature [XMLDSIG-CORE2].

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

Canonical XML 2.0 takes many parameters, these are listed in Canonicalization Parameters. All parameters are optional and have default values. They can be present in any order. Here is the schema definition for them:

  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">
       <complexType">
          <attribute name="PrefixList" type="NMTOKENS"/>
       </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="IgnoreDTD" type="xs:boolean"/>
     <xs:element name="ExpandEntities" type="xs:boolean"/>
     <xs:element name="XmlBaseAncestors">
         <xs:simpleType>
             <xs:restriction base="xs:string">
                 <xs:enumeration value="none"/>
                 <xs:enumeration value="inherit"/>
                 <xs:enumeration value="combine"/>
             </xs:restriction>
         </xs:simpleType>
     </xs:element>
     <xs:element name="XmlIdAncestors">
         <xs:simpleType>
             <xs:restriction base="xs:string">
                 <xs:enumeration value="none"/>
                 <xs:enumeration value="inherit"/>
                 <xs:enumeration value=""/>
             </xs:restriction>
         </xs:simpleType>
     </xs:element>
     <xs:element name="XmlLangAncestors">
         <xs:simpleType>
             <xs:restriction base="xs:string">
                 <xs:enumeration value="none"/>
                 <xs:enumeration value="inherit"/>
             </xs:restriction>
         </xs:simpleType>
     </xs:element>
     <xs:element name="XmlSpaceAncestors">
         <xs:simpleType>
             <xs:restriction base="xs:string">
                 <xs:enumeration value="none"/>
                 <xs:enumeration value="inherit"/>
             </xs:restriction>
         </xs:simpleType>
     </xs:element>
     <xs:element name="XsiTypeAware" type="xs:boolean"/>

   </schema>

4. Pseudocode

This section presents the entire canonicalization algorithm in psuedo code. It is not normative.

4.1 canonicalize()

Top level canonicalize function.
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

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 
        addXmlattribs(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()

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

4.4 processDocument()

Process the Document Node.
processDocument(document, namespaceContext)
{
  Loop through all child nodes and call
    processNode(child, namespaceContext)
}

4.5 processElement()

Process an Element Node.
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()

Process an Text Node.
processTextNode(textNode)
{
  if this text node is outside document root
     return
     
  in the text replace 
    all ampersands by &amp;, 
    all open angle brackets (<) by &lt;, 
    all closing angle brackets (>) by &gt;, 
    and all  #xD characters by &#xD;.
    
  If trimTextNode 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 processPINode()

Process an Processing Instruction (PI) Node.
processPINode(piNode)
{
  if before document node
    output('#xA')
    
  output('<?')
  output(the PI target name of the node)
  output(a leading space)
  output(the PI string value)
  output('?>') 

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

4.8 processCommentNode()

Process an Comment Node.
processCommentNode(commentNode)
{
  if ignoreComments
    return
    
  if before document node
    output('#xA')
    
  output('<!--')
  output(string value of node)
  output('-->')

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

4.9 addNamespaces()

Add namespaces from this element to the namespace context. This function is called for every ancestor element, and also at every element of the subtrees (minus the exclusion elements).
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()

Process the list of namespaces for this element.
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 visibily 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 Base64
      string 
    // refer to presentation by Ed Simon  
  }
  
  return nsToBeOutputList    
}

4.11 addXMLAttribute()

Combine/modify the 4 special xml attributes: xml:id, xml:lang, xml:space and xml:base.
addXMLAttribute(element, xmlattribContext)
{
   for each of the xml: attributes of this element
   {
      case xml:id attribute: 
        if xmlIdAncestors is inherit then store this attribute value, else do nothing

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

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

      case xml:base attribute 
        if xmlBaseAncestors is inherit then store this attribute value,
        else if xmlBaseAncestors is combine, 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
   } 
}

5. Output rules

6. Other ideas considered

7. Processing model for Streaming XML parsers

Unlike DOM parsers which represent XML document as a tree of nodes, streaming parsers represent an XML document as stream of events like "start-element", "end-element", "text" etc. A document subset can also be represented as a stream of events. This stream of events in exactly in the same order as a tree walk, so the above canonicalization algorithm can be also used to canonicalize an event stream.

A. Remove Dot segments

The following informative table outlines example results of the modified Remove Dot Segments algorithm described in Section 2.4.

Input Output
no/.././/pseudo-netpath/seg/file.ext pseudo-netpath/seg/file.ext
no/..//.///pseudo-netpath/seg/file.ext pseudo-netpath/seg/file.ext
yes/no//..//.///pseudo-netpath/seg/file.ext yes/pseudo-netpath/seg/file.ext
no/../yes yes
no/../yes/ yes/
no/../yes/no/.. yes/
../../no/../.. ../../../
no/../.. ../
no/..  
no/../  
/a/b/c/./../../g /a/g
mid/content=5/../6 mid/6
../../.. ../../../
no/../../ ../
..yes/..no/..no/..no/../../../..yes ..yes/..yes
..yes/..no/..no/..no/../../../..yes/ ..yes/..yes/
../.. ../../
../../../ ../../../
.  
./  
./.  
//no/.. /
../../no/.. ../../
../../no/../ ../../
yes/no/../ yes/
yes/no/no/../.. yes/
yes/no/no/no/../../.. yes/
yes/no/../yes/no/no/../.. yes/yes/
yes/no/no/no/../../../yes yes/yes
yes/no/no/no/../../../yes/ yes/yes/
/no/../ /
/yes/no/../ /yes/
/yes/no/no/../.. /yes/
/yes/no/no/no/../../.. /yes/
../../..no/.. ../../
../../..no/../ ../../
..yes/..no/../ ..yes/
..yes/..no/..no/../.. ..yes/
..yes/...no/..no/..no/../../.. ..yes/
..yes/..no/../..yes/..no/..no/../.. ..yes/..yes/
/..no/../ /
/..yes/..no/../ /..yes/
/..yes/..no/..no/../.. /..yes/
/..yes/..no/..no/..no/../../.. /..yes/
/ /
/. /
/./ /
/./. /
/././ /
/.. /
/../.. /
/../../.. /
/../../.. /
//.. /
//..//.. /
//..//..//.. /
/./.. /
/./.././.. /
/./.././.././.. /
.  
./  
./.  
.. ../
../ ../

B. References

Dated references below are to the latest known or appropriate edition of the referenced work. The referenced works may be subject to revision, and conformant implementations may follow, and are encouraged to investigate the appropriateness of following, some or all more recent editions or replacements of the works cited. It is in each case implementation-defined which editions are supported.

B.1 Normative references

[RFC2119]
S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. Internet RFC 2119. URL: http://www.ietf.org/rfc/rfc2119.txt
[XML-C14N]
John Boyer. Canonical XML Version 1.0. 15 March 2001. W3C Recommendation. URL: http://www.w3.org/TR/2001/REC-xml-c14n-20010315
[XML-C14N11]
Glenn Marcy; John Boyer. Canonical XML Version 1.1. 2 May 2008. W3C Recommendation. URL: http://www.w3.org/TR/2008/REC-xml-c14n11-20080502/
[XML-NAMES]
Richard Tobin; et al. Namespaces in XML 1.0 (Second Edition). 16 August 2006. W3C Recommendation. URL: http://www.w3.org/TR/2006/REC-xml-names-20060816/
[XML10]
C. M. Sperberg-McQueen; et al. Extensible Markup Language (XML) 1.0 (Fifth Edition). 10 February 1998. W3C Proposed Edited Recommendation. Revised 5 February 2008 URL: http://www.w3.org/TR/2008/PER-xml-20080205/
[XMLDSIG-CORE2]
Mark Bartel; John Boyer; Pratik Datta et al. XML Signature Syntax and Processing Version 2.0, 4 March 2010. W3C Working Draft. URL: http://www.w3.org/TR/xmldsig-core2/
[XMLDSIG-XPATH-FILTER2]
Merlin Hughes; John Boyer; Joseph Reagle. XML-Signature XPath Filter 2.0. 8 November 2002. W3C Recommendation. URL: http://www.w3.org/TR/2002/REC-xmldsig-filter2-20021108/

B.2 Informative references

[URI]
T. Berners-Lee; R. Fielding; L. Masinter. Uniform Resource Identifiers (URI): generic syntax. January 2005. Internet RFC 3986. URL: http://www.ietf.org/rfc/rfc3986.txt
[XML-INFOSET]
John Cowan; Richard Tobin. XML Information Set (Second Edition). 4 February 2004. W3C Recommendation. URL: http://www.w3.org/TR/2004/REC-xml-infoset-20040204/
[XMLBASE]
Richard Tobin; Jonathan Marsh. XML Base (Second Edition). 28 January 2009. W3C Recommendation. URL: http://www.w3.org/TR/2009/REC-xmlbase-20090128/