05 February 2004

Appendix B: Namespaces Algorithms

Editors:
Arnaud Le Hors, IBM
Elena Litani, IBM

Table of contents

This appendix contains several namespace algorithms, such as namespace normalization algorithm that fixes namespace information in the Document Object Model to produce a namespace well-formed document. If [XML 1.0] is in use (see Document.xmlVersion) the algorithms conform to [XML Namespaces], otherwise if [XML 1.1] is in use, algorithms conform to [XML Namespaces 1.1].

B.1 Namespace normalization

Namespace declaration attributes and prefixes are normalized as part of the normalizeDocument method of the Document interface as if the following method described in pseudo code was called on the document element.

void Element.normalizeNamespaces()
{

  // Pick up local namespace declarations
  // 
  for ( all DOM Level 2 valid local namespace declaration attributes of Element ) 
  {    
      if (the namespace declaration is invalid) 
      {
          // Note: The prefix xmlns is used only to declare namespace bindings and
          // is by definition bound to the namespace name http://www.w3.org/2000/xmlns/.
          // It must not be declared. No other prefix may be bound to this namespace name.         
               
          ==> Report an error.

      } 
      else 
      {
          ==>  Record the namespace declaration
      }
  }


  // Fixup element's namespace
  //
  if ( Element's namespaceURI != null )
  {
    if ( Element's prefix/namespace pair (or default namespace,
         if no prefix) are within the scope of a binding )
    {
      ==> do nothing, declaration in scope is inherited

      See section "B.1.1: Scope of a binding" for an example

    }
    else
    {
      ==> Create a local namespace declaration attr for this namespace,
          with Element's current prefix (or a default namespace, if
          no prefix). If there's a conflicting local declaration
          already present, change its value to use this namespace.

          See section "B.1.2: Conflicting namespace declaration" for an example

          // NOTE that this may break other nodes within this Element's
          // subtree, if they're already using this prefix.
          // They will be repaired when we reach them.
    }
  }
  else
  {
    // Element has no namespace URI:
    if ( Element's localName is null )
    {
       // DOM Level 1 node
       ==> if in process of validation against a namespace aware schema 
           (i.e XML Schema) report a fatal error: the processor can not recover 
           in this situation. 
           Otherwise, report an error: no namespace fixup will be performed on this node.
    }
    else
    {
      // Element has no pseudo-prefix
      if ( there's a conflicting local default namespace declaration
           already present )
      {
        ==> change its value to use this empty namespace.

      }
      // NOTE that this may break other nodes within this Element's
      // subtree, if they're already using the default namespaces.
      // They will be repaired when we reach them.
    }
  }


  // Examine and polish the attributes
  //
  for ( all non-namespace Attrs of Element )
  {
     if ( Attr[i] has a namespace URI )
     {
        if ( attribute has no prefix (default namespace decl does not apply to attributes) 
             OR
             attribute prefix is not declared
             OR
             conflict: attribute has a prefix that conflicts with a binding
                       already active in scope)
        {              
           if (namespaceURI matches an in scope declaration of one or more prefixes) 
           {
               // pick the most local binding available; 
               // if there is more than one pick one arbitrarily

               ==> change attribute's prefix.
           }
           else 
           {
               if (the current prefix is not null and it has no in scope declaration) 
               {
                   ==> declare this prefix
               } 
               else 
               {
                   // find a prefix following the pattern "NS" +index (starting at 1)
                   // make sure this prefix is not declared in the current scope.
                   // create a local namespace declaration attribute

                   ==> change attribute's prefix.
               }
           }           
        }
     }    
     else
     {
        // Attr[i] has no namespace URI
            
        if ( Attr[i] has no localName )
        {
           // DOM Level 1 node
           ==> if in process of validation against a namespace aware schema 
               (i.e XML Schema) report a fatal error: the processor can not recover 
                in this situation. 
                Otherwise, report an error: no namespace fixup will be performed on this node.
        }
        else
        { 
           // attr has no namespace URI and no prefix
           // no action is required, since attrs don't use default
           ==> do nothing 
        }
     }
  } // end for-all-Attrs

  // do this recursively
  for ( all child elements of Element )
  {
    childElement.normalizeNamespaces()
  }
} // end Element.normalizeNamespaces
      

B.1.1 Scope of a binding

Note: This section is informative.

An element's prefix/namespace URI pair is said to be within the scope of a binding if its namespace prefix is bound to the same namespace URI in the [in-scope namespaces] defined in [XML Information Set].

As an example, the following document is loaded in a DOM tree:

