src/org/apache/xml/security/c14n/implementations/Canonicalizer11.java - santuario-xml-security-java - Git at Google

 /*
  * Copyright 2008 The Apache Software Foundation.
  *
  *  Licensed under the Apache License, Version 2.0 (the "License");
  *  you may not use this file except in compliance with the License.
  *  You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  *  Unless required by applicable law or agreed to in writing, software
  *  distributed under the License is distributed on an "AS IS" BASIS,
  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  *
  */
 package org.apache.xml.security.c14n.implementations;

 import java.io.IOException;
 import java.net.URI;
 import java.net.URISyntaxException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.SortedSet;
 import java.util.TreeSet;
 import javax.xml.parsers.ParserConfigurationException;
 import org.w3c.dom.Attr;
 import org.w3c.dom.Document;
 import org.w3c.dom.Element;
 import org.w3c.dom.NamedNodeMap;
 import org.w3c.dom.Node;
 import org.xml.sax.SAXException;

 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
 import org.apache.xml.security.c14n.CanonicalizationException;
 import org.apache.xml.security.c14n.helper.C14nHelper;
 import org.apache.xml.security.signature.XMLSignatureInput;
 import org.apache.xml.security.utils.Constants;
 import org.apache.xml.security.utils.XMLUtils;

 /**
  * Implements <A HREF="http://www.w3.org/TR/2008/PR-xml-c14n11-20080129/">
  * Canonical XML Version 1.1</A>, a W3C Proposed Recommendation from 29
  * January 2008.
  *
  * @author Sean Mullan
  * @author Raul Benito
  * @version $Revision: 429012 $
  */
 public abstract class Canonicalizer11 extends CanonicalizerBase {
     boolean firstCall = true;
     final SortedSet result = new TreeSet(COMPARE);
     static final String XMLNS_URI = Constants.NamespaceSpecNS;
     static final String XML_LANG_URI = Constants.XML_LANG_SPACE_SpecNS;

     static Log log = LogFactory.getLog(Canonicalizer11.class.getName());

     static class XmlAttrStack {
     	int currentLevel = 0;
     	int lastlevel = 0;
     	XmlsStackElement cur;
     	static class XmlsStackElement {
 	    int level;
     	    boolean rendered = false;
 	    List nodes = new ArrayList();
     	};
     	List levels = new ArrayList();
     	void push(int level) {
 	    currentLevel = level;
 	    if (currentLevel == -1)
     		return;
 	    cur = null;
 	    while (lastlevel >= currentLevel) {
 		levels.remove(levels.size() - 1);
 		if (levels.size() == 0) {
 		    lastlevel = 0;
 		    return;
 		}
     		lastlevel=((XmlsStackElement)levels.get(levels.size()-1)).level;
 	    }
     	}
     	void addXmlnsAttr(Attr n) {
 	    if (cur == null) {
 		cur = new XmlsStackElement();
 		cur.level = currentLevel;
 		levels.add(cur);
     		lastlevel = currentLevel;
 	    }
     	    cur.nodes.add(n);
     	}
     	void getXmlnsAttr(Collection col) {
 	    if (cur == null) {
 		cur = new XmlsStackElement();
     		cur.level = currentLevel;
     		lastlevel = currentLevel;
     		levels.add(cur);
     	    }
 	    int size = levels.size() - 2;
 	    boolean parentRendered = false;
 	    XmlsStackElement e = null;
 	    if (size == -1) {
 		parentRendered = true;
 	    } else {
     		e = (XmlsStackElement) levels.get(size);
 		if (e.rendered && e.level+1 == currentLevel)
     		    parentRendered = true;
 	    }
     	    if (parentRendered) {
 	        col.addAll(cur.nodes);
 	        cur.rendered = true;
 	        return;
 	    }

 	    Map loa = new HashMap();
 	    List baseAttrs = new ArrayList();
 	    boolean successiveOmitted = true;
     	    for (;size>=0;size--) {
     	        e = (XmlsStackElement) levels.get(size);
 		if (e.rendered) {
 		    successiveOmitted = false;
 		}
     	        Iterator it = e.nodes.iterator();
     	        while (it.hasNext() && successiveOmitted) {
     		    Attr n = (Attr) it.next();
 		    if (n.getLocalName().equals("base")) {
 			if (!e.rendered) {
 			    baseAttrs.add(n);
 			}
     		    } else if (!loa.containsKey(n.getName()))
 		        loa.put(n.getName(), n);
 	        }
 	    }
 	    if (!baseAttrs.isEmpty()) {
     	        Iterator it = cur.nodes.iterator();
 		String base = null;
 		Attr baseAttr = null;
     	        while (it.hasNext()) {
     		    Attr n = (Attr) it.next();
 		    if (n.getLocalName().equals("base")) {
 			base = n.getValue();
 			baseAttr = n;
 			break;
 		    }
 		}
 	        it = baseAttrs.iterator();
 	        while (it.hasNext()) {
 		    Attr n = (Attr) it.next();
 		    if (base == null) {
 			base = n.getValue();
 			baseAttr = n;
 		    } else {
 		        try {
 		            base = joinURI(n.getValue(), base);
 		        } catch (URISyntaxException ue) {
 			    ue.printStackTrace();
 		        }
 		    }
 		}
 		if (base != null && base.length() != 0) {
 		    baseAttr.setValue(base);
 		    col.add(baseAttr);
 		}
 	    }

 	    cur.rendered = true;
     	    col.addAll(loa.values());
         }
     };
     XmlAttrStack xmlattrStack = new XmlAttrStack();

     /**
      * Constructor Canonicalizer11
      *
      * @param includeComments
      */
     public Canonicalizer11(boolean includeComments) {
 	super(includeComments);
     }

     /**
      * Returns the Attr[]s to be outputted for the given element.
      * <br>
      * The code of this method is a copy of {@link #handleAttributes(Element,
      * NameSpaceSymbTable)},
      * whereas it takes into account that subtree-c14n is -- well --
      * subtree-based.
      * So if the element in question isRoot of c14n, it's parent is not in the
      * node set, as well as all other ancestors.
      *
      * @param E
      * @param ns
      * @return the Attr[]s to be outputted
      * @throws CanonicalizationException
      */
     Iterator handleAttributesSubtree(Element E, NameSpaceSymbTable ns)
 	throws CanonicalizationException {
 	if (!E.hasAttributes() && !firstCall) {
 	    return null;
 	}
 	// result will contain the attrs which have to be outputted
 	final SortedSet result = this.result;
 	result.clear();
 	NamedNodeMap attrs = E.getAttributes();
 	int attrsLength = attrs.getLength();

 	for (int i = 0; i < attrsLength; i++) {
 	    Attr N = (Attr) attrs.item(i);
 	    String NUri = N.getNamespaceURI();

 	    if (XMLNS_URI != NUri) {
 		// It's not a namespace attr node. Add to the result and
 		// continue.
 		result.add(N);
             	continue;
 	    }

 	    String NName = N.getLocalName();
 	    String NValue = N.getValue();
 	    if (XML.equals(NName)
 		&& XML_LANG_URI.equals(NValue)) {
          	// The default mapping for xml must not be output.
          	continue;
 	    }

 	    Node n = ns.addMappingAndRender(NName, NValue, N);

 	    if (n != null) {
 		// Render the ns definition
 		result.add(n);
 		if (C14nHelper.namespaceIsRelative(N)) {
                     Object exArgs[] = {E.getTagName(), NName, N.getNodeValue()};
                     throw new CanonicalizationException(
 			"c14n.Canonicalizer.RelativeNamespace", exArgs);
 		}
 	    }
 	}

 	if (firstCall) {
 	    // It is the first node of the subtree
 	    // Obtain all the namespaces defined in the parents, and added
 	    // to the output.
 	    ns.getUnrenderedNodes(result);
 	    // output the attributes in the xml namespace.
 	    xmlattrStack.getXmlnsAttr(result);
 	    firstCall = false;
 	}

 	return result.iterator();
     }

     /**
      * Returns the Attr[]s to be outputted for the given element.
      * <br>
      * IMPORTANT: This method expects to work on a modified DOM tree, i.e. a
      * DOM which has been prepared using
      * {@link org.apache.xml.security.utils.XMLUtils#circumventBug2650(
      * org.w3c.dom.Document)}.
      *
      * @param E
      * @param ns
      * @return the Attr[]s to be outputted
      * @throws CanonicalizationException
      */
     Iterator handleAttributes(Element E, NameSpaceSymbTable ns)
 	throws CanonicalizationException {
         // result will contain the attrs which have to be output
 	xmlattrStack.push(ns.getLevel());
         boolean isRealVisible = isVisibleDO(E, ns.getLevel()) == 1;
         NamedNodeMap attrs = null;
         int attrsLength = 0;
         if (E.hasAttributes()) {
             attrs = E.getAttributes();
             attrsLength = attrs.getLength();
         }

 	SortedSet result = this.result;
 	result.clear();

 	for (int i = 0; i < attrsLength; i++) {
 	    Attr N = (Attr) attrs.item(i);
 	    String NUri = N.getNamespaceURI();

 	    if (XMLNS_URI != NUri) {
 		// A non namespace definition node.
 		if (XML_LANG_URI == NUri) {
 		    if (N.getLocalName().equals("id")) {
 			if (isRealVisible) {
 			    // treat xml:id like any other attribute
 		 	    // (emit it, but don't inherit it)
 			    result.add(N);
 			}
 		    } else {
 		        xmlattrStack.addXmlnsAttr(N);
 		    }
                 } else if (isRealVisible) {
        		    // The node is visible add the attribute to the list of
 		    // output attributes.
            	    result.add(N);
           	}
        	  	// keep working
           	continue;
 	    }

 	    String NName = N.getLocalName();
 	    String NValue = N.getValue();
 	    if ("xml".equals(NName)
                 && XML_LANG_URI.equals(NValue)) {
 		/* except omit namespace node with local name xml, which defines
 		 * the xml prefix, if its string value is
 		 * http://www.w3.org/XML/1998/namespace.
            	 */
           	continue;
 	    }
 	    // add the prefix binding to the ns symb table.
 	    // ns.addInclusiveMapping(NName,NValue,N,isRealVisible);
 	    if (isVisible(N))  {
 	    	if (!isRealVisible && ns.removeMappingIfRender(NName)) {
     		    continue;
 	    	}
 		// The xpath select this node output it if needed.
 	    	// Node n = ns.addMappingAndRenderXNodeSet
 		//	(NName, NValue, N, isRealVisible);
 	    	Node n = ns.addMappingAndRender(NName, NValue, N);
 	 	if (n != null) {
 	 	    result.add(n);
                     if (C14nHelper.namespaceIsRelative(N)) {
 			Object exArgs[] =
 			    { E.getTagName(), NName, N.getNodeValue() };
 			throw new CanonicalizationException(
                             "c14n.Canonicalizer.RelativeNamespace", exArgs);
 		    }
 		}
 	    } else {
     		if (isRealVisible && NName != XMLNS) {
 		    ns.removeMapping(NName);
 		} else {
     		    ns.addMapping(NName, NValue, N);
     		}
 	    }
 	}
 	if (isRealVisible) {
     	    // The element is visible, handle the xmlns definition
             Attr xmlns = E.getAttributeNodeNS(XMLNS_URI, XMLNS);
             Node n = null;
             if (xmlns == null) {
         	// No xmlns def just get the already defined.
         	n = ns.getMapping(XMLNS);
 	    } else if (!isVisible(xmlns)) {
 		// There is a defn but the xmlns is not selected by the xpath.
         	// then xmlns=""
         	n = ns.addMappingAndRender(XMLNS, "", nullNode);
 	    }
             // output the xmlns def if needed.
             if (n != null) {
 		result.add(n);
 	    }
 	    // Float all xml:* attributes of the unselected parent elements to
 	    // this one. addXmlAttributes(E,result);
             xmlattrStack.getXmlnsAttr(result);
     	    ns.getUnrenderedNodes(result);
         }

 	return result.iterator();
     }

     /**
      * Always throws a CanonicalizationException because this is inclusive c14n.
      *
      * @param xpathNodeSet
      * @param inclusiveNamespaces
      * @return none it always fails
      * @throws CanonicalizationException always
      */
     public byte[] engineCanonicalizeXPathNodeSet(Set xpathNodeSet,
 	String inclusiveNamespaces) throws CanonicalizationException {
         throw new CanonicalizationException(
          "c14n.Canonicalizer.UnsupportedOperation");
     }

     /**
      * Always throws a CanonicalizationException because this is inclusive c14n.
      *
      * @param rootNode
      * @param inclusiveNamespaces
      * @return none it always fails
      * @throws CanonicalizationException
      */
     public byte[] engineCanonicalizeSubTree(Node rootNode,
 	String inclusiveNamespaces) throws CanonicalizationException {
         throw new CanonicalizationException(
 	    "c14n.Canonicalizer.UnsupportedOperation");
     }

     void circumventBugIfNeeded(XMLSignatureInput input)
 	throws CanonicalizationException, ParserConfigurationException,
         IOException, SAXException {
 	if (!input.isNeedsToBeExpanded())
 	    return;
 	Document doc = null;
 	if (input.getSubNode() != null) {
 	    doc = XMLUtils.getOwnerDocument(input.getSubNode());
 	} else {
 	    doc = XMLUtils.getOwnerDocument(input.getNodeSet());
 	}
 	XMLUtils.circumventBug2650(doc);
     }

     void handleParent(Element e, NameSpaceSymbTable ns) {
 	if (!e.hasAttributes()) {
 	    return;
 	}
 	xmlattrStack.push(-1);
 	NamedNodeMap attrs = e.getAttributes();
 	int attrsLength = attrs.getLength();
 	for (int i = 0; i < attrsLength; i++) {
 	    Attr N = (Attr) attrs.item(i);
 	    if (Constants.NamespaceSpecNS != N.getNamespaceURI()) {
 		// Not a namespace definition, ignore.
 		if (XML_LANG_URI == N.getNamespaceURI()) {
 		    xmlattrStack.addXmlnsAttr(N);
 		}
 		continue;
 	    }

 	    String NName = N.getLocalName();
 	    String NValue = N.getNodeValue();
 	    if (XML.equals(NName)
 	        && Constants.XML_LANG_SPACE_SpecNS.equals(NValue)) {
 	        continue;
 	    }
 	    ns.addMapping(NName,NValue,N);
 	}
     }

     private static String joinURI(String baseURI, String relativeURI)
         throws URISyntaxException {
 	String bscheme = null;
 	String bauthority = null;
 	String bpath = "";
 	String bquery = null;
 	String bfragment = null; // Is this correct?

 	// pre-parse the baseURI
 	if (baseURI != null) {
 	    if (baseURI.endsWith("..")) {
 		baseURI = baseURI + "/";
 	    }
 	    URI base = new URI(baseURI);
 	    bscheme = base.getScheme();
 	    bauthority = base.getAuthority();
 	    bpath = base.getPath();
 	    bquery = base.getQuery();
 	    bfragment = base.getFragment();
 	}

 	URI r = new URI(relativeURI);
 	String rscheme = r.getScheme();
 	String rauthority = r.getAuthority();
 	String rpath = r.getPath();
 	String rquery = r.getQuery();
 	String rfragment = null;

 	String tscheme, tauthority, tpath, tquery, tfragment;
 	if (rscheme != null && rscheme.equals(bscheme)) {
 	    rscheme = null;
 	}
 	if (rscheme != null) {
 	    tscheme = rscheme;
 	    tauthority = rauthority;
 	    tpath = removeDotSegments(rpath);
 	    tquery = rquery;
 	} else {
 	    if (rauthority != null) {
 		tauthority = rauthority;
 		tpath = removeDotSegments(rpath);
 		tquery = rquery;
 	    } else {
 	        if (rpath.length() == 0) {
 		    tpath = bpath;
 		    if (rquery != null) {
 		        tquery = rquery;
 		    } else {
 		        tquery = bquery;
 		    }
 	        } else {
 		    if (rpath.startsWith("/")) {
 		        tpath = removeDotSegments(rpath);
 		    } else {
 		        if (bauthority != null && bpath.length() == 0) {
 			    tpath = "/" + rpath;
 		        } else {
 			    int last = bpath.lastIndexOf('/');
 			    if (last == -1) {
 			        tpath = rpath;
 			    } else {
 			        tpath = bpath.substring(0, last+1) + rpath;
 			    }
 		        }
 		        tpath = removeDotSegments(tpath);
 		    }
 		    tquery = rquery;
 	        }
 	        tauthority = bauthority;
 	    }
 	    tscheme = bscheme;
 	}
 	tfragment = rfragment;
 	return new URI(tscheme, tauthority, tpath, tquery, tfragment).toString();
     }

     private static String removeDotSegments(String path) {

         log.debug("STEP   OUTPUT BUFFER\t\tINPUT BUFFER");

         // 1. The input buffer is initialized with the now-appended path
         // components then replace occurrences of "//" in the input buffer
         // with "/" until no more occurrences of "//" are in the input buffer.
         String input = path;
         while (input.indexOf("//") > -1) {
             input = input.replaceAll("//", "/");
         }

         // Initialize the output buffer with the empty string.
         StringBuffer output = new StringBuffer();

         // If the input buffer starts with a root slash "/" then move this
         // character to the output buffer.
         if (input.charAt(0) == '/') {
             output.append("/");
             input = input.substring(1);
         }

         printStep("1 ", output.toString(), input);

         // While the input buffer is not empty, loop as follows
         while (input.length() != 0) {
             // 2A. If the input buffer begins with a prefix of "./",
             // then remove that prefix from the input buffer
             // else if the input buffer begins with a prefix of "../", then
             // if also the output does not contain the root slash "/" only,
             // then move this prefix to the end of the output buffer else
             // remove that prefix
             if (input.startsWith("./")) {
                 input = input.substring(2);
                 printStep("2A", output.toString(), input);
             } else if (input.startsWith("../")) {
                 input = input.substring(3);
                 if (!output.toString().equals("/")) {
                     output.append("../");
                 }
                 printStep("2A", output.toString(), input);
             // 2B. if the input buffer begins with a prefix of "/./" or "/.",
             // where "." is a complete path segment, then replace that prefix
             // with "/" in the input buffer; otherwise,
             } else if (input.startsWith("/./")) {
                 input = input.substring(2);
                 printStep("2B", output.toString(), input);
             } else if (input.equals("/.")) {
                 // FIXME: what is complete path segment?
                 input = input.replaceFirst("/.", "/");
                 printStep("2B", output.toString(), input);
             // 2C. if the input buffer begins with a prefix of "/../" or "/..",
             // where ".." is a complete path segment, then replace that prefix
             // with "/" in the input buffer and if also the output buffer is
             // empty, last segment in the output buffer equals "../" or "..",
             // where ".." is a complete path segment, then append ".." or "/.."
             // for the latter case respectively to the output buffer else
             // remove the last segment and its preceding "/" (if any) from the
             // output buffer and if hereby the first character in the output
             // buffer was removed and it was not the root slash then delete a
             // leading slash from the input buffer; otherwise,
             } else if (input.startsWith("/../")) {
                 input = input.substring(3);
                 if (output.length() == 0) {
                     output.append("/");
                 } else if (output.toString().endsWith("../")) {
                     output.append("..");
                 } else if (output.toString().endsWith("..")) {
                     output.append("/..");
                 } else {
                     int index = output.lastIndexOf("/");
                     if (index == -1) {
                         output = new StringBuffer();
                         if (input.charAt(0) == '/') {
                             input = input.substring(1);
                         }
                     } else {
                         output = output.delete(index, output.length());
                     }
                 }
                 printStep("2C", output.toString(), input);
             } else if (input.equals("/..")) {
                 // FIXME: what is complete path segment?
                 input = input.replaceFirst("/..", "/");
                 if (output.length() == 0) {
                     output.append("/");
                 } else if (output.toString().endsWith("../")) {
                     output.append("..");
                 } else if (output.toString().endsWith("..")) {
                     output.append("/..");
                 } else {
                     int index = output.lastIndexOf("/");
                     if (index == -1) {
                         output = new StringBuffer();
                         if (input.charAt(0) == '/') {
                             input = input.substring(1);
                         }
                     } else {
                         output = output.delete(index, output.length());
                     }
                 }
                 printStep("2C", output.toString(), input);
             // 2D. if the input buffer consists only of ".", then remove
             // that from the input buffer else if the input buffer consists
             // only of ".." and if the output buffer does not contain only
             // the root slash "/", then move the ".." to the output buffer
             // else delte it.; otherwise,
             } else if (input.equals(".")) {
                 input = "";
                 printStep("2D", output.toString(), input);
             } else if (input.equals("..")) {
                 if (!output.toString().equals("/"))
                     output.append("..");
                 input = "";
                 printStep("2D", output.toString(), input);
             // 2E. move the first path segment (if any) in the input buffer
             // to the end of the output buffer, including the initial "/"
             // character (if any) and any subsequent characters up to, but not
             // including, the next "/" character or the end of the input buffer.
             } else {
                 int end = -1;
                 int begin = input.indexOf('/');
                 if (begin == 0) {
                     end = input.indexOf('/', 1);
                 } else {
                     end = begin;
                     begin = 0;
                 }
                 String segment;
                 if (end == -1) {
                     segment = input.substring(begin);
                     input = "";
                 } else {
                     segment = input.substring(begin, end);
                     input = input.substring(end);
                 }
                 output.append(segment);
                 printStep("2E", output.toString(), input);
             }
         }

         // 3. Finally, if the only or last segment of the output buffer is
         // "..", where ".." is a complete path segment not followed by a slash
         // then append a slash "/". The output buffer is returned as the result
         // of remove_dot_segments
         if (output.toString().endsWith("..")) {
             output.append("/");
             printStep("3 ", output.toString(), input);
         }

         return output.toString();
     }

     private static void printStep(String step, String output, String input) {
 	if (log.isDebugEnabled()) {
             log.debug(" " + step + ":   " + output);
             if (output.length() == 0) {
                 log.debug("\t\t\t\t" + input);
             } else {
                 log.debug("\t\t\t" + input);
             }
         }
     }
 }
	/*
	* Copyright 2008 The Apache Software Foundation.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*
	*/
	package org.apache.xml.security.c14n.implementations;

	import java.io.IOException;
	import java.net.URI;
	import java.net.URISyntaxException;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	import java.util.SortedSet;
	import java.util.TreeSet;
	import javax.xml.parsers.ParserConfigurationException;
	import org.w3c.dom.Attr;
	import org.w3c.dom.Document;
	import org.w3c.dom.Element;
	import org.w3c.dom.NamedNodeMap;
	import org.w3c.dom.Node;
	import org.xml.sax.SAXException;

	import org.apache.commons.logging.Log;
	import org.apache.commons.logging.LogFactory;
	import org.apache.xml.security.c14n.CanonicalizationException;
	import org.apache.xml.security.c14n.helper.C14nHelper;
	import org.apache.xml.security.signature.XMLSignatureInput;
	import org.apache.xml.security.utils.Constants;
	import org.apache.xml.security.utils.XMLUtils;

	/**
	* Implements <A HREF="http://www.w3.org/TR/2008/PR-xml-c14n11-20080129/">
	* Canonical XML Version 1.1</A>, a W3C Proposed Recommendation from 29
	* January 2008.
	*
	* @author Sean Mullan
	* @author Raul Benito
	* @version $Revision: 429012 $
	*/
	public abstract class Canonicalizer11 extends CanonicalizerBase {
	boolean firstCall = true;
	final SortedSet result = new TreeSet(COMPARE);
	static final String XMLNS_URI = Constants.NamespaceSpecNS;
	static final String XML_LANG_URI = Constants.XML_LANG_SPACE_SpecNS;

	static Log log = LogFactory.getLog(Canonicalizer11.class.getName());

	static class XmlAttrStack {
	int currentLevel = 0;
	int lastlevel = 0;
	XmlsStackElement cur;
	static class XmlsStackElement {
	int level;
	boolean rendered = false;
	List nodes = new ArrayList();
	};
	List levels = new ArrayList();
	void push(int level) {
	currentLevel = level;
	if (currentLevel == -1)
	return;
	cur = null;
	while (lastlevel >= currentLevel) {
	levels.remove(levels.size() - 1);
	if (levels.size() == 0) {
	lastlevel = 0;
	return;
	}
	lastlevel=((XmlsStackElement)levels.get(levels.size()-1)).level;
	}
	}
	void addXmlnsAttr(Attr n) {
	if (cur == null) {
	cur = new XmlsStackElement();
	cur.level = currentLevel;
	levels.add(cur);
	lastlevel = currentLevel;
	}
	cur.nodes.add(n);
	}
	void getXmlnsAttr(Collection col) {
	if (cur == null) {
	cur = new XmlsStackElement();
	cur.level = currentLevel;
	lastlevel = currentLevel;
	levels.add(cur);
	}
	int size = levels.size() - 2;
	boolean parentRendered = false;
	XmlsStackElement e = null;
	if (size == -1) {
	parentRendered = true;
	} else {
	e = (XmlsStackElement) levels.get(size);
	if (e.rendered && e.level+1 == currentLevel)
	parentRendered = true;
	}
	if (parentRendered) {
	col.addAll(cur.nodes);
	cur.rendered = true;
	return;
	}

	Map loa = new HashMap();
	List baseAttrs = new ArrayList();
	boolean successiveOmitted = true;
	for (;size>=0;size--) {
	e = (XmlsStackElement) levels.get(size);
	if (e.rendered) {
	successiveOmitted = false;
	}
	Iterator it = e.nodes.iterator();
	while (it.hasNext() && successiveOmitted) {
	Attr n = (Attr) it.next();
	if (n.getLocalName().equals("base")) {
	if (!e.rendered) {
	baseAttrs.add(n);
	}
	} else if (!loa.containsKey(n.getName()))
	loa.put(n.getName(), n);
	}
	}
	if (!baseAttrs.isEmpty()) {
	Iterator it = cur.nodes.iterator();
	String base = null;
	Attr baseAttr = null;
	while (it.hasNext()) {
	Attr n = (Attr) it.next();
	if (n.getLocalName().equals("base")) {
	base = n.getValue();
	baseAttr = n;
	break;
	}
	}
	it = baseAttrs.iterator();
	while (it.hasNext()) {
	Attr n = (Attr) it.next();
	if (base == null) {
	base = n.getValue();
	baseAttr = n;
	} else {
	try {
	base = joinURI(n.getValue(), base);
	} catch (URISyntaxException ue) {
	ue.printStackTrace();
	}
	}
	}
	if (base != null && base.length() != 0) {
	baseAttr.setValue(base);
	col.add(baseAttr);
	}
	}

	cur.rendered = true;
	col.addAll(loa.values());
	}
	};
	XmlAttrStack xmlattrStack = new XmlAttrStack();

	/**
	* Constructor Canonicalizer11
	*
	* @param includeComments
	*/
	public Canonicalizer11(boolean includeComments) {
	super(includeComments);
	}

	/**
	* Returns the Attr[]s to be outputted for the given element.
	* <br>
	* The code of this method is a copy of {@link #handleAttributes(Element,
	* NameSpaceSymbTable)},
	* whereas it takes into account that subtree-c14n is -- well --
	* subtree-based.
	* So if the element in question isRoot of c14n, it's parent is not in the
	* node set, as well as all other ancestors.
	*
	* @param E
	* @param ns
	* @return the Attr[]s to be outputted
	* @throws CanonicalizationException
	*/
	Iterator handleAttributesSubtree(Element E, NameSpaceSymbTable ns)
	throws CanonicalizationException {
	if (!E.hasAttributes() && !firstCall) {
	return null;
	}
	// result will contain the attrs which have to be outputted
	final SortedSet result = this.result;
	result.clear();
	NamedNodeMap attrs = E.getAttributes();
	int attrsLength = attrs.getLength();

	for (int i = 0; i < attrsLength; i++) {
	Attr N = (Attr) attrs.item(i);
	String NUri = N.getNamespaceURI();

	if (XMLNS_URI != NUri) {
	// It's not a namespace attr node. Add to the result and
	// continue.
	result.add(N);
	continue;
	}

	String NName = N.getLocalName();
	String NValue = N.getValue();
	if (XML.equals(NName)
	&& XML_LANG_URI.equals(NValue)) {
	// The default mapping for xml must not be output.
	continue;
	}

	Node n = ns.addMappingAndRender(NName, NValue, N);

	if (n != null) {
	// Render the ns definition
	result.add(n);
	if (C14nHelper.namespaceIsRelative(N)) {
	Object exArgs[] = {E.getTagName(), NName, N.getNodeValue()};
	throw new CanonicalizationException(
	"c14n.Canonicalizer.RelativeNamespace", exArgs);
	}
	}
	}

	if (firstCall) {
	// It is the first node of the subtree
	// Obtain all the namespaces defined in the parents, and added
	// to the output.
	ns.getUnrenderedNodes(result);
	// output the attributes in the xml namespace.
	xmlattrStack.getXmlnsAttr(result);
	firstCall = false;
	}

	return result.iterator();
	}

	/**
	* Returns the Attr[]s to be outputted for the given element.
	* <br>
	* IMPORTANT: This method expects to work on a modified DOM tree, i.e. a
	* DOM which has been prepared using
	* {@link org.apache.xml.security.utils.XMLUtils#circumventBug2650(
	* org.w3c.dom.Document)}.
	*
	* @param E
	* @param ns
	* @return the Attr[]s to be outputted
	* @throws CanonicalizationException
	*/
	Iterator handleAttributes(Element E, NameSpaceSymbTable ns)
	throws CanonicalizationException {
	// result will contain the attrs which have to be output
	xmlattrStack.push(ns.getLevel());
	boolean isRealVisible = isVisibleDO(E, ns.getLevel()) == 1;
	NamedNodeMap attrs = null;
	int attrsLength = 0;
	if (E.hasAttributes()) {
	attrs = E.getAttributes();
	attrsLength = attrs.getLength();
	}

	SortedSet result = this.result;
	result.clear();

	for (int i = 0; i < attrsLength; i++) {
	Attr N = (Attr) attrs.item(i);
	String NUri = N.getNamespaceURI();

	if (XMLNS_URI != NUri) {
	// A non namespace definition node.
	if (XML_LANG_URI == NUri) {
	if (N.getLocalName().equals("id")) {
	if (isRealVisible) {
	// treat xml:id like any other attribute
	// (emit it, but don't inherit it)
	result.add(N);
	}
	} else {
	xmlattrStack.addXmlnsAttr(N);
	}
	} else if (isRealVisible) {
	// The node is visible add the attribute to the list of
	// output attributes.
	result.add(N);
	}
	// keep working
	continue;
	}

	String NName = N.getLocalName();
	String NValue = N.getValue();
	if ("xml".equals(NName)
	&& XML_LANG_URI.equals(NValue)) {
	/* except omit namespace node with local name xml, which defines
	* the xml prefix, if its string value is
	* http://www.w3.org/XML/1998/namespace.
	*/
	continue;
	}
	// add the prefix binding to the ns symb table.
	// ns.addInclusiveMapping(NName,NValue,N,isRealVisible);
	if (isVisible(N)) {
	if (!isRealVisible && ns.removeMappingIfRender(NName)) {
	continue;
	}
	// The xpath select this node output it if needed.
	// Node n = ns.addMappingAndRenderXNodeSet
	// (NName, NValue, N, isRealVisible);
	Node n = ns.addMappingAndRender(NName, NValue, N);
	if (n != null) {
	result.add(n);
	if (C14nHelper.namespaceIsRelative(N)) {
	Object exArgs[] =
	{ E.getTagName(), NName, N.getNodeValue() };
	throw new CanonicalizationException(
	"c14n.Canonicalizer.RelativeNamespace", exArgs);
	}
	}
	} else {
	if (isRealVisible && NName != XMLNS) {
	ns.removeMapping(NName);
	} else {
	ns.addMapping(NName, NValue, N);
	}
	}
	}
	if (isRealVisible) {
	// The element is visible, handle the xmlns definition
	Attr xmlns = E.getAttributeNodeNS(XMLNS_URI, XMLNS);
	Node n = null;
	if (xmlns == null) {
	// No xmlns def just get the already defined.
	n = ns.getMapping(XMLNS);
	} else if (!isVisible(xmlns)) {
	// There is a defn but the xmlns is not selected by the xpath.
	// then xmlns=""
	n = ns.addMappingAndRender(XMLNS, "", nullNode);
	}
	// output the xmlns def if needed.
	if (n != null) {
	result.add(n);
	}
	// Float all xml:* attributes of the unselected parent elements to
	// this one. addXmlAttributes(E,result);
	xmlattrStack.getXmlnsAttr(result);
	ns.getUnrenderedNodes(result);
	}

	return result.iterator();
	}

	/**
	* Always throws a CanonicalizationException because this is inclusive c14n.
	*
	* @param xpathNodeSet
	* @param inclusiveNamespaces
	* @return none it always fails
	* @throws CanonicalizationException always
	*/
	public byte[] engineCanonicalizeXPathNodeSet(Set xpathNodeSet,
	String inclusiveNamespaces) throws CanonicalizationException {
	throw new CanonicalizationException(
	"c14n.Canonicalizer.UnsupportedOperation");
	}

	/**
	* Always throws a CanonicalizationException because this is inclusive c14n.
	*
	* @param rootNode
	* @param inclusiveNamespaces
	* @return none it always fails
	* @throws CanonicalizationException
	*/
	public byte[] engineCanonicalizeSubTree(Node rootNode,
	String inclusiveNamespaces) throws CanonicalizationException {
	throw new CanonicalizationException(
	"c14n.Canonicalizer.UnsupportedOperation");
	}

	void circumventBugIfNeeded(XMLSignatureInput input)
	throws CanonicalizationException, ParserConfigurationException,
	IOException, SAXException {
	if (!input.isNeedsToBeExpanded())
	return;
	Document doc = null;
	if (input.getSubNode() != null) {
	doc = XMLUtils.getOwnerDocument(input.getSubNode());
	} else {
	doc = XMLUtils.getOwnerDocument(input.getNodeSet());
	}
	XMLUtils.circumventBug2650(doc);
	}

	void handleParent(Element e, NameSpaceSymbTable ns) {
	if (!e.hasAttributes()) {
	return;
	}
	xmlattrStack.push(-1);
	NamedNodeMap attrs = e.getAttributes();
	int attrsLength = attrs.getLength();
	for (int i = 0; i < attrsLength; i++) {
	Attr N = (Attr) attrs.item(i);
	if (Constants.NamespaceSpecNS != N.getNamespaceURI()) {
	// Not a namespace definition, ignore.
	if (XML_LANG_URI == N.getNamespaceURI()) {
	xmlattrStack.addXmlnsAttr(N);
	}
	continue;
	}

	String NName = N.getLocalName();
	String NValue = N.getNodeValue();
	if (XML.equals(NName)
	&& Constants.XML_LANG_SPACE_SpecNS.equals(NValue)) {
	continue;
	}
	ns.addMapping(NName,NValue,N);
	}
	}

	private static String joinURI(String baseURI, String relativeURI)
	throws URISyntaxException {
	String bscheme = null;
	String bauthority = null;
	String bpath = "";
	String bquery = null;
	String bfragment = null; // Is this correct?

	// pre-parse the baseURI
	if (baseURI != null) {
	if (baseURI.endsWith("..")) {
	baseURI = baseURI + "/";
	}
	URI base = new URI(baseURI);
	bscheme = base.getScheme();
	bauthority = base.getAuthority();
	bpath = base.getPath();
	bquery = base.getQuery();
	bfragment = base.getFragment();
	}

	URI r = new URI(relativeURI);
	String rscheme = r.getScheme();
	String rauthority = r.getAuthority();
	String rpath = r.getPath();
	String rquery = r.getQuery();
	String rfragment = null;

	String tscheme, tauthority, tpath, tquery, tfragment;
	if (rscheme != null && rscheme.equals(bscheme)) {
	rscheme = null;
	}
	if (rscheme != null) {
	tscheme = rscheme;
	tauthority = rauthority;
	tpath = removeDotSegments(rpath);
	tquery = rquery;
	} else {
	if (rauthority != null) {
	tauthority = rauthority;
	tpath = removeDotSegments(rpath);
	tquery = rquery;
	} else {
	if (rpath.length() == 0) {
	tpath = bpath;
	if (rquery != null) {
	tquery = rquery;
	} else {
	tquery = bquery;
	}
	} else {
	if (rpath.startsWith("/")) {
	tpath = removeDotSegments(rpath);
	} else {
	if (bauthority != null && bpath.length() == 0) {
	tpath = "/" + rpath;
	} else {
	int last = bpath.lastIndexOf('/');
	if (last == -1) {
	tpath = rpath;
	} else {
	tpath = bpath.substring(0, last+1) + rpath;
	}
	}
	tpath = removeDotSegments(tpath);
	}
	tquery = rquery;
	}
	tauthority = bauthority;
	}
	tscheme = bscheme;
	}
	tfragment = rfragment;
	return new URI(tscheme, tauthority, tpath, tquery, tfragment).toString();
	}

	private static String removeDotSegments(String path) {

	log.debug("STEP OUTPUT BUFFER\t\tINPUT BUFFER");

	// 1. The input buffer is initialized with the now-appended path
	// components then replace occurrences of "//" in the input buffer
	// with "/" until no more occurrences of "//" are in the input buffer.
	String input = path;
	while (input.indexOf("//") > -1) {
	input = input.replaceAll("//", "/");
	}

	// Initialize the output buffer with the empty string.
	StringBuffer output = new StringBuffer();

	// If the input buffer starts with a root slash "/" then move this
	// character to the output buffer.
	if (input.charAt(0) == '/') {
	output.append("/");
	input = input.substring(1);
	}

	printStep("1 ", output.toString(), input);

	// While the input buffer is not empty, loop as follows
	while (input.length() != 0) {
	// 2A. If the input buffer begins with a prefix of "./",
	// then remove that prefix from the input buffer
	// else if the input buffer begins with a prefix of "../", then
	// if also the output does not contain the root slash "/" only,
	// then move this prefix to the end of the output buffer else
	// remove that prefix
	if (input.startsWith("./")) {
	input = input.substring(2);
	printStep("2A", output.toString(), input);
	} else if (input.startsWith("../")) {
	input = input.substring(3);
	if (!output.toString().equals("/")) {
	output.append("../");
	}
	printStep("2A", output.toString(), input);
	// 2B. if the input buffer begins with a prefix of "/./" or "/.",
	// where "." is a complete path segment, then replace that prefix
	// with "/" in the input buffer; otherwise,
	} else if (input.startsWith("/./")) {
	input = input.substring(2);
	printStep("2B", output.toString(), input);
	} else if (input.equals("/.")) {
	// FIXME: what is complete path segment?
	input = input.replaceFirst("/.", "/");
	printStep("2B", output.toString(), input);
	// 2C. if the input buffer begins with a prefix of "/../" or "/..",
	// where ".." is a complete path segment, then replace that prefix
	// with "/" in the input buffer and if also the output buffer is
	// empty, last segment in the output buffer equals "../" or "..",
	// where ".." is a complete path segment, then append ".." or "/.."
	// for the latter case respectively to the output buffer else
	// remove the last segment and its preceding "/" (if any) from the
	// output buffer and if hereby the first character in the output
	// buffer was removed and it was not the root slash then delete a
	// leading slash from the input buffer; otherwise,
	} else if (input.startsWith("/../")) {
	input = input.substring(3);
	if (output.length() == 0) {
	output.append("/");
	} else if (output.toString().endsWith("../")) {
	output.append("..");
	} else if (output.toString().endsWith("..")) {
	output.append("/..");
	} else {
	int index = output.lastIndexOf("/");
	if (index == -1) {
	output = new StringBuffer();
	if (input.charAt(0) == '/') {
	input = input.substring(1);
	}
	} else {
	output = output.delete(index, output.length());
	}
	}
	printStep("2C", output.toString(), input);
	} else if (input.equals("/..")) {
	// FIXME: what is complete path segment?
	input = input.replaceFirst("/..", "/");
	if (output.length() == 0) {
	output.append("/");
	} else if (output.toString().endsWith("../")) {
	output.append("..");
	} else if (output.toString().endsWith("..")) {
	output.append("/..");
	} else {
	int index = output.lastIndexOf("/");
	if (index == -1) {
	output = new StringBuffer();
	if (input.charAt(0) == '/') {
	input = input.substring(1);
	}
	} else {
	output = output.delete(index, output.length());
	}
	}
	printStep("2C", output.toString(), input);
	// 2D. if the input buffer consists only of ".", then remove
	// that from the input buffer else if the input buffer consists
	// only of ".." and if the output buffer does not contain only
	// the root slash "/", then move the ".." to the output buffer
	// else delte it.; otherwise,
	} else if (input.equals(".")) {
	input = "";
	printStep("2D", output.toString(), input);
	} else if (input.equals("..")) {
	if (!output.toString().equals("/"))
	output.append("..");
	input = "";
	printStep("2D", output.toString(), input);
	// 2E. move the first path segment (if any) in the input buffer
	// to the end of the output buffer, including the initial "/"
	// character (if any) and any subsequent characters up to, but not
	// including, the next "/" character or the end of the input buffer.
	} else {
	int end = -1;
	int begin = input.indexOf('/');
	if (begin == 0) {
	end = input.indexOf('/', 1);
	} else {
	end = begin;
	begin = 0;
	}
	String segment;
	if (end == -1) {
	segment = input.substring(begin);
	input = "";
	} else {
	segment = input.substring(begin, end);
	input = input.substring(end);
	}
	output.append(segment);
	printStep("2E", output.toString(), input);
	}
	}

	// 3. Finally, if the only or last segment of the output buffer is
	// "..", where ".." is a complete path segment not followed by a slash
	// then append a slash "/". The output buffer is returned as the result
	// of remove_dot_segments
	if (output.toString().endsWith("..")) {
	output.append("/");
	printStep("3 ", output.toString(), input);
	}

	return output.toString();
	}

	private static void printStep(String step, String output, String input) {
	if (log.isDebugEnabled()) {
	log.debug(" " + step + ": " + output);
	if (output.length() == 0) {
	log.debug("\t\t\t\t" + input);
	} else {
	log.debug("\t\t\t" + input);
	}
	}
	}
	}