xml comparexml_compare

14 files changed, 2077 insertions, 0 deletions

diff --git a/ui/org.eclipse.pde.ui/icons/obj16/xml_text_node.gif b/ui/org.eclipse.pde.ui/icons/obj16/xml_text_node.gif
new file mode 100644
index 0000000000..2a2b4b6f40
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/icons/obj16/xml_text_node.gif
diff --git a/ui/org.eclipse.pde.ui/plugin.xml b/ui/org.eclipse.pde.ui/plugin.xml
index b02b282aa2..c779b3a911 100644
--- a/ui/org.eclipse.pde.ui/plugin.xml
+++ b/ui/org.eclipse.pde.ui/plugin.xml
@@ -1759,6 +1759,13 @@
       <contentTypeBinding

             contentTypeId="org.eclipse.pde.bundleManifest"

             structureMergeViewerId="org.eclipse.pde.internal.ui.compare.ManifestStructureMergeViewerCreator"/>

+      <viewer

+            extensions="xml,exsd"

+            class="org.eclipse.pde.internal.ui.compare.XMLStructureViewerCreator"

+            id="org.eclipse.pde.internal.ui.compare.XMLStructureViewerCreator" />

+      <contentTypeBinding

+            structureMergeViewerId="org.eclipse.pde.internal.ui.compare.XMLStructureViewerCreator"

+            contentTypeId="org.eclipse.pde.pluginManifest" />

    </extension>

    <extension

          point="org.eclipse.compare.contentMergeViewers">

@@ -1769,6 +1776,13 @@
       <contentTypeBinding

             contentMergeViewerId="org.eclipse.pde.internal.ui.compare.ManifestContentMergeViewerCreator"

             contentTypeId="org.eclipse.pde.bundleManifest"/>

+      <viewer

+            class="org.eclipse.pde.internal.ui.compare.XMLContentMergeViewerCreator"

+            extensions="xml,exsd"

+            id="org.eclipse.pde.internal.ui.compare.XMLContentMergeViewerCreator"/>

+      <contentTypeBinding

+            contentMergeViewerId="org.eclipse.pde.internal.ui.compare.XMLContentMergeViewerCreator"

+            contentTypeId="org.eclipse.pde.pluginManifest" />

    </extension>

    <extension

          point="org.eclipse.ui.themes">

diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/PDEPluginImages.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/PDEPluginImages.java
index 661a7c4902..58231f1b9d 100644
--- a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/PDEPluginImages.java
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/PDEPluginImages.java
@@ -122,6 +122,7 @@ public class PDEPluginImages {
 	public static final ImageDescriptor DESC_OK_TRANSLATE_OBJ = create(PATH_OBJ, "ok_st_obj.gif"); //$NON-NLS-1$
 	public static final ImageDescriptor DESC_NO_TRANSLATE_OBJ = create(PATH_OBJ, "incomplete_tsk.gif"); //$NON-NLS-1$
 	public static final ImageDescriptor DESC_DISCOVERY = create(PATH_OBJ, "discovery.gif"); //$NON-NLS-1$
+	public static final ImageDescriptor DESC_XML_TEXT_NODE = create(PATH_OBJ, "xml_text_node.gif"); //$NON-NLS-1$
 	/**
 	 * OVR16
 	 */
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/AbstractMatching.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/AbstractMatching.java
new file mode 100644
index 0000000000..5ecbd85b30
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/AbstractMatching.java
@@ -0,0 +1,313 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import java.util.ArrayList;
+import java.util.Vector;
+
+import org.eclipse.compare.rangedifferencer.IRangeComparator;
+import org.eclipse.compare.rangedifferencer.RangeDifference;
+import org.eclipse.compare.rangedifferencer.RangeDifferencer;
+import org.eclipse.core.runtime.IProgressMonitor;
+
+/**
+ * @version 	1.0
+ * @author
+ */
+public abstract class AbstractMatching {
+
+	protected static final int NO_ENTRY = -1;//value with which fDT elements are initialized
+	protected static final String SIGN_ELEMENT= XMLStructureCreator.SIGN_ELEMENT;
+	int[][] fDT;//Distance Table; 1st index from fNLeft, 2nd index from fNRight
+	ArrayList[][] fDT_Matchings;//Mathing entries of children for a match. 1st index from fNLeft, 2nd index from fNRight
+	Vector fNLeft;
+	Vector fNRight;
+	Vector fMatches;
+	
+	/* methods used for match */
+
+	/* finds all the leaves of a tree and puts them in a vector */
+	protected void findLeaves(XMLNode root, ArrayList leaves) {
+		if (isLeaf(root)) {
+			leaves.add(root);			
+		} else {
+			Object[] children = root.getChildren();
+			for (int i=0; i<children.length; i++)
+				findLeaves((XMLNode) children[i], leaves);
+		}
+	}
+
+	/* true if x is a leaf */
+	protected boolean isLeaf(XMLNode x) {
+		if (x == null) return true;
+		return x.getChildren() == null || x.getChildren().length <= 0;
+	}
+
+	/* Numbers all nodes of tree. The number of x is its index in the vector numbering */
+	protected void numberNodes(XMLNode root, Vector numbering) {
+		if (root != null) {
+			numbering.add(root);
+			Object[] children = root.getChildren();
+			if (children != null) {
+				for (int i=0; i<children.length; i++)
+					numberNodes((XMLNode) children[i], numbering);
+			}
+		}
+	}
+	
+	/* counts # of nodes in tree including root */
+	protected int countNodes(XMLNode root) {
+		if (root == null) return 0;
+		int count = 1;
+		if (isLeaf(root)) return count;
+		Object[] children = root.getChildren();
+		for (int i=0; i<children.length; i++)
+			count+=countNodes((XMLNode) children[i]);
+		return count;
+	}
+
+	/* returns index of node x in fNLeft */
+	protected int indexOfLN (XMLNode x) {
+		int i= 0;
+		while ((i<fNLeft.size()) && (fNLeft.elementAt(i) != x))
+			i++;
+		return i;
+	}
+	
+	/* returns index of node y in fNRight */
+	protected int indexOfRN (XMLNode y) {
+		int j= 0;
+		while ((j<fNRight.size()) && (fNRight.elementAt(j) != y))
+			j++;
+		return j;
+	}
+
+/* for testing */
+ 	public Vector getMatches() {
+  		return fMatches;
+   	}
+
+	protected class XMLComparator implements IRangeComparator {
+	
+		private Object[] fXML_elements;
+	
+		public XMLComparator(Object[] xml_elements) {
+			fXML_elements= xml_elements;
+		}
+	
+		/*
+		 * @see IRangeComparator#getRangeCount()
+		 */
+		public int getRangeCount() {
+			return fXML_elements.length;
+		}
+	
+		/*
+		 * @see IRangeComparator#rangesEqual(int, IRangeComparator, int)
+		 */
+		public boolean rangesEqual(
+			int thisIndex,
+			IRangeComparator other_irc,
+			int otherIndex) {
+			
+			if (other_irc instanceof XMLComparator) {
+				XMLComparator other= (XMLComparator) other_irc;
+				//return ((XMLNode)fXML_elements[thisIndex]).subtreeEquals(other.getXML_elements()[otherIndex]);
+				
+				//ordered compare of subtrees
+				//boolean result= ((XMLNode)fXML_elements[thisIndex]).subtreeEquals(other.getXML_elements()[otherIndex]);
+				
+				//taking ids into account
+				boolean sameId= false;
+				XMLNode thisNode= (XMLNode)fXML_elements[thisIndex];
+				XMLNode otherNode= (XMLNode)other.getXML_elements()[otherIndex]; 
+				if ( thisNode.usesIDMAP() && otherNode.usesIDMAP() ) {
+					if ( otherNode.getOrigId().equals(thisNode.getOrigId()) ) {
+						sameId= true;
+					}
+				}
+				
+				//unordered compare of subtrees
+				int distance= dist((XMLNode)other.getXML_elements()[otherIndex] , (XMLNode)fXML_elements[thisIndex]);
+				return sameId || distance == 0;
+			}
+			return false;
+		}
+	
+		/*
+		 * @see IRangeComparator#skipRangeComparison(int, int, IRangeComparator)
+		 */
+		public boolean skipRangeComparison(
+			int length,
+			int maxLength,
+			IRangeComparator other) {
+			return false;
+		}
+	
+		public Object[] getXML_elements() {
+			return fXML_elements;
+		}
+	
+	}
+
+	/* represents a matching between a node in the Left tree and a node in the Right tree */
+	class Match {
+		public XMLNode fx;
+		public XMLNode fy;
+		
+		Match(XMLNode x, XMLNode y) {
+			fx = x;
+			fy = y;	
+		}
+		
+		public boolean equals(Object obj) {
+			if (obj instanceof Match) {
+				Match m = (Match) obj;
+				if (m != null)
+					return fx == m.fx && fy == m.fy;
+			}
+			return false;
+		}
+	}
+	
+	protected int handleRangeDifferencer(Object[] xc_elements, Object[] yc_elements, ArrayList DTMatching, int distance) {
+		RangeDifference[] differences= RangeDifferencer.findDifferences(new XMLComparator(xc_elements), new XMLComparator(yc_elements));
+		
+		int cur_pos_left= 0;
+		int cur_pos_right= 0;
+		for (int i= 0; i < differences.length; i++) {
+			RangeDifference rd= differences[i];
+			int equal_length= rd.leftStart();
+			//handle elements before current range which are unchanged
+			while (cur_pos_left < equal_length) {
+				//assuming XMLComparator has already filled fDT and fDT_Matchings for subtrees
+				//rooted at xc_elements[cur_pos_left] and yc_elements[cur_pos_right]
+//				if ( fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])] != 0)
+//					System.out.println("distance not 0");
+//				distance += fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])];
+				//DTMatching.addAll(fDT_Matchings[index_left][index_right]);
+				DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right]));
+				cur_pos_left++;
+				cur_pos_right++;
+			}
+			//now handle RangeDifference rd[i]
+			int smaller_length, greater_length;
+			boolean leftGreater= rd.leftLength() > rd.rightLength();
+			if (leftGreater) {
+				smaller_length= rd.rightLength();
+				greater_length= rd.leftLength();
+			} else {
+				smaller_length= rd.leftLength();
+				greater_length= rd.rightLength();
+			}
+			
+			//handle elements elements in range
+			for (int j=0; j < smaller_length; j++) {
+				distance += dist((XMLNode) xc_elements[cur_pos_left], (XMLNode) yc_elements[cur_pos_right]);
+				DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right]));
+				cur_pos_left++;
+				cur_pos_right++;
+			}
+			//int cur_pos_greater= (leftGreater)?cur_pos_left:cur_pos_right;
+			if (leftGreater) {
+				for (int j=smaller_length; j < greater_length; j++) {
+					distance += countNodes((XMLNode) xc_elements[cur_pos_left]);
+					DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], null));
+					cur_pos_left++;
+				}
+			} else {
+				for (int j=smaller_length; j < greater_length; j++) {
+					distance += countNodes((XMLNode) yc_elements[cur_pos_right]);
+				DTMatching.add(new Match( null, (XMLNode)yc_elements[cur_pos_right]));
+					cur_pos_right++;
+				}
+			}
+//			for (int j=smaller_length; j < greater_length; j++) {
+//				distance += countNodes((XMLNode) xc_elements[cur_pos_greater]);
+//				cur_pos_greater++;
+//			}
+//			if (leftGreater)
+//				cur_pos_left= cur_pos_greater;
+//			else
+//				cur_pos_right= cur_pos_greater;
+		}
+		
+		for (int i= cur_pos_left; i < xc_elements.length; i++) {
+			//distance += fDT[indexOfLN( (XMLNode)xc_elements[cur_pos_left])][indexOfRN( (XMLNode)yc_elements[cur_pos_right])];
+			//DTMatching.addAll(fDT_Matchings[index_left][index_right]);
+			DTMatching.add(new Match( (XMLNode)xc_elements[cur_pos_left], (XMLNode)yc_elements[cur_pos_right]));
+			cur_pos_left++;
+			cur_pos_right++;
+		}
+		
+		return distance;
+	}
+
+	abstract public void match(XMLNode LeftTree, XMLNode RightTree, boolean rightTreeIsAncestor, IProgressMonitor monitor) throws InterruptedException;
+
+	protected int dist(XMLNode x, XMLNode y) {
+		//System.out.println("dist( "+x.getSignature()+" , "+y.getSignature()+")");
+		int ret= NO_ENTRY;
+
+		int index_x= indexOfLN(x);
+		int index_y= indexOfRN(y);
+		if (fDT[index_x][index_y] != NO_ENTRY) return fDT[index_x][index_y];
+		
+		if (isLeaf(x) && isLeaf(y)) {
+			if (x.getXMLType() == XMLStructureCreator.TYPE_ELEMENT) {
+				if ( x.getSignature().equals(y.getSignature()) ) {
+					ret= 0;
+					fDT[index_x][index_y] = ret;
+				} else {
+					ret= 2;
+					fDT[index_x][index_y] = ret;
+				}
+				return ret;
+			} else if (x.getXMLType() == XMLStructureCreator.TYPE_ATTRIBUTE || x.getXMLType() == XMLStructureCreator.TYPE_TEXT) {
+				if ( x.getSignature().equals(y.getSignature()) ) {
+					if (x.getValue().equals(y.getValue())) {
+						ret= 0;
+						fDT[index_x][index_y] = ret;
+					} else {
+						ret= 1;
+						fDT[index_x][index_y] = ret;
+					}
+				} else {
+					ret= 2;
+					fDT[index_x][index_y] = ret;
+				}
+				return ret;
+			}
+		} else {//x or y are not leaves
+			if ( !x.getSignature().equals(y.getSignature()) ) {
+				ret= countNodes(x) + countNodes(y);
+				fDT[index_x][index_y] = ret;
+				return ret;
+			}
+			//x.getSignature().equals(y.getSignature())
+			if (isLeaf(x)) {
+				ret= countNodes(y)-1;
+				fDT[index_x][index_y] = ret;
+				return ret;
+			}
+			if (isLeaf(y)) {
+				ret= countNodes(x)-1;
+				fDT[index_x][index_y] = ret;
+				return ret;
+			}
+			//both x and y have children
+			return handleXandYnotLeaves(x,y);
+		}
+		return ret;
+	}
+	
+	abstract int handleXandYnotLeaves(XMLNode x, XMLNode y);
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/AttributesImpl.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/AttributesImpl.java
new file mode 100644
index 0000000000..b62f9a3996
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/AttributesImpl.java
@@ -0,0 +1,331 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import org.xml.sax.Attributes;
+
+/**
+ * An Attributes implementation that can perform more operations
+ * than the attribute list helper supplied with the standard SAX2
+ * distribution.
+ */
+public class AttributesImpl implements Attributes {
+
+	/** Head node. */
+	private ListNode fHead;
+
+	/** Tail node. */
+	private ListNode fTail;
+
+	/** Length. */
+	private int fLength;
+
+
+	/* Returns the number of attributes. */
+	public int getLength() {
+		return fLength;
+	}
+
+	/* Returns the index of the specified attribute. */
+	public int getIndex(String raw) {
+		ListNode place= fHead;
+		int index= 0;
+		while (place != null) {
+			if (place.raw.equals(raw)) {
+				return index;
+			}
+			index++;
+			place= place.next;
+		}
+		return -1;
+	}
+
+	/* Returns the index of the specified attribute. */
+	public int getIndex(String uri, String local) {
+		ListNode place= fHead;
+		int index= 0;
+		while (place != null) {
+			if (place.uri.equals(uri) && place.local.equals(local)) {
+				return index;
+			}
+			index++;
+			place= place.next;
+		}
+		return -1;
+	}
+
+	/* Returns the attribute URI by index. */
+	public String getURI(int index) {
+
+		ListNode node= getListNodeAt(index);
+		return node != null ? node.uri : null;
+	}
+
+	/* Returns the attribute local name by index. */
+	public String getLocalName(int index) {
+
+		ListNode node= getListNodeAt(index);
+		return node != null ? node.local : null;
+	}
+
+	/* Returns the attribute raw name by index. */
+	public String getQName(int index) {
+
+		ListNode node= getListNodeAt(index);
+		return node != null ? node.raw : null;
+
+	}
+
+	/* Returns the attribute type by index. */
+	public String getType(int index) {
+
+		ListNode node= getListNodeAt(index);
+		return (node != null) ? node.type : null;
+	}
+
+	/* Returns the attribute type by uri and local. */
+	public String getType(String uri, String local) {
+
+		ListNode node= getListNode(uri, local);
+		return (node != null) ? node.type : null;
+
+	}
+
+	/* Returns the attribute type by raw name. */
+	public String getType(String raw) {
+
+		ListNode node= getListNode(raw);
+		return (node != null) ? node.type : null;
+	}
+
+	/* Returns the attribute value by index. */
+	public String getValue(int index) {
+
+		ListNode node= getListNodeAt(index);
+		return (node != null) ? node.value : null;
+	}
+
+	/* Returns the attribute value by uri and local. */
+	public String getValue(String uri, String local) {
+
+		ListNode node= getListNode(uri, local);
+		return (node != null) ? node.value : null;
+	}
+
+	/* Returns the attribute value by raw name. */
+	public String getValue(String raw) {
+
+		ListNode node= getListNode(raw);
+		return (node != null) ? node.value : null;
+	}
+
+	/* Adds an attribute. */
+	public void addAttribute(String raw, String type, String value) {
+		addAttribute(null, null, raw, type, value);
+	}
+
+	/* Adds an attribute. */
+	public void addAttribute(
+		String uri,
+		String local,
+		String raw,
+		String type,
+		String value) {
+
+		ListNode node= new ListNode(uri, local, raw, type, value);
+		if (fLength == 0) {
+			fHead= node;
+		} else {
+			fTail.next= node;
+		}
+		fTail= node;
+		fLength++;
+	}
+
+	/* Inserts an attribute. */
+	public void insertAttributeAt(
+		int index,
+		String raw,
+		String type,
+		String value) {
+		insertAttributeAt(index, null, null, raw, type, value);
+	}
+
+	/* Inserts an attribute. */
+	public void insertAttributeAt(
+		int index,
+		String uri,
+		String local,
+		String raw,
+		String type,
+		String value) {
+
+		// if list is empty, add attribute
+		if (fLength == 0 || index >= fLength) {
+			addAttribute(uri, local, raw, type, value);
+			return;
+		}
+
+		// insert at beginning of list
+		ListNode node= new ListNode(uri, local, raw, type, value);
+		if (index < 1) {
+			node.next= fHead;
+			fHead= node;
+		} else {
+			ListNode prev= getListNodeAt(index - 1);
+			node.next= prev.next;
+			prev.next= node;
+		}
+		fLength++;
+	}
+
+	/* Removes an attribute. */
+	public void removeAttributeAt(int index) {
+
+		if (fLength == 0)
+			return;
+
+		if (index == 0) {
+			fHead= fHead.next;
+			if (fHead == null) {
+				fTail= null;
+			}
+			fLength--;
+		} else {
+			ListNode prev= getListNodeAt(index - 1);
+			ListNode node= getListNodeAt(index);
+			if (node != null) {
+				prev.next= node.next;
+				if (node == fTail) {
+					fTail= prev;
+				}
+				fLength--;
+			}
+		}
+	}
+
+	/* Removes the specified attribute. */
+	public void removeAttribute(String raw) {
+		removeAttributeAt(getIndex(raw));
+	}
+
+	/* Removes the specified attribute. */
+	public void removeAttribute(String uri, String local) {
+		removeAttributeAt(getIndex(uri, local));
+	}
+
+	/* Returns the node at the specified index. */
+	private ListNode getListNodeAt(int i) {
+
+		for (ListNode place= fHead; place != null; place= place.next) {
+			if (--i == -1) {
+				return place;
+			}
+		}
+		return null;
+	}
+
+	/* Returns the first node with the specified uri and local. */
+	public ListNode getListNode(String uri, String local) {
+
+		if (uri != null && local != null) {
+			ListNode place= fHead;
+			while (place != null) {
+				if (place.uri != null
+					&& place.local != null
+					&& place.uri.equals(uri)
+					&& place.local.equals(local)) {
+					return place;
+				}
+				place= place.next;
+			}
+		}
+		return null;
+	}
+
+	/* Returns the first node with the specified raw name. */
+	private ListNode getListNode(String raw) {
+
+		if (raw != null) {
+			for (ListNode place= fHead; place != null; place= place.next) {
+				if (place.raw != null && place.raw.equals(raw)) {
+					return place;
+				}
+			}
+		}
+
+		return null;
+	}
+
+	/* Returns a string representation of this object. */
+	public String toString() {
+		StringBuffer str= new StringBuffer();
+
+		str.append('[');
+		str.append("len="); //$NON-NLS-1$
+		str.append(fLength);
+		str.append(", {"); //$NON-NLS-1$
+		for (ListNode place= fHead; place != null; place= place.next) {
+			str.append(place.toString());
+			if (place.next != null) {
+				str.append(", "); //$NON-NLS-1$
+			}
+		}
+		str.append("}]"); //$NON-NLS-1$
+
+		return str.toString();
+	}
+
+	/*
+	 * An attribute node.
+	 */
+	static class ListNode {
+
+		/** Attribute uri. */
+		public String uri;
+
+		/** Attribute local. */
+		public String local;
+
+		/** Attribute raw. */
+		public String raw;
+
+		/** Attribute type. */
+		public String type;
+
+		/** Attribute value. */
+		public String value;
+
+		/** Next node. */
+		public ListNode next;
+
+		/* Constructs a list node. */
+		public ListNode(
+			String uri0,
+			String local0,
+			String raw0,
+			String type0,
+			String value0) {
+
+			this.uri= uri0;
+			this.local= local0;
+			this.raw= raw0;
+			this.type= type0;
+			this.value= value0;
+
+		}
+
+		/* Returns string representation of this object. */
+		public String toString() {
+			return raw != null ? raw : local;
+		}
+	}
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/OrderedMatching.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/OrderedMatching.java
new file mode 100644
index 0000000000..9d960aed9f
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/OrderedMatching.java
@@ -0,0 +1,176 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.ListIterator;
+import java.util.Vector;
+
+import org.eclipse.core.runtime.IProgressMonitor;
+
+public class OrderedMatching extends AbstractMatching {
+
+	public OrderedMatching() {
+		super();
+	}
+
+	protected int orderedMath(XMLNode x, XMLNode y) {
+		//assumes x and y have children
+		Object[] xc = x.getChildren();
+		Object[] yc = y.getChildren();
+
+		ArrayList xc_elementsAL = new ArrayList();
+		ArrayList xc_attrsAL = new ArrayList();
+
+		ArrayList yc_elementsAL = new ArrayList();
+		ArrayList yc_attrsAL = new ArrayList();
+
+		//find attributes and elements and put them in xc_elementsAL and xc_attrsAL, respectively
+		for (int i = 0; i < xc.length; i++) {
+			XMLNode x_i = (XMLNode) xc[i];
+			if (x_i.getXMLType().equals(XMLStructureCreator.TYPE_ELEMENT)) {
+				xc_elementsAL.add(x_i);
+			} else if (
+				x_i.getXMLType().equals(XMLStructureCreator.TYPE_ATTRIBUTE)) {
+				xc_attrsAL.add(x_i);
+			}
+		}
+
+		//do the same for yc				
+		for (int i = 0; i < yc.length; i++) {
+			XMLNode y_i = (XMLNode) yc[i];
+			if (y_i.getXMLType().equals(XMLStructureCreator.TYPE_ELEMENT)) {
+				yc_elementsAL.add(y_i);
+			} else if (
+				y_i.getXMLType().equals(XMLStructureCreator.TYPE_ATTRIBUTE)) {
+				yc_attrsAL.add(y_i);
+			}
+		}
+
+		Object[] xc_elements = xc_elementsAL.toArray();
+		Object[] yc_elements = yc_elementsAL.toArray();
+
+		ArrayList DTMatching = new ArrayList();
+		// Matching to be added to Entry in fDT_Matchings
+		int distance = 0; //distance to be added to entry in fDT
+
+		// perform unordered matching on attributes
+		// this updates fDT and fDT_Matchings
+		if (xc_attrsAL.size() > 0 || yc_attrsAL.size() > 0) {
+			if (xc_attrsAL.size() == 0)
+				distance += yc_attrsAL.size();
+			else if (yc_attrsAL.size() == 0)
+				distance += xc_attrsAL.size();
+			else {
+				distance = handleAttributes(xc_attrsAL, yc_attrsAL, DTMatching);
+			}
+		}
+
+		distance = handleRangeDifferencer(
+				xc_elements,
+				yc_elements,
+				DTMatching,
+				distance);
+
+		fDT[indexOfLN(x)][indexOfRN(y)]= distance;
+		fDT_Matchings[indexOfLN(x)][indexOfRN(y)]= DTMatching;
+		return distance;
+
+	}
+
+	/* matches two trees according to paper "X-Diff", p. 16 */
+	public void match(XMLNode LeftTree, XMLNode RightTree, boolean rightTreeIsAncestor,
+			IProgressMonitor monitor) throws InterruptedException {
+
+		fNLeft = new Vector();
+		//numbering LeftTree: Mapping nodes in LeftTree to numbers to be used as array indexes
+		fNRight = new Vector();
+		//numbering RightTree: Mapping nodes in RightTree to numbers to be used as array indexes
+		numberNodes(LeftTree, fNLeft);
+		numberNodes(RightTree, fNRight);
+		fDT = new int[fNLeft.size()][fNRight.size()];
+		fDT_Matchings = new ArrayList[fNLeft.size()][fNRight.size()];
+		for (int i = 0; i < fDT.length; i++) {
+			fDT[i] = new int[fNRight.size()];
+			for (int j = 0; j < fDT[0].length; j++) {
+				fDT[i][j] = NO_ENTRY;
+			}
+		}
+
+		dist(LeftTree, RightTree);
+		//		/* mark matchings on LeftTree and RightTree */
+		fMatches = new Vector();
+		if (!LeftTree.getSignature().equals(RightTree.getSignature())) {
+			//matching is empty	
+		} else {
+			fMatches.add(new Match(LeftTree, RightTree));
+			for (int i_M = 0; i_M < fMatches.size(); i_M++) {
+				Match m = (Match) fMatches.elementAt(i_M);
+				if (!isLeaf(m.fx) && !isLeaf(m.fy)) {
+					if (fDT_Matchings[indexOfLN(m.fx)][indexOfRN(m.fy)] != null)
+						fMatches.addAll(fDT_Matchings[indexOfLN(m.fx)][indexOfRN(m.fy)]);
+				}
+			}
+		}
+		//end of Step2
+		/* Renumber Id of Nodes to follow Matches. Or for ancestor, copy over Id to ancestor */
+		if (rightTreeIsAncestor) {
+			for (ListIterator it_M = fMatches.listIterator(); it_M.hasNext();) {
+				Match m = (Match) it_M.next();
+				if (m.fx != null && m.fy != null)
+					m.fy.setId(m.fx.getId());
+			}
+		} else {
+			int newId = 0;
+			for (ListIterator it_M = fMatches.listIterator(); it_M.hasNext(); newId++) {
+				Match m = (Match) it_M.next();
+				if (m.fx != null)
+					m.fx.setId(Integer.toString(newId));
+				if (m.fy != null)
+					m.fy.setId(Integer.toString(newId));
+			}
+		}
+	}
+
+	public int handleAttributes(ArrayList xc_attrs, ArrayList yc_attrs, ArrayList DTMatching) {
+		int distance = 0;
+		x_for : for (
+			Iterator iter_xc = xc_attrs.iterator(); iter_xc.hasNext();) {
+			XMLNode x_attr = (XMLNode) iter_xc.next();
+			String x_attr_name = x_attr.getName();
+			for (Iterator iter_yc = yc_attrs.iterator(); iter_yc.hasNext();) {
+				XMLNode y_attr = (XMLNode) iter_yc.next();
+				if (y_attr.getName().equals(x_attr_name)) {
+					if (!y_attr.getValue().equals(x_attr.getValue()))
+						distance += 1;
+					DTMatching.add(new Match(x_attr, y_attr));
+					yc_attrs.remove(y_attr);
+					continue x_for;
+				}
+			}
+			DTMatching.add(new Match(x_attr, null));
+			distance += 1;
+		}
+
+		for (Iterator iter_yc = yc_attrs.iterator(); iter_yc.hasNext();) {
+			DTMatching.add(new Match(null, (XMLNode) iter_yc.next()));
+			distance += 1;
+		}
+
+		return distance;
+	}
+
+	protected int handleXandYnotLeaves(XMLNode x, XMLNode y) {
+		/* handle entries as ordered*/
+		return orderedMath(x, y);
+	}
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLChildren.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLChildren.java
new file mode 100644
index 0000000000..033f8c8de5
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLChildren.java
@@ -0,0 +1,29 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import java.util.HashMap;
+
+import org.eclipse.jface.text.IDocument;
+
+/** XMLNode that has children elements */
+public class XMLChildren extends XMLNode {
+	
+	public int children;	// counts the number of children
+	public HashMap childElements;	// maps the name of XML child elements to their # of occurence
+	
+	public XMLChildren(String XMLType, String id, String value, String signature, IDocument doc, int start, int length) {
+		super(XMLType, id, value, signature, doc, start, length);
+		children= 0;
+		childElements = new HashMap();
+	}
+}
+
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLContentMergeViewer.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLContentMergeViewer.java
new file mode 100644
index 0000000000..bd08a2f301
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLContentMergeViewer.java
@@ -0,0 +1,38 @@
+package org.eclipse.pde.internal.ui.compare;
+
+import org.eclipse.compare.CompareConfiguration;
+import org.eclipse.compare.contentmergeviewer.TextMergeViewer;
+import org.eclipse.jface.resource.JFaceResources;
+import org.eclipse.jface.text.IDocumentPartitioner;
+import org.eclipse.jface.text.TextViewer;
+import org.eclipse.jface.text.rules.FastPartitioner;
+import org.eclipse.jface.text.source.SourceViewer;
+import org.eclipse.pde.internal.ui.editor.text.ColorManager;
+import org.eclipse.pde.internal.ui.editor.text.IColorManager;
+import org.eclipse.pde.internal.ui.editor.text.XMLConfiguration;
+import org.eclipse.pde.internal.ui.editor.text.XMLPartitionScanner;
+import org.eclipse.swt.widgets.Composite;
+
+public class XMLContentMergeViewer extends TextMergeViewer {
+
+	public XMLContentMergeViewer(Composite parent, CompareConfiguration config) {
+		super(parent, config);
+	}
+
+	protected void configureTextViewer(TextViewer textViewer) {
+		if (textViewer instanceof SourceViewer) {
+			IColorManager colorManager = ColorManager.getDefault();
+			((SourceViewer)textViewer).configure(new XMLConfiguration(colorManager));
+			((SourceViewer)textViewer).getTextWidget().setFont(JFaceResources.getTextFont());
+		}
+	}
+
+	protected IDocumentPartitioner getDocumentPartitioner() {
+		return new FastPartitioner(new XMLPartitionScanner(), XMLPartitionScanner.PARTITIONS);
+	}
+	
+	public String getTitle() {
+		return XMLStructureCreator.DEFAULT_NAME; 
+	}
+
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLContentMergeViewerCreator.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLContentMergeViewerCreator.java
new file mode 100644
index 0000000000..0bd771dfa1
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLContentMergeViewerCreator.java
@@ -0,0 +1,13 @@
+package org.eclipse.pde.internal.ui.compare;
+
+import org.eclipse.compare.CompareConfiguration;
+import org.eclipse.compare.IViewerCreator;
+import org.eclipse.jface.viewers.Viewer;
+import org.eclipse.swt.widgets.Composite;
+
+public class XMLContentMergeViewerCreator implements IViewerCreator {
+
+	public Viewer createViewer(Composite parent, CompareConfiguration config) {
+		return new XMLContentMergeViewer(parent, config);
+	}
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLNode.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLNode.java
new file mode 100644
index 0000000000..d15b914475
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLNode.java
@@ -0,0 +1,163 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import org.eclipse.compare.CompareUI;
+import org.eclipse.compare.ITypedElement;
+import org.eclipse.compare.structuremergeviewer.DocumentRangeNode;
+import org.eclipse.jface.text.IDocument;
+import org.eclipse.swt.graphics.Image;
+
+/**
+ * Objects that make up the parse tree.
+ */
+public class XMLNode extends DocumentRangeNode implements ITypedElement {
+
+	private String fValue;
+	private String fName;
+	private String fSignature;
+	private String fOrigId;
+	private XMLNode parent;
+	private String fXMLType;
+	private boolean fUsesIDMAP;
+
+	public int bodies; // counts the number of bodies
+
+	public XMLNode(String XMLType, String id, String value, String signature, IDocument doc, int start, int length) {
+		super(0, id, doc, start, length);
+		fXMLType= XMLType;
+		fValue= value;
+		fSignature= signature;
+		fOrigId= id;
+		if (XMLStructureCreator.DEBUG_MODE)
+			System.out.println("Created XMLNode with XMLType: " + XMLType + ", id: " + id + ", value: " + value + ", signature: " + fSignature); //$NON-NLS-1$ //$NON-NLS-4$ //$NON-NLS-3$ //$NON-NLS-2$
+		bodies= 0;
+		fUsesIDMAP= false;
+	}
+
+	void setValue(String value) {
+		fValue= value;
+	}
+
+	String getValue() {
+		return fValue;
+	}
+
+	/*
+	 * @see ITypedElement#getName
+	 */
+	public String getName() {
+		if (fName != null)
+			return fName;
+		return this.getId();
+	}
+
+	public void setName(String name) {
+		fName= name;
+	}
+
+	/*
+	 * Every xml node is of type "txt" so that the builtin TextMergeViewer is used automatically.
+	 * @see ITypedElement#getType
+	 */
+	public String getType() {
+		return "txt"; //$NON-NLS-1$
+	}
+
+	
+	/*
+	 * @see ITypedElement#getImage
+	 */
+	public Image getImage() {
+		return CompareUI.getImage(XMLStructureMapping.getImageKey(getXMLType()));
+	}
+
+	public void setParent(XMLNode parent0) {
+		this.parent= parent0;
+	}
+
+	public XMLNode getParent() {
+		return this.parent;
+	}
+
+	String getXMLType() {
+		return fXMLType;
+	}
+
+	String getSignature() {
+		return fSignature;
+	}
+
+	void setOrigId(String id) {
+		fOrigId= id;
+	}
+
+	public String getOrigId() {
+		return fOrigId;
+	}
+
+	public void setUsesIDMAP(boolean b) {
+		fUsesIDMAP= b;
+	}
+
+	public boolean usesIDMAP() {
+		return fUsesIDMAP;
+	}
+
+	//for tests
+	public boolean testEquals(Object obj) {
+		if (obj instanceof XMLNode) {
+			XMLNode n= (XMLNode) obj;
+			return fValue.equals(n.getValue())
+				&& fSignature.equals(n.getSignature())
+				&& fXMLType.equals(n.getXMLType())
+				&& fUsesIDMAP == n.usesIDMAP();
+		}
+		return false;
+	}
+
+	/*
+	 * Returns true if the subtree rooted at this node is equals to the subtree rooted at <code>obj</code>
+	 */
+	public boolean subtreeEquals(Object obj) {
+		if (!testEquals(obj))
+			return false;
+		if (obj instanceof XMLNode) {
+			XMLNode n= (XMLNode) obj;
+			if (getXMLType().equals(XMLStructureCreator.TYPE_ATTRIBUTE)
+				&& n.getXMLType().equals(XMLStructureCreator.TYPE_ATTRIBUTE))
+				return true;
+			Object[] children= getChildren();
+			Object[] n_children= n.getChildren();
+			//if both nodes have no children, return true;
+			if ((children == null || children.length <= 0)
+				&& (n_children == null || n_children.length <= 0))
+				return true;
+			//now at least one of the two nodes has children;
+			/* so if one of the two nodes has no children, or they don't have the same number of children,
+			 * return false;
+			 */
+			if ((children == null || children.length <= 0)
+				|| (n_children == null || n_children.length <= 0)
+				|| (children.length != n_children.length))
+				return false;
+			//now both have children and the same number of children
+			for (int i= 0; i < children.length; i++) {
+				/* if the subtree rooted at children[i] is not equal to the subtree rooted at n_children[i],
+				 * return false
+				 */
+				if (!((XMLNode) children[i]).subtreeEquals(n_children[i]))
+					return false;
+			}
+		}
+		return true;
+	}
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureCreator.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureCreator.java
new file mode 100644
index 0000000000..822904b33a
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureCreator.java
@@ -0,0 +1,697 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.io.StringReader;
+import java.io.UnsupportedEncodingException;
+import java.text.MessageFormat;
+import java.util.HashMap;
+
+import javax.xml.parsers.SAXParser;
+import javax.xml.parsers.SAXParserFactory;
+
+import org.eclipse.compare.IEditableContent;
+import org.eclipse.compare.IEncodedStreamContentAccessor;
+import org.eclipse.compare.IStreamContentAccessor;
+import org.eclipse.compare.structuremergeviewer.IStructureComparator;
+import org.eclipse.compare.structuremergeviewer.IStructureCreator;
+import org.eclipse.core.runtime.CoreException;
+import org.eclipse.jface.text.BadLocationException;
+import org.eclipse.jface.text.Document;
+import org.eclipse.jface.text.IDocument;
+import org.eclipse.jface.text.IRegion;
+import org.eclipse.jface.text.Position;
+import org.eclipse.osgi.util.NLS;
+import org.eclipse.pde.internal.ui.PDEPlugin;
+import org.xml.sax.Attributes;
+import org.xml.sax.InputSource;
+import org.xml.sax.Locator;
+import org.xml.sax.SAXException;
+import org.xml.sax.SAXParseException;
+import org.xml.sax.helpers.DefaultHandler;
+import org.xml.sax.helpers.LocatorImpl;
+
+/**
+ * This structure analyzer builds a parse tree of an XML document found in a
+ * <code>IByteContentAccessor</code> input by calling getStructure(Object)
+ */
+public class XMLStructureCreator implements IStructureCreator {
+
+	protected static final boolean DEBUG_MODE = true;
+	public static final String DEFAULT_NAME = "XML Compare";
+	public static final String USE_UNORDERED = "Unordered";
+	public static final String USE_ORDERED = "Ordered";
+	
+	public static final String DEFAULT_IDMAP = XMLStructureMapping.ECLIPSE_PLUGIN;
+	public static final String TYPE_ROOT = "plugin"; //$NON-NLS-1$
+	public static final String TYPE_EXTENSION = "extension"; //$NON-NLS-1$
+	public static final String TYPE_EXTENSIONPOINT = "extension-point"; //$NON-NLS-1$
+	public static final String TYPE_ELEMENT = "element"; //$NON-NLS-1$
+	public static final String TYPE_TEXT = "text"; //$NON-NLS-1$
+	public static final String TYPE_ATTRIBUTE = "attribute"; //$NON-NLS-1$
+
+	// for signatures
+	public static final String ROOT_ID = "root"; //$NON-NLS-1$
+	public static final char SIGN_SEPARATOR = '>';//'.'
+	public static final char SIGN_ENCLOSING = '$';
+	public static final String SIGN_ELEMENT = SIGN_ENCLOSING + TYPE_ELEMENT	+ SIGN_ENCLOSING;
+	public static final String SIGN_TEXT = SIGN_ENCLOSING + TYPE_TEXT + SIGN_ENCLOSING;
+	public static final String SIGN_ATTRIBUTE = SIGN_ENCLOSING + TYPE_ATTRIBUTE + SIGN_ENCLOSING;
+	public static final char ID_SEPARATOR = '<';
+	public static final char ID_TYPE_BODY = '<';
+
+	private XMLNode fCurrentParent;
+	private String fSignature;
+	private Document fDoc;
+	private boolean ignoreBodies = false;
+	private HashMap fIdMapsInternal;
+    private HashMap idMap;
+	private String fIdMapToUse;
+	private boolean fRemoveWhiteSpace;
+
+	protected class XMLHandler extends DefaultHandler {
+
+		protected Locator prevlocator; //previous locator
+		protected Locator locator; //current locator
+
+		public void setDocumentLocator(Locator locator) {
+			this.locator = locator;
+		}
+
+		public void processingInstruction(String target, String data) {
+			prevlocator = new LocatorImpl(locator);
+		}
+
+		public void startDocument() {
+			prevlocator = new LocatorImpl(locator);
+		}
+
+		public void startElement(String uri, String local, String raw, Attributes attrs) {
+			/* add root node for this element */
+			if (XMLStructureCreator.DEBUG_MODE) {
+				if (locator != null && prevlocator != null) {
+					System.out.println("prevlocator: line " + prevlocator.getLineNumber() + "  column " + prevlocator.getColumnNumber() + "  id " + prevlocator.getPublicId()); //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+					System.out.println("locator: line " + locator.getLineNumber() + "  column " + locator.getColumnNumber() + "  id " + locator.getPublicId()); //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+				}
+			}
+
+			try {
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("Node where children field accessed: " + fCurrentParent.getId()); //$NON-NLS-1$
+				XMLChildren currentParent = (XMLChildren) fCurrentParent;
+				currentParent.children++;
+				String elementId;
+				String elementName;
+				IRegion r = fDoc.getLineInformation(prevlocator.getLineNumber() - 1);
+
+				fSignature = fSignature + raw + SIGN_SEPARATOR;
+
+				if (idMap.containsKey(fSignature)) {
+					String attrName = (String) idMap.get(fSignature);
+					String attrValue = attrs.getValue(attrName);
+					elementId = raw + new Character(ID_SEPARATOR) + attrValue;
+					elementName = raw;
+					if (attrValue != null)
+						elementName += " [" + attrName + "=" + attrs.getValue(attrName) + "]"; //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+				} else {
+					if (!currentParent.childElements.containsKey(raw)) {
+						currentParent.childElements.put(raw, new Integer(1));
+					} else {
+						currentParent.childElements.put(raw, new Integer(((Integer) currentParent.childElements.get(raw)).intValue() + 1));
+					}
+					elementId = raw + new Character(ID_SEPARATOR) + "[" + currentParent.childElements.get(raw) + "]"; //$NON-NLS-2$ //$NON-NLS-1$
+					elementName = MessageFormat.format("{0} [{1}]", new String[] { raw, currentParent.childElements.get(raw).toString() }); //$NON-NLS-1$
+				}
+				int start = r.getOffset() + prevlocator.getColumnNumber() - 1;
+				if (start < 0)
+					start = 0;
+				String type = TYPE_ELEMENT;
+				if (currentParent.getId() == ROOT_ID && elementName.startsWith(TYPE_ROOT))
+					type = TYPE_ROOT;
+				else if (currentParent.getXMLType().equals(TYPE_ROOT)) {
+					if (elementName.startsWith(TYPE_EXTENSIONPOINT))
+						type = TYPE_EXTENSIONPOINT;
+					else if (elementName.startsWith(TYPE_EXTENSION))
+						type = TYPE_EXTENSION;
+				}
+				XMLNode currentElement = new XMLChildren(type, elementId, elementId,
+						(fSignature + SIGN_ELEMENT), fDoc, start, 0);
+				currentElement.setName(elementName);
+				if (idMap.containsKey(fSignature))
+					currentElement.setUsesIDMAP(true);
+			
+				fCurrentParent.addChild(currentElement);
+				currentElement.setParent(fCurrentParent);
+				fCurrentParent = currentElement;
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("\nAdded Element " + raw + "  with offset " + r.getOffset()); //$NON-NLS-2$ //$NON-NLS-1$
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("fcurrentParent1: " + fCurrentParent.getId()); //$NON-NLS-1$
+
+				if (attrs != null) {
+					if (XMLStructureCreator.DEBUG_MODE)
+						System.out.println("attrs != null, fcurrentParent is " + fCurrentParent.getId()); //$NON-NLS-1$
+					int len = attrs.getLength();
+					int element_lines_length_size;
+					int[] element_lines_length;
+					int column_offset;
+					String element_string;
+					if (fCurrentParent.getParent().getId().equals(ROOT_ID)) {
+						element_lines_length_size = locator.getLineNumber() - prevlocator.getLineNumber();
+						element_lines_length = new int[element_lines_length_size];
+						column_offset = 0;
+						element_string = ""; //$NON-NLS-1$
+						for (int i_ell = 0; i_ell < element_lines_length.length; i_ell++) {
+							IRegion attr_r = fDoc.getLineInformation(i_ell + prevlocator.getLineNumber());
+							element_lines_length[i_ell] = fDoc.get(attr_r.getOffset(), attr_r.getLength()).length() + 1;
+							element_string = element_string + fDoc.get(attr_r.getOffset(), attr_r.getLength()) + " "; //$NON-NLS-1$
+						}
+					} else {
+						element_lines_length_size = locator.getLineNumber() - prevlocator.getLineNumber() + 1;
+						//if (element_lines_length_size < 1)
+						// element_lines_length_size = 1;
+						element_lines_length = new int[element_lines_length_size];
+						IRegion first_line = fDoc.getLineInformation(prevlocator.getLineNumber() - 1);
+						column_offset = prevlocator.getColumnNumber() - 1;
+						int first_line_relevant_offset = first_line.getOffset() + column_offset;
+						int first_line_relevant_length = first_line.getLength() - column_offset;
+						element_string = fDoc.get(first_line_relevant_offset, first_line_relevant_length) + " "; //$NON-NLS-1$
+						element_lines_length[0] = element_string.length();
+						for (int i_ell = 1; i_ell < element_lines_length.length; i_ell++) {
+							IRegion attr_r = fDoc.getLineInformation(i_ell + prevlocator.getLineNumber() - 1);
+							element_lines_length[i_ell] = fDoc.get(attr_r.getOffset(), attr_r.getLength()).length() + 1;
+							element_string = element_string + fDoc.get(attr_r.getOffset(), attr_r.getLength()) + " "; //$NON-NLS-1$
+						}
+					}
+
+					for (int i_attr = 0; i_attr < len; i_attr++) {
+						String attr_name = attrs.getQName(i_attr);
+						String attr_value = attrs.getValue(i_attr);
+
+						/*
+						 * find range of attribute in doc; manually parses the
+						 * line
+						 */
+						boolean found = false;
+						int first_quotes = -1;
+						int second_quotes = -1;
+						int id_index = -1;
+						while (!found) {
+							first_quotes = element_string.indexOf("\"", second_quotes + 1); //$NON-NLS-1$
+							second_quotes = element_string.indexOf("\"", first_quotes + 1); //$NON-NLS-1$
+							String value;
+							try {
+								value = element_string.substring(first_quotes + 1, second_quotes);
+							} catch (Exception e) {
+								value = ""; //$NON-NLS-1$
+							}
+							if (value.equals("")) //$NON-NLS-1$
+								found = true;
+							else if (value.equals(attr_value)) {
+								id_index = element_string.lastIndexOf(attr_name, first_quotes - 1);
+								boolean wrong = false;
+								boolean found_equal = false;
+								for (int i_char = id_index + attr_name.length(); i_char < first_quotes && !wrong; i_char++) {
+									if (element_string.charAt(i_char) == '=')
+										if (!found_equal)
+											found_equal = true;
+										else
+											wrong = true;
+									else if (!Character.isWhitespace(element_string.charAt(i_char)))
+										wrong = true;
+								}
+								if (!wrong)
+									found = true;
+							}
+						}
+						//id_index has one char missing for every line (the
+						// final cr)
+						int line_of_index = 0;
+						for (line_of_index = 0; id_index > element_lines_length[line_of_index] - 1; line_of_index++)
+							id_index -= (element_lines_length[line_of_index]);
+						if (line_of_index == 0)
+							id_index += column_offset;
+						if (fCurrentParent.getParent().getId().equals(ROOT_ID))
+							line_of_index += prevlocator.getLineNumber();
+						else
+							line_of_index += prevlocator.getLineNumber() - 1;
+						//index at line line_of_index, line offset id_index
+						int line_of_end_of_value = 0;
+						int end_of_value_index = second_quotes;
+						for (line_of_end_of_value = 0; end_of_value_index > element_lines_length[line_of_end_of_value] - 1; line_of_end_of_value++)
+							end_of_value_index -= (element_lines_length[line_of_end_of_value]);
+						if (line_of_end_of_value == 0)
+							end_of_value_index += column_offset;
+						if (fCurrentParent.getParent().getId().equals(ROOT_ID))
+							line_of_end_of_value += prevlocator.getLineNumber();
+						else
+							line_of_end_of_value += prevlocator.getLineNumber() - 1;
+						//end of value at line line_of_end_of_value, line
+						// offset end_of_value_index
+
+						int attr_start_doc_offset = fDoc.getLineInformation(line_of_index).getOffset() + id_index;
+						//int attr_length_doc_offset =
+						// fdoc.getLineInformation(line_of_value).getOffset()+value_index+attr_value.length()+1+(line_of_end_of_value-line_of_index)
+						// - attr_start_doc_offset;
+						int attr_length_doc_offset = fDoc.getLineInformation(line_of_end_of_value).getOffset() + end_of_value_index + 1 - attr_start_doc_offset;
+						currentElement = new XMLNode(TYPE_ATTRIBUTE, attr_name, attr_value, (fSignature + attr_name + SIGN_SEPARATOR + SIGN_ATTRIBUTE), fDoc, attr_start_doc_offset, attr_length_doc_offset);
+						currentElement.setName(attr_name);
+						fCurrentParent.addChild(currentElement);
+						currentElement.setParent(fCurrentParent);
+						if (XMLStructureCreator.DEBUG_MODE)
+							System.out.println("added attribute " + currentElement.getId() + " with value >" + currentElement.getValue() + "<" + " to element " + fCurrentParent.getId() + " which has parent " + fCurrentParent.getParent().getId()); //$NON-NLS-5$ //$NON-NLS-4$ //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+					}
+				}
+			} catch (BadLocationException ex) {
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("BadLocationException in startElement(...) " + ex); //$NON-NLS-1$
+				new XMLChildren(TYPE_ELEMENT, raw+ "_(" + ((XMLChildren) fCurrentParent).children + ")", raw + "_(" + ((XMLChildren) fCurrentParent).children + ")", (fSignature + SIGN_ELEMENT), fDoc, 0, 0); //$NON-NLS-4$ //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+			}
+			if (XMLStructureCreator.DEBUG_MODE)
+				System.out.println("At the end of startElement(...), fcurrentParent is " + fCurrentParent.getId()); //$NON-NLS-1$
+			prevlocator = new LocatorImpl(locator);
+		}
+
+		public void characters(char ch[], int start, int length) {
+			if (!ignoreBodies) {
+				String chars = new String(ch, start, length);
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("characters: >" + chars + "<"); //$NON-NLS-2$ //$NON-NLS-1$
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("Body Location: line " + locator.getLineNumber() + "  column " + locator.getColumnNumber()); //$NON-NLS-2$ //$NON-NLS-1$
+
+				//if text contains only white space, it will be ignored.
+				if (!trimWhiteSpace(chars).equals("")) { //$NON-NLS-1$
+					if (XMLStructureCreator.DEBUG_MODE)
+						System.out.println("Adding body"); //$NON-NLS-1$
+					try {
+						IRegion r = fDoc.getLineInformation(locator.getLineNumber() - 1);
+						//location returns the END of the characters
+						//offset of BEGINNING of characters:
+						int offset = r.getOffset() + locator.getColumnNumber() - 1 - length;
+						fCurrentParent.bodies++;
+						String body_value = new String(ch, start, length);
+						if (fRemoveWhiteSpace) {
+							body_value = removeWhiteSpace(body_value);
+						}
+						XMLNode bodynode = new XMLNode(TYPE_TEXT, "body_(" + fCurrentParent.bodies + ")", body_value, (fSignature + SIGN_TEXT), fDoc, offset, length); //$NON-NLS-2$ //$NON-NLS-1$
+						bodynode.setName(NLS.bind("{0} ({1})", "body", Integer.toString(fCurrentParent.bodies))); //$NON-NLS-1$
+						fCurrentParent.addChild(bodynode);
+						bodynode.setParent(fCurrentParent);
+						if (XMLStructureCreator.DEBUG_MODE)
+							System.out.println("Created body " + fCurrentParent.bodies //$NON-NLS-1$
+											+ " with offset " + offset + " and length " + length //$NON-NLS-2$ //$NON-NLS-1$
+											+ " with parent " + bodynode.getParent().getId()); //$NON-NLS-1$
+						//bodies as id attributes
+						String popsig = fCurrentParent.getParent().getSignature(); //signature of parent of
+						// parent
+						popsig = popsig.substring(0, popsig.lastIndexOf(SIGN_ELEMENT));
+						if (fCurrentParent.bodies == 1 && idMap.containsKey(popsig)) {
+							String pid = fCurrentParent.getId();//id of parent
+							String pelementname = pid.substring(0, pid.indexOf("<")); //name of parent element //$NON-NLS-1$
+							if (((String) idMap.get(popsig)).equals(ID_TYPE_BODY + pelementname)) {
+								XMLNode pop = fCurrentParent.getParent();
+								String popid = pop.getId();
+								String popelementname = popid.substring(0, popid.indexOf("<")); //$NON-NLS-1$
+								pop.setId(popelementname + "<" + body_value); //$NON-NLS-1$
+								pop.setOrigId(popelementname + "<" + body_value); //$NON-NLS-1$
+								pop.setName(MessageFormat.format("{0} [{1}={2}]", new String[] { popelementname, pelementname, body_value })); //$NON-NLS-1$
+								pop.setUsesIDMAP(true);
+							}
+						}
+					} catch (BadLocationException ex) {
+						if (XMLStructureCreator.DEBUG_MODE)
+							System.out.println("BadLocationException in characters(...) " + ex); //$NON-NLS-1$
+						fCurrentParent.addChild(new XMLNode(TYPE_TEXT,"body_(" + fCurrentParent.bodies + ")", new String(ch, start, length), (fSignature + SIGN_TEXT), fDoc, 0, 0)); //$NON-NLS-2$ //$NON-NLS-1$
+					}
+				}
+			}
+			prevlocator = new LocatorImpl(locator);
+		}
+
+		public void ignorableWhitespace(char ch[], int start, int length) {
+			prevlocator = new LocatorImpl(locator);
+		}
+
+		public void endElement(String uri, String local, String raw) {
+			if (XMLStructureCreator.DEBUG_MODE)
+				System.out.println("\nExiting element " + fCurrentParent.getId()); //$NON-NLS-1$
+
+			if (XMLStructureCreator.DEBUG_MODE)
+				System.out.println("prevlocator: line " + prevlocator.getLineNumber() + "  column " + prevlocator.getColumnNumber() + "  id " + prevlocator.getPublicId()); //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+			if (XMLStructureCreator.DEBUG_MODE)
+				System.out.println("locator: line " + locator.getLineNumber() + "  column " + locator.getColumnNumber() + "  id " + locator.getPublicId()); //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+
+			if (fCurrentParent.getParent() != null) {
+				try {
+					IRegion r2 = fDoc.getLineInformation(locator.getLineNumber() - 1);
+					Position pos = fCurrentParent.getRange();
+
+					int elem_length = r2.getOffset() + locator.getColumnNumber() - 1 - pos.getOffset();//length of element from
+					// start tag to end tag
+					fCurrentParent.setLength(elem_length);
+					if (XMLStructureCreator.DEBUG_MODE)
+						System.out.println("pos.getOffset: " + pos.getOffset() + "  elem_length: " + elem_length); //$NON-NLS-2$ //$NON-NLS-1$
+					if (XMLStructureCreator.DEBUG_MODE)
+						System.out.println("fdoc.get(pos.getOffset()+elem_length-5,4): >" + fDoc.get(pos.getOffset() + elem_length - 5, 4) + "<"); //$NON-NLS-2$ //$NON-NLS-1$
+					
+					try {
+						fCurrentParent.setValue(fDoc.get(pos.getOffset(), elem_length));
+					} catch (BadLocationException ex) {
+						try {
+							fCurrentParent.setValue(fDoc.get(pos.getOffset(), elem_length - 1));
+						} catch (BadLocationException ex2) {
+							if (XMLStructureCreator.DEBUG_MODE) {
+								System.out.println("BadLocationException in endElement(...) while attempting fcurrentParent.setValue(...): " + ex); //$NON-NLS-1$
+								System.out.println("Attempt to correct BadLocationException failed: " + ex2); //$NON-NLS-1$
+							}
+						}
+					}
+					if (XMLStructureCreator.DEBUG_MODE)
+						System.out.println("Value of " + fCurrentParent.getId() + "  is >" + fCurrentParent.getValue() + "<"); //$NON-NLS-3$ //$NON-NLS-2$ //$NON-NLS-1$
+
+					//going from ending element to parent element
+					fCurrentParent = fCurrentParent.getParent();
+					if (XMLStructureCreator.DEBUG_MODE)
+						System.out.println("fcurrentParent = fcurrentParent.getParent();"); //$NON-NLS-1$
+				} catch (BadLocationException ex) {
+					if (XMLStructureCreator.DEBUG_MODE) {
+						System.out.println("BadLocationException in endElement(...): " + ex); //$NON-NLS-1$
+						System.out.println("fcurrentParent.getId(): " + fCurrentParent.getId()); //$NON-NLS-1$
+					}
+				}
+			} else {
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("Error: Cannot reach Parent of Parent"); //$NON-NLS-1$
+			}
+			if (XMLStructureCreator.DEBUG_MODE)
+				System.out.println("fcurrentParent is now " + fCurrentParent.getId()); //$NON-NLS-1$
+
+			prevlocator = new LocatorImpl(locator);
+			if (XMLStructureCreator.DEBUG_MODE)
+				System.out.println("Signature before cutting: " + fSignature); //$NON-NLS-1$
+			int ssi = fSignature.lastIndexOf(SIGN_SEPARATOR);
+			// second-last
+			// separator index
+			ssi = fSignature.lastIndexOf(SIGN_SEPARATOR, ssi - 1);
+			
+			fSignature = fSignature.substring(0, ssi + 1);
+			if (XMLStructureCreator.DEBUG_MODE)
+				System.out.println("Signature after cutting: " + fSignature); //$NON-NLS-1$
+		}
+
+		//
+		// ErrorHandler methods
+		//
+
+		/* Warning. */
+		public void warning(SAXParseException ex) {
+			System.err.println("[Warning] " + //$NON-NLS-1$
+					getLocationString(ex) + ": " + //$NON-NLS-1$
+					ex.getMessage());
+		}
+
+		/* Error. */
+		public void error(SAXParseException ex) {
+			System.err.println("[Error] " + //$NON-NLS-1$
+					getLocationString(ex) + ": " + //$NON-NLS-1$
+					ex.getMessage());
+		}
+
+		/* Fatal error. */
+		public void fatalError(SAXParseException ex) throws SAXException {
+			System.err.println("[Fatal Error] " + //$NON-NLS-1$
+					getLocationString(ex) + ": " + //$NON-NLS-1$
+					ex.getMessage());
+			//System.out.println(ex);
+			//throw ex;
+		}
+
+		/* Returns a string of the location. */
+		private String getLocationString(SAXParseException ex) {
+			StringBuffer str = new StringBuffer();
+
+			String systemId = ex.getSystemId();
+			if (systemId != null) {
+				int index = systemId.lastIndexOf('/');
+				if (index != -1)
+					systemId = systemId.substring(index + 1);
+				str.append(systemId);
+			}
+			str.append(':');
+			str.append(ex.getLineNumber());
+			str.append(':');
+			str.append(ex.getColumnNumber());
+
+			return str.toString();
+
+		}
+	}
+
+	public XMLStructureCreator() {
+		// set default idmap
+		fIdMapToUse = DEFAULT_IDMAP;
+		fIdMapsInternal = XMLStructureMapping.getMappings();
+		fRemoveWhiteSpace = false;
+	}
+
+	/*
+	 * This title will be shown in the title bar of the structure compare pane.
+	 */
+	public String getName() {
+		return DEFAULT_NAME;
+	}
+
+	/*
+	 * Set File extension of the parsed file. This extension will be used to choose an Id Map scheme.
+	 */
+	public void setFileExtension(String ext) {
+		if (ext.equals(".xml"))
+			setIdMap(XMLStructureMapping.ECLIPSE_PLUGIN);
+		else if (ext.equals(".exsd"))
+			setIdMap(XMLStructureMapping.ECLIPSE_SCHEMA);
+	}
+
+	/**
+	 * Initialize the Id Mappings for the Id Mapping Scheme and the Ordered Elements
+	 * This method must be called before getStructure(Object) is called on the two/three inputs of the compare
+	 */
+	public void initIdMaps() {
+		if (fIdMapsInternal.containsKey(fIdMapToUse)) {
+			idMap = (HashMap) fIdMapsInternal.get(fIdMapToUse);
+		} else {
+			idMap = new HashMap();
+		}
+
+	}
+
+	/*
+	 * Returns the XML parse tree of the input.
+	 */
+	public IStructureComparator getStructure(Object input) {
+		if (XMLStructureCreator.DEBUG_MODE)
+			System.out.println("Starting parse"); //$NON-NLS-1$
+
+		if (!(input instanceof IStreamContentAccessor))
+			return null;
+
+		IStreamContentAccessor sca = (IStreamContentAccessor) input;
+
+		try {
+			String contents = readString(sca);
+			if (contents == null)
+				contents = ""; //$NON-NLS-1$
+			fDoc = new Document(contents);
+
+			fSignature = ROOT_ID + SIGN_SEPARATOR;
+			XMLChildren root = new XMLChildren(TYPE_ELEMENT, ROOT_ID, "", (fSignature + SIGN_ELEMENT), fDoc, 0, fDoc.getLength()); //$NON-NLS-1$
+			fCurrentParent = root;
+
+			XMLHandler handler = new XMLHandler();
+
+			try {
+				SAXParserFactory factory = SAXParserFactory.newInstance();
+				factory.setNamespaceAware(true);
+				SAXParser parser = factory.newSAXParser();
+				parser.parse(new InputSource(new StringReader(contents)), handler);
+
+				if (XMLStructureCreator.DEBUG_MODE)
+					System.out.println("End of parse"); //$NON-NLS-1$
+			} catch (SAXParseException e) {
+				PDEPlugin.log(e);
+				return null;
+			} catch (Exception e) {
+				PDEPlugin.log(e);
+				return null;
+			}
+			return root;
+		} catch (CoreException ex) {
+			PDEPlugin.log(ex);
+		}
+		return null;
+	}
+
+	public void save(IStructureComparator structure, Object input) {
+		if (input instanceof IEditableContent && structure instanceof XMLNode) {
+			IDocument document = ((XMLNode) structure).getDocument();
+			IEditableContent bca = (IEditableContent) input;
+			String contents = document.get();
+			String encoding = null;
+			if (input instanceof IEncodedStreamContentAccessor) {
+				try {
+					encoding = ((IEncodedStreamContentAccessor) input).getCharset();
+				} catch (CoreException e) {
+					// ignore
+				}
+			}
+			if (encoding == null)
+				encoding = "UTF-8"; //$NON-NLS-1$
+			try {
+				bca.setContent(contents.getBytes(encoding));
+			} catch (UnsupportedEncodingException e) {
+				bca.setContent(contents.getBytes());
+			}
+		}
+	}
+
+	public String getContents(Object node, boolean ignoreWhitespace) {
+		if (node instanceof XMLNode) {
+			String s = ((XMLNode) node).getValue();
+			if (ignoreWhitespace)
+				s = s.trim();
+			return s;
+		}
+		return null;
+	}
+
+	public IStructureComparator locate(Object path, Object source) {
+		return null;
+	}
+
+	static String readString(IStreamContentAccessor sa) throws CoreException {
+		InputStream is = sa.getContents();
+		String encoding = null;
+		if (sa instanceof IEncodedStreamContentAccessor)
+			encoding = ((IEncodedStreamContentAccessor) sa).getCharset();
+		if (encoding == null)
+			encoding = "UTF-8"; //$NON-NLS-1$
+		return readString(is, encoding);
+	}
+
+	/*
+	 * Returns null if an error occurred.
+	 */
+	private static String readString(InputStream is, String encoding) {
+		if (is == null)
+			return null;
+		BufferedReader reader = null;
+		try {
+			StringBuffer buffer = new StringBuffer();
+			char[] part = new char[2048];
+			int read = 0;
+			reader = new BufferedReader(new InputStreamReader(is, encoding));
+
+			while ((read = reader.read(part)) != -1)
+				buffer.append(part, 0, read);
+
+			return buffer.toString();
+
+		} catch (IOException ex) {
+			// NeedWork
+		} finally {
+			if (reader != null) {
+				try {
+					reader.close();
+				} catch (IOException ex) {
+					// silently ignored
+				}
+			}
+		}
+		return null;
+	}
+
+	protected Attributes sortAttributes(Attributes attrs) {
+		AttributesImpl attributes = new AttributesImpl();
+		int len = (attrs != null) ? attrs.getLength() : 0;
+		for (int i = 0; i < len; i++) {
+			String name = attrs.getQName(i);
+			int count = attributes.getLength();
+			int j = 0;
+			while (j < count) {
+				if (name.compareTo(attributes.getQName(j)) < 0)
+					break;
+				j++;
+			}
+			attributes.insertAttributeAt(j, name, attrs.getType(i), attrs.getValue(i));
+		}
+		return attributes;
+
+	}
+
+	public void setIdMap(String idmap) {
+		fIdMapToUse = idmap;
+	}
+
+	public String getIdMap() {
+		return fIdMapToUse;
+	}
+
+	protected boolean isWhiteSpace(char c) {
+		return c == '\t' || c == '\n' || c == '\r' || c == ' ';
+	}
+
+	protected String removeWhiteSpace(String str) {
+		str = trimWhiteSpace(str);
+		StringBuffer retStr = new StringBuffer();
+		int start = 0, end = 0;
+		outer_while: while (true) {
+			while (end < str.length() && !isWhiteSpace(str.charAt(end))) {
+				end++;
+			}
+			if (end > str.length())
+				break outer_while;
+			if (start != 0)
+				retStr.append(' ');
+			retStr.append(str.substring(start, end));
+			end++;
+			while (end < str.length() && isWhiteSpace(str.charAt(end))) {
+				end++;
+			}
+			start = end;
+		}
+		return retStr.toString();
+	}
+
+	protected String trimWhiteSpace(String str) {
+		int start = 0, end = str.length() - 1;
+		while (start < str.length() && isWhiteSpace(str.charAt(start))) {
+			start++;
+		}
+		if (start == str.length())
+			return ""; //$NON-NLS-1$
+		while (end >= 0 && isWhiteSpace(str.charAt(end))) {
+			end--;
+		}
+		return str.substring(start, end + 1);
+	}
+
+	public void setRemoveWhiteSpace(boolean removeWhiteSpace) {
+		fRemoveWhiteSpace = removeWhiteSpace;
+	}
+
+	public boolean getRemoveWhiteSpace() {
+		return fRemoveWhiteSpace;
+	}
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureMapping.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureMapping.java
new file mode 100644
index 0000000000..67857c7571
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureMapping.java
@@ -0,0 +1,77 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+
+import org.eclipse.compare.CompareUI;
+import org.eclipse.pde.internal.ui.PDEPluginImages;
+
+/**
+ * This class is the plug-in runtime class for the 
+ * <code>"org.eclipse.compare.xml"</code> plug-in.
+ * </p>
+ */
+public final class XMLStructureMapping {
+	
+	public static final String PLUGIN_ID= "org.eclipse.compare.examples.xml"; //$NON-NLS-1$
+	public static final String ECLIPSE_PLUGIN = "Eclipse Plugin"; //$NON-NLS-1$
+	public static final String ECLIPSE_SCHEMA = "Eclipse Schema";
+	public static final String IMAGE_TYPE_PREFIX = "xml_"; //$NON-NLS-1$
+
+	private static HashMap fMappings;
+	private static HashMap fOrderedMappings;
+	static {
+		fMappings = new HashMap();
+		HashMap idmapHM = new HashMap();
+		idmapHM.put(getMapString("plugin"), "id"); //$NON-NLS-1$ //$NON-NLS-2$
+		idmapHM.put(getMapString("plugin>requires>import"), "plugin"); //$NON-NLS-1$ //$NON-NLS-2$
+		idmapHM.put(getMapString("plugin>runtime>library"), "name"); //$NON-NLS-1$ //$NON-NLS-2$
+		idmapHM.put(getMapString("plugin>runtime>library>export"), "name"); //$NON-NLS-1$ //$NON-NLS-2$
+		idmapHM.put(getMapString("plugin>extension-point"), "id"); //$NON-NLS-1$ //$NON-NLS-2$
+		idmapHM.put(getMapString("plugin>extension"), "point"); //$NON-NLS-1$ //$NON-NLS-2$
+		fMappings.put(ECLIPSE_PLUGIN, idmapHM);
+		
+		fOrderedMappings = new HashMap();
+		ArrayList orderedList = new ArrayList();
+		orderedList.add(getMapString("plugin"));
+		orderedList.add(getMapString("plugin>requires"));
+		orderedList.add(getMapString("plugin>runtime"));
+		orderedList.add(getMapString("plugin>extension-point"));
+		orderedList.add(getMapString("plugin>extension"));
+		fOrderedMappings.put(ECLIPSE_PLUGIN, orderedList);
+		
+		CompareUI.registerImageDescriptor(getImageKey(XMLStructureCreator.TYPE_ROOT), PDEPluginImages.DESC_PLUGIN_OBJ);
+		CompareUI.registerImageDescriptor(getImageKey(XMLStructureCreator.TYPE_EXTENSION), PDEPluginImages.DESC_EXTENSION_OBJ);
+		CompareUI.registerImageDescriptor(getImageKey(XMLStructureCreator.TYPE_EXTENSIONPOINT), PDEPluginImages.DESC_EXT_POINT_OBJ);
+		CompareUI.registerImageDescriptor(getImageKey(XMLStructureCreator.TYPE_ELEMENT), PDEPluginImages.DESC_XML_ELEMENT_OBJ); 
+		CompareUI.registerImageDescriptor(getImageKey(XMLStructureCreator.TYPE_ATTRIBUTE), PDEPluginImages.DESC_ATT_URI_OBJ);
+		CompareUI.registerImageDescriptor(getImageKey(XMLStructureCreator.TYPE_TEXT), PDEPluginImages.DESC_XML_TEXT_NODE);
+	}
+
+	protected static String getImageKey(String xmlType) {
+		return IMAGE_TYPE_PREFIX + xmlType;
+	}
+	
+	private static String getMapString(String signature) {
+		return XMLStructureCreator.ROOT_ID + XMLStructureCreator.SIGN_SEPARATOR + signature + XMLStructureCreator.SIGN_SEPARATOR;
+	}
+	
+	public static HashMap getMappings() {
+		return fMappings;
+	}
+	
+	public static HashMap getOrderedMappings() {
+		return fOrderedMappings;
+	}
+	
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureViewer.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureViewer.java
new file mode 100644
index 0000000000..88c50640e1
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureViewer.java
@@ -0,0 +1,194 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import java.lang.reflect.InvocationTargetException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+
+import org.eclipse.compare.CompareConfiguration;
+import org.eclipse.compare.ITypedElement;
+import org.eclipse.compare.structuremergeviewer.DiffNode;
+import org.eclipse.compare.structuremergeviewer.ICompareInput;
+import org.eclipse.compare.structuremergeviewer.IStructureComparator;
+import org.eclipse.compare.structuremergeviewer.StructureDiffViewer;
+import org.eclipse.core.runtime.IProgressMonitor;
+import org.eclipse.core.runtime.NullProgressMonitor;
+import org.eclipse.core.runtime.OperationCanceledException;
+import org.eclipse.core.runtime.SubProgressMonitor;
+import org.eclipse.jface.operation.IRunnableWithProgress;
+import org.eclipse.jface.viewers.Viewer;
+import org.eclipse.jface.viewers.ViewerSorter;
+import org.eclipse.pde.internal.ui.PDEPlugin;
+import org.eclipse.swt.widgets.Composite;
+import org.eclipse.ui.PlatformUI;
+
+/**
+ * An XML diff tree viewer that can be configured with a <code>IStructureCreator</code>
+ * to retrieve a hierarchical structure from the input object (an <code>ICompareInput</code>)
+ * and perform a two-way or three-way compare on it.
+ * <p>
+ * This class may be instantiated; it is not intended to be subclassed outside
+ * this package.
+ * </p>
+ *
+ * @see ICompareInput
+ */
+public class XMLStructureViewer extends StructureDiffViewer {
+	
+	class XMLSorter extends ViewerSorter {
+
+		public XMLSorter() {
+			super();
+		}
+
+		public int category(Object node) {
+			if (node instanceof DiffNode) {
+				Object o = ((DiffNode) node).getId();
+				if (o instanceof XMLNode) {
+					String xmlType= ((XMLNode) o).getXMLType();
+					if (xmlType.equals(XMLStructureCreator.TYPE_ATTRIBUTE))
+						return 1;
+					if (xmlType.equals(XMLStructureCreator.TYPE_ELEMENT) 
+							|| xmlType.equals(XMLStructureCreator.TYPE_TEXT)
+							|| xmlType.equals(XMLStructureCreator.TYPE_EXTENSION)
+							|| xmlType.equals(XMLStructureCreator.TYPE_EXTENSIONPOINT))
+						return 2;
+				}
+			}
+			return 0;
+		}
+
+		public void sort(final Viewer viewer, Object[] elements) {
+			if (elements != null
+					&& elements.length > 0
+					&& elements[0] instanceof DiffNode) {
+				Object o = ((DiffNode) elements[0]).getId();
+				if (o instanceof XMLNode) {
+					XMLNode parent = ((XMLNode) o).getParent();
+					String sig = parent.getSignature();
+					if (sig.endsWith(XMLStructureCreator.SIGN_ELEMENT)) {
+						final ArrayList originalTree =
+							new ArrayList(Arrays.asList(parent.getChildren()));
+						Arrays.sort(elements, new Comparator() {
+							public int compare(Object a, Object b) {
+								return XMLSorter.this.compare(
+									(DiffNode) a,
+									(DiffNode) b,
+									originalTree);
+							}
+						});
+						return;
+					}
+				}
+			}
+			super.sort(viewer, elements);
+		}
+
+		private int compare(DiffNode a, DiffNode b, ArrayList originalTree) {
+
+			int index_a = originalTree.indexOf(a.getId());
+			int index_b = originalTree.indexOf(b.getId());
+			if (index_a < index_b)
+				return -1;
+			return 1;
+		}
+	}
+
+	/**
+	 * Creates a new viewer under the given SWT parent with the specified configuration.
+	 *
+	 * @param parent the SWT control under which to create the viewer
+	 * @param configuration the configuration for this viewer
+	 */
+	public XMLStructureViewer(Composite parent, CompareConfiguration configuration) {
+		super(parent, configuration);
+		setStructureCreator(new XMLStructureCreator());
+		setSorter(new XMLSorter());
+	}
+
+
+	protected XMLStructureCreator getXMLStructureCreator() {
+		return (XMLStructureCreator) getStructureCreator();
+	}
+
+
+	/*
+	 * Recreates the comparable structures for the input sides.
+	 */
+	protected void compareInputChanged(ICompareInput input) {
+		if (input != null) {
+			ITypedElement t = input.getLeft();
+			if (t != null) {
+				String fileExtension = t.getType();
+				getXMLStructureCreator().setFileExtension(fileExtension);
+			}
+		}
+
+		getXMLStructureCreator().initIdMaps();
+		super.compareInputChanged(input);
+
+	}
+
+
+	public IRunnableWithProgress getMatchingRunnable(
+			final XMLNode left,
+			final XMLNode right,
+			final XMLNode ancestor) {
+		
+		return new IRunnableWithProgress() {
+			public void run(IProgressMonitor monitor) throws
+					InvocationTargetException,
+					InterruptedException,
+					OperationCanceledException {
+				
+				if (monitor == null)
+					monitor = new NullProgressMonitor();
+				
+				int totalWork;
+				if (ancestor != null)
+					totalWork = 1;
+				else
+					totalWork = 3;
+				monitor.beginTask("Running Matching algorithm...", totalWork); 
+				
+				AbstractMatching m = new OrderedMatching();
+				try {
+					m.match(left, right, false, monitor);
+					if (ancestor != null) {
+						m.match(left, ancestor, true,
+							new SubProgressMonitor(monitor, 1));
+						m.match(right, ancestor, true,
+							new SubProgressMonitor(monitor, 1));
+					}
+				} finally {
+					monitor.done();
+				}
+			}
+		};
+	}
+
+	protected void preDiffHook(
+			IStructureComparator ancestor,
+			IStructureComparator left,
+			IStructureComparator right) {
+		if (left != null && right != null) {
+			try {
+				PlatformUI.getWorkbench().getProgressService().run(true, true,
+					getMatchingRunnable((XMLNode) left, (XMLNode) right, (XMLNode) ancestor));
+			} catch (Exception e) {
+				PDEPlugin.log(e);
+			}
+		}
+	}
+
+}
diff --git a/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureViewerCreator.java b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureViewerCreator.java
new file mode 100644
index 0000000000..91358bdccc
--- /dev/null
+++ b/ui/org.eclipse.pde.ui/src/org/eclipse/pde/internal/ui/compare/XMLStructureViewerCreator.java
@@ -0,0 +1,31 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2004 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.pde.internal.ui.compare;
+
+import org.eclipse.swt.widgets.Composite;
+
+import org.eclipse.jface.viewers.Viewer;
+
+import org.eclipse.compare.CompareConfiguration;
+import org.eclipse.compare.IViewerCreator;
+
+/**
+ * A factory object for the <code>TextMergeViewer</code>.
+ * This indirection is necessary because only objects with a default
+ * constructor can be created via an extension point
+ * (this precludes Viewers).
+ */
+public class XMLStructureViewerCreator implements IViewerCreator {
+
+	public Viewer createViewer(Composite parent, CompareConfiguration mp) {
+		return new XMLStructureViewer(parent, mp);
+	}
+}