<root>
  <parent xmlns:ns="http://www.example.org/ns1"
          xmlns:bar="http://www.example.org/ns2">
    <ns:child1 xmlns:ns="http://www.example.org/ns2"/>
  </parent>
</root>
      

In the case of the child1 element, the namespace prefix and namespace URI are within the scope of the appropriate namespace declaration given that the namespace prefix ns of child1 is bound to http://www.example.org/ns2.

Using the method Node.appendChild, a child2 element is added as a sibling of child1 with the same namespace prefix and namespace URI, i.e. "ns" and "http://www.example.org/ns2" respectively. Unlike child1 which contains the appropriate namespace declaration in its attributes, child2's prefix/namespace URI pair is within the scope of the namespace declaration of its parent, and the namespace prefix "ns" is bound to "http://www.example.org/ns1". child2's prefix/namespace URI pair is therefore not within the scope of a binding. In order to put them within a scope of a binding, the namespace normalization algorithm will create a namespace declaration attribute value to bind the namespace prefix "ns" to the namespace URI "http://www.example.org/ns2" and will attach to child2. The XML representation of the document after the completion of the namespace normalization algorithm will be:

<root>
  <parent xmlns:ns="http://www.example.org/ns1"
          xmlns:bar="http://www.example.org/ns2">
    <ns:child1 xmlns:ns="http://www.example.org/ns2"/>
    <ns:child2 xmlns:ns="http://www.example.org/ns2"/>
  </parent>
</root>
      

To determine if an element is within the scope of a binding, one can invoke Node.lookupNamespaceURI, using its namespace prefix as the parameter, and compare the resulting namespace URI against the desired URI, or one can invoke Node.isDefaultNamespaceURI using its namespace URI if the element has no namespace prefix.

B.1.2 Conflicting namespace declaration

Note: This section is informative.

A conflicting namespace declaration could occur on an element if an Element node and a namespace declaration attribute use the same prefix but map them to two different namespace URIs.

As an example, the following document is loaded in a DOM tree:

<root>
  <ns:child1 xmlns:ns="http://www.example.org/ns1">
    <ns:child2/> 
  </ns:child1>   
</root>
      

Using the method Node.renameNode, the namespace URI of the element child1 is renamed from "http://www.example.org/ns1" to "http://www.example.org/ns2". The namespace prefix "ns" is now mapped to two different namespace URIs at the element child1 level and thus the namespace declaration is declared conflicting. The namespace normalization algorithm will resolved the namespace prefix conflict by modifying the namespace declaration attribute value from "http://www.example.org/ns1" to "http://www.example.org/ns2". The algorithm will then continue and consider the element child2, will no longer find a namespace declaration mapping the namespace prefix "ns" to "http://www.example.org/ns1" in the element's scope, and will create a new one. The XML representation of the document after the completion of the namespace normalization algorithm will be:

<root>
  <ns:child1 xmlns:ns="http://www.example.org/ns2">
    <ns:child2  xmlns:ns="http://www.example.org/ns1"/> 
  </ns:child1>   
</root>
      

B.2 Namespace Prefix Lookup

The following describes in pseudo code the algorithm used in the lookupPrefix method of the Node interface. Before returning found prefix the algorithm needs to make sure that the prefix is not redefined on an element from which the lookup started. This methods ignores DOM Level 1 nodes.

Note: This method ignores all default namespace declarations. To look up default namespace use isDefaultNamespace method.

DOMString lookupPrefix(in DOMString namespaceURI)
{
  if (namespaceURI has no value, i.e. namespaceURI is null or empty string) {
     return null;
  }
  short type = this.getNodeType(); 
  switch (type) { 
        case Node.ELEMENT_NODE: 
        { 
             return lookupNamespacePrefix(namespaceURI, this); 
        } 
        case Node.DOCUMENT_NODE:
        { 
             return getDocumentElement().lookupNamespacePrefix(namespaceURI); 
        } 
        case Node.ENTITY_NODE : 
        case Node.NOTATION_NODE: 
        case Node.DOCUMENT_FRAGMENT_NODE: 
        case Node.DOCUMENT_TYPE_NODE: 
            return null;  // type is unknown  
        case Node.ATTRIBUTE_NODE:
        {
             if ( Attr has an owner Element ) 
             { 
                 return ownerElement.lookupNamespacePrefix(namespaceURI); 
             } 
             return null; 
        } 
        default:
        { 
           if (Node has an ancestor Element )
           // EntityReferences may have to be skipped to get to it 
           { 
                    return ancestor.lookupNamespacePrefix(namespaceURI); 
           } 
            return null; 
        } 
     } 
 } 


