09 April 2002

Appendix B: Namespaces Algorithms

Editor:
Arnaud Le Hors, IBM

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()
{
  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 example 1
    }
    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 example 2
          // 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 has a colon in its name )
    {
       if ( Level 2 node )
       {
          ==> report an error 
       }
       else
       {
          // Level 1 node

          if ( Name is not a QName )
          {
             ==> report an error 
          }
          else
          {
             if ( Prefix is bound to something )
             {
                ==> report a warning
             }
             else
             {
                ==> report an error
             }
          }
       }
    }
    else
    {
      // Element has no namespace URI 
      // Element has no pseudo-prefix
      if ( default Namespace in scope is "no namespace" )
      {
        ==> do nothing, we're fine as we stand
      }
      else
      {
        if ( there's a conflicting local default namespace declaration
             already present )
        {
          ==> change its value to use this empty namespace.
          See example 3
        }
        else
        {
          ==> Set the default namespace to "no namespace" by creating or
          changing a local declaration attribute: xmlns="". 
          See example 4
        }
        // 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 ATTRS ////////
  for ( all Attrs of Element )
  {
    if ( Attr[i] has a namespace URI )
    {
      if ( Attr has no prefix, or has a prefix that conflicts with
           a binding already active in scope )
      {
        if ( Element is in the scope of a non default binding for this
             namespace )
        {
          if ( one or more prefix bindings are available )
          {
            if ( one is locally defined )
            {
              ==> pick that one. 
            }
            else
            {
              ==> pick one arbitrarily 
            }
            ==> Change the Attr to use that prefix.
          }
          else
          {
            ==> Create a local namespace declaration attr for this namespace
            with a prefix not already used in the current scope and following
            the pattern "NS" + index (starting at 1).
            Change the Attr to use this prefix.
     
            // 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
      {
        // prefix does match but....

        if ( namespace is "http://www.w3.org/2000/xmlns/" AND attribute does
             not have the prefix "xmlns:" or the nodeName "xmlns" )
        {
          // While all Namespace Declarations belong to a reserved NSURI,
          // it is _not_ true that all attributes having that NSURI are to be
          // considered Namespace Declarations.
          // According to the namespace spec, only "xmlns" and names having
          // the xmlns: prefix should be interpreted as declarations. So:
          if ( there is a non default binding for this namespace in scope
               with a prefix other than "xmlns" )
          {
            if ( one is locally defined )
            {
              ==> pick that one. 
            }
            else
            {
              ==> pick one arbitrarily 
            }
            ==> Change the Attr to use that prefix.
          }
          else
          {
            ==> Create a local namespace declaration attr for this namespace
            with a prefix not already used in the current scope and following
            the pattern "NS" + index (starting at 1).
            Change the Attr to use this prefix.
     
            // NOTE that this may break other nodes within thisElement's
            // subtree, if they're already using this prefix.
            // They will be repaired when we reach them.
          }
          // end non-namespace-decl with namespace-decl URI
        }
      }
      // end namespaced Attr
    }
    else
    {
      // Attr[i] has no namespace URI
      if ( Attr[i] has a colon in its name )
      {
         if ( Level 2 node )
         {
            ==> report an error 
         }
         else
         {
            // Level 1 node
            if ( Name is not a QName )
            {
               ==> report an error 
            }
            else
            {
               if ( Prefix is bound to something )
               {
                  ==> report a warning
               }
               else
               {
                  ==> report an error
               }
            }
         }
      }
      else
      { 
        // attr has no namespace URI and no prefix
        // we're fine as we stand, 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.2: Namespace Prefix Lookup

The following describes in pseudo code the algorithm used in the lookupNamespacePrefix method of the Node interface.

DOMString lookupNamespacePrefix(in DOMString specifiedNamespaceURI,
                                in DOMString useDefault)
{
  switch (nodeType) {
  case ELEMENT_NODE:  
     if ( ( Element's namespaceURI == specifiedNamespaceURI ) and
          ( ( Element has prefix ) or
            ( Element has no prefix and
                 useDefault is true ) ) )
     {
          return Element's prefix
     }
     else if ( Element has an Attr and
               Attr's namespaceURI == "http://www.w3.org/2000/xmlns/" and
               Attr's prefix == "xmlns" and
               Attr's value == specifiedNamespaceURI )
     {
          return Attr's localName.
     }
     else if ( Element has an Attr and
               Attr's namespaceURI == "http://www.w3.org/2000/xmlns/" and
               Attr's localName == "xmlns" and
               Attr's value == specifiedNamespaceURI and
               useDefault is true )
     {
          return (null)
     }
     else if ( Element has an ancestor Element )
               // EntityReferences may have to be skipped to get to it
     {
          return ancestorElement.lookupNamespacePrefix(specifiedNamespaceURI,
                                                   useDefault)
     }
     else {
          return unknown (null)
     }    
  case DOCUMENT_NODE:
     return documentElement.lookupNamespacePrefix(specifiedNamespaceURI,
                                                  useDefault)
  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.lookupNamespacePrefix(specifiedNamespaceURI,
                                                    useDefault)
     }
     else {
          return unknown (null)
     }    
  default:
     if ( Node has an ancestor Element )
     {          
          return ancestorElement.lookupNamespacePrefix(specifiedNamespaceURI,
                                                       useDefault)
     }
     else {
          return unknown (null)
     }    
  }
}
     
Issue lookupNamespacePrefixAlgo-1:
Isn't the name the opposite of what it stands for?
Resolution: No.
Issue lookupNamespacePrefixAlgo-2:
How does one differentiate the case where it's the default namespace (prefix == null) from the case where the namespaceURI was not found?
Resolution: Use isDefaultNamespace.
Issue lookupNamespacePrefixAlgo-3:
How does one specify this is for an attribute and therefore the default namespace is not applicable?
Resolution: The algorithm goes directly to the owner element. Use useDefault to prevent using the default namespace.

B.3: Default Namespace Lookup

The following describes in pseudo code the algorithm used in the isDefaultNamespace method of the Node interface.

DOMString isDefaultNamespace(in DOMString specifiedNamespaceURI)
{
  switch (nodeType) {
  case ELEMENT_NODE:  
     if ( Element has no prefix )
     {
          return (Element's namespaceURI == specifiedNamespaceURI)
     }
     else if ( Element has an Attr and
               Attr's namespaceURI == "http://www.w3.org/2000/xmlns/" and
               Attr's localName == "xmlns" )
     {
      return Attr's value == specifiedNamespaceURI
     }

     if ( Element has an ancestor Element )
               // EntityReferences may have to be skipped to get to it
     {
          return ancestorElement.isDefaultNamespace(specifiedNamespaceURI)
     }
     else {
          return unknown (null)
     }    
  case DOCUMENT_NODE:
     return documentElement.isDefaultNamespace(specifiedNamespaceURI)
  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.isDefaultNamespace(specifiedNamespaceURI)
     }
     else {
          return unknown (null)
     }    
  default:
     if ( Node has an ancestor Element )
     {          
          return ancestorElement.isDefaultNamespace(specifiedNamespaceURI)
     }
     else {
          return unknown (null)
     }    
  }
}
     

B.4: Namespace URI Lookup

The following describes in pseudo code the algorithm used in the lookupNamespaceURI method of the Node interface.

DOMString lookupNamespaceURI(in DOMString specifiedPrefix)
{
  switch (nodeType) {
  case ELEMENT_NODE:
    return lookupNamespaceURI(specifiedPrefix, this);
  case DOCUMENT_NODE:
     return documentElement.lookupNamespaceURI(specifiedPrefix)
  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(specifiedPrefix)
     }
     else {
          return unknown (null)
     }    
  default:
     if (Node has an ancestor Element)
     {          
          return ancestorElement.lookupNamespaceURI(specifiedPrefix)
     }
     else {
          return unknown (null)
     }    
  }
}

DOMString lookupNamespaceURI(in DOMString specifiedPrefix, Element el)
{
   if ( Element's namespace URI != null and
        Element's prefix == specifiedPrefix and
    specifiedPrefix != null and
        el.lookupNamespacePrefix(Element's namespace URI, false) == specifiedPrefix )
        return Element's namespace URI
   }
   else if ( Element's namespace URI != null and
        Element's prefix == specifiedPrefix and
    specifiedPrefix == null and
        el.lookupNamespacePrefix(Element's namespace URI, true) == null )
        return Element's namespace URI
   }
   else if ( Element has an Attr and
             Attr's namespaceURI == "http://www.w3.org/2000/xmlns/" and
             Attr's prefix == "xmlns" and
             Attr's localName == specifiedPrefix and
             el.lookupNamespacePrefix(Attr's value URI, false) == specifiedPrefix )
   {
        return Attr's value.
   }
   else if ( Element has an Attr and
             Attr's namespaceURI == "http://www.w3.org/2000/xmlns/" and
             Attr's localName == "xmlns" and
             specifiedPrefix == null and
             el.lookupNamespacePrefix(Attr's value URI, true) == null )
   {
        return Attr's value.
   }
   else if ( Element has an ancestor Element )
            // EntityReferences may have to be skipped to get to it
   {
        return ancestorElement.lookupNamespaceURI(specifiedPrefix, el)
   }
   else {
        return unknown (null)
   }
}
     
Issue lookupNamespaceURIAlgo-1:
How does one look for the default namespace?
Resolution: use lookupNamespaceURI(null)