DOMString lookupNamespacePrefix(DOMString namespaceURI, Element originalElement){ 
        if ( Element has a namespace and Element's namespace == namespaceURI and 
             Element has a prefix and 
             originalElement.lookupNamespaceURI(Element's prefix) == namespaceURI) 
        { 
             return (Element's prefix); 
        } 
        if ( Element has attributes)
        { 
            for ( all DOM Level 2 valid local namespace declaration attributes of Element )
            {
                if (Attr's prefix == "xmlns" and 
                   Attr's value == namespaceURI and 
                   originalElement.lookupNamespaceURI(Attr's localname) == namespaceURI) 
                   { 
                      return (Attr's localname);
                   } 
            }
        } 

        if (Node has an ancestor Element ) 
           // EntityReferences may have to be skipped to get to it 
        { 
            return ancestor.lookupNamespacePrefix(namespaceURI, originalElement); 
        } 
        return null; 
    } 

B.3 Default Namespace Lookup

The following describes in pseudo code the algorithm used in the isDefaultNamespace method of the Node interface. This methods ignores DOM Level 1 nodes.

boolean isDefaultNamespace(in DOMString namespaceURI)
{
  switch (nodeType) {
  case ELEMENT_NODE:  
     if ( Element has no prefix )
     {
          return (Element's namespace == namespaceURI);
     }
     if ( Element has attributes and there is a valid DOM Level 2 
          default namespace declaration, i.e. Attr's localName == "xmlns" )
     {
	  return (Attr's value == namespaceURI);
     }

     if ( Element has an ancestor Element )
         // EntityReferences may have to be skipped to get to it
     {
          return ancestorElement.isDefaultNamespace(namespaceURI);
     }
     else {
          return unknown (false);
     }    
  case DOCUMENT_NODE:
     return documentElement.isDefaultNamespace(namespaceURI);
  case ENTITY_NODE:
  case NOTATION_NODE:
  case DOCUMENT_TYPE_NODE:
  case DOCUMENT_FRAGMENT_NODE:
     return unknown (false);
  case ATTRIBUTE_NODE:
     if ( Attr has an owner Element )
     {          
          return ownerElement.isDefaultNamespace(namespaceURI);
     }
     else {
          return unknown (false);
     }    
  default:
     if ( Node has an ancestor Element )
         // EntityReferences may have to be skipped to get to it
     {          
          return ancestorElement.isDefaultNamespace(namespaceURI);
     }
     else {
          return unknown (false);
     }    
  }
}
      

B.4 Namespace URI Lookup

The following describes in pseudo code the algorithm used in the lookupNamespaceURI method of the Node interface. This methods ignores DOM Level 1 nodes.

DOMString lookupNamespaceURI(in DOMString prefix) 
{ 
  switch (nodeType) { 
     case ELEMENT_NODE: 
     { 
         if ( Element's namespace != null and Element's prefix == prefix ) 
         { 
               // Note: prefix could be "null" in this case we are looking for default namespace 
               return (Element's namespace);
         } 
         if ( Element has attributes)
         { 
            for ( all DOM Level 2 valid local namespace declaration attributes of Element )
            {
                 if (Attr's prefix == "xmlns" and Attr's localName == prefix ) 
                       // non default namespace
                 { 
                        if (Attr's value is not empty) 
                        {
                          return (Attr's value);
                        }         
                        return unknown (null);                   
                 } 
                 else if (Attr's localname == "xmlns" and prefix == null)
                       // default namespace
                 { 
                        if (Attr's value is not empty) 
                        {
                          return (Attr's value);
                        }         
                        return unknown (null); 
                 } 
           }
         } 
         if ( Element has an ancestor Element ) 
            // EntityReferences may have to be skipped to get to it 
         { 
                   return ancestorElement.lookupNamespaceURI(prefix); 
         } 
         return null; 
     } 
     case DOCUMENT_NODE: 
          return documentElement.lookupNamespaceURI(prefix) 

     case ENTITY_NODE: 
     case NOTATION_NODE: 
     case DOCUMENT_TYPE_NODE: 
     case DOCUMENT_FRAGMENT_NODE: 
           return unknown (null); 

     case ATTRIBUTE_NODE: 
         if (Attr has an owner Element) 
         { 
             return ownerElement.lookupNamespaceURI(prefix); 
         } 
         else 
         { 
             return unknown (null); 
         } 
     default: 
         if (Node has an ancestor Element) 
          // EntityReferences may have to be skipped to get to it 
         { 
             return ancestorElement.lookupNamespaceURI(prefix); 
         } 
         else { 
             return unknown (null); 
         } 
  } 
}