Changeset 830

Timestamp:

06/20/09 18:35:26 (3 years ago)

Author:

jharrop

Message:

WIP (lightly tested so far) implementation of top-down LCS based heuristic for improving differencing performance

Location:

trunk/docx4j

Files:

• lib/commons-lang-gump-20062009.jar (added)
• src/diffx/com/topologi/diffx/Docx4jDriver.java (added)
• src/diffx/com/topologi/diffx/Main.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/algorithm/DiffXFitopsy.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/AttributeEventImpl.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/AttributeEventNSImpl.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/CharEvent.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/DiffXEventBase.java (modified) (1 diff)
• src/diffx/com/topologi/diffx/event/impl/EventFactory.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/LineEvent.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/OpenElementEventImpl.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/OpenElementEventNSImpl.java (modified) (3 diffs)
• src/diffx/com/topologi/diffx/event/impl/ProcessingInstructionEvent.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/event/impl/XMLBranchEvent.java (modified) (2 diffs)
• src/diffx/com/topologi/diffx/load/DOMRecorder.java (modified) (3 diffs)
• src/diffx/com/topologi/diffx/sequence/EventSequence.java (modified) (9 diffs)
• src/diffx/com/topologi/diffx/sequence/PrefixMapping.java (modified) (1 diff)
• src/diffx/com/topologi/diffx/xml/NSAwareXMLWriter.java (modified) (4 diffs)
• src/diffx/org/eclipse/compare/EventSequenceComparator.java (added)
• src/diffx/org/eclipse/compare/StringComparator.java (moved) (moved from trunk/docx4j/src/main/java/org/docx4j/diff/StringComparator.java) (1 diff)
• src/main/java/org/docx4j/diff/MarkupDelete.xslt (modified) (1 diff)
• src/main/java/org/docx4j/diff/MarkupInsert.xslt (modified) (4 diffs)
• src/main/java/org/docx4j/diff/ParagraphDifferencer.java (modified) (16 diffs)
• src/main/java/org/docx4j/diff/diffx2wml.xslt (modified) (1 diff)

trunk/docx4j/src/diffx/com/topologi/diffx/Main.java

@@ -250 +250 @@
     diff(seq1, seq2, out, config);
   }
+  
+  // NB: The signatures which takes Reader objects appear to be broken!!
 
   /**
@@ -304 +306 @@
       throws DiffXException, IOException {
     SmartXMLFormatter formatter = new SmartXMLFormatter(out);
-    formatter.declarePrefixMapping(seq1.getPrefixMapping());
-    formatter.declarePrefixMapping(seq2.getPrefixMapping());
+    if (config != null) formatter.setConfig(config);
     
-    if (config != null) formatter.setConfig(config);
-    SequenceSlicer slicer = new SequenceSlicer(seq1, seq2);
-    slicer.slice();
-    slicer.formatStart(formatter);
-    DiffXAlgorithm df = new DiffXFitopsy(seq1, seq2);
-    df.process(formatter);
-    slicer.formatEnd(formatter);
-  }
-
+    diff(seq1, seq2, formatter, config);
+  }
+
+  public static void diff(EventSequence seq1, EventSequence seq2, SmartXMLFormatter formatter , DiffXConfig config)
+        throws DiffXException, IOException {
+            formatter.declarePrefixMapping(seq1.getPrefixMapping());
+            formatter.declarePrefixMapping(seq2.getPrefixMapping());
+            
+            if (config != null) formatter.setConfig(config);
+            SequenceSlicer slicer = new SequenceSlicer(seq1, seq2);
+            slicer.slice();
+            slicer.formatStart(formatter);
+            DiffXAlgorithm df = new DiffXFitopsy(seq1, seq2);
+            df.process(formatter);
+            slicer.formatEnd(formatter);
+  }
+  
 // command line ------------------------------------------------------------------------- 
 

trunk/docx4j/src/diffx/com/topologi/diffx/algorithm/DiffXFitopsy.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import com.topologi.diffx.Docx4jDriver;
 import com.topologi.diffx.event.DiffXEvent;
 import com.topologi.diffx.event.AttributeEvent;
@@ -227 +228 @@
     // handle the case when one of the two sequences is empty
     processEmpty(formatter);
+    
+    Docx4jDriver.log("length first: " + this.length1);
+    Docx4jDriver.log("length second: " + this.length2);
+    
     if (this.length1 == 0 || this.length2 == 0) return;
-    // calculate the LCS length to fill the matrix
+
+    // Phase I: calculate the LCS length to fill the matrix (slow for lengths in order of > 10^2)
+    long startTime = System.currentTimeMillis();
     length();
+    long endTime = System.currentTimeMillis();
+    long duration = endTime - startTime;
+    Docx4jDriver.log("diffx LCS phase took: " + duration + " ms ");
+    
     int i = 0;
     int j = 0;
     DiffXEvent e1 = sequence1.getEvent(i);
     DiffXEvent e2 = sequence2.getEvent(j);
-    // start walking the matrix
+    
+    
+    // Phase II: start walking the matrix (this should be quick)
     while (i < super.length1 && j < super.length2) {
       e1 = sequence1.getEvent(i);

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/AttributeEventImpl.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 import com.topologi.diffx.event.AttributeEvent;
 import com.topologi.diffx.event.DiffXEvent;
@@ -173 +175 @@
    * @see java.lang.Object#hashCode()
    */
-  public int hashCode() {
-    return this.name.hashCode() + this.value.hashCode();
-  }
+//  public int hashCode() {
+//    return this.name.hashCode() + this.value.hashCode();
+//  }
+
+  private int fHashCode;  
+  @Override public int hashCode() {
+            if ( fHashCode == 0) {
+                  // you pick a hard-coded, randomly chosen, non-zero, odd number
+                  // ideally different for each class
+              fHashCode = new HashCodeBuilder(17, 37).
+                                                          append(this.name).
+                                                          append(this.value).
+                                                          toHashCode();
+            }
+            return fHashCode;
+          }  
+  
 
   /**

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/AttributeEventNSImpl.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 import com.topologi.diffx.event.AttributeEvent;
 import com.topologi.diffx.event.DiffXEvent;
@@ -194 +196 @@
    * @see java.lang.Object#hashCode()
    */
-  public int hashCode() {
-    return this.name.hashCode() + this.value.hashCode();
-  }
-
+//  public int hashCode() {
+//    return this.name.hashCode() + this.value.hashCode();
+//  }
+
+  private int fHashCode;  
+  @Override public int hashCode() {
+            if ( fHashCode == 0) {
+                  // you pick a hard-coded, randomly chosen, non-zero, odd number
+                  // ideally different for each class
+              fHashCode = new HashCodeBuilder(17, 37).
+                                                          append(this.name).
+                                                          append(this.uri).
+                                                          append(this.value).
+                                                          toHashCode();
+            }
+            return fHashCode;
+          }  
+  
   /**
    * Returns <code>true</code> if the event is a  

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/CharEvent.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 import com.topologi.diffx.event.DiffXEvent;
 import com.topologi.diffx.xml.XMLWriter;
@@ -135 +137 @@
    * @see com.topologi.diffx.event.impl.DiffXEventBase#hashCode()
    */
-  public int hashCode() {
-    return c;
-  }
+//  public int hashCode() {
+//    return c;
+//  }
 
+  private int fHashCode;  
+  @Override public int hashCode() {
+            if ( fHashCode == 0) {
+                  // you pick a hard-coded, randomly chosen, non-zero, odd number
+                  // ideally different for each class
+              fHashCode = new HashCodeBuilder(17, 37).
+                                                          append(this.c).
+                                                          toHashCode();
+            }
+            return fHashCode;
+          }  
+  
+  
   /**
    * @see com.topologi.diffx.event.impl.DiffXEventBase#equals(com.topologi.diffx.event.DiffXEvent)

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/DiffXEventBase.java

@@ -133 +133 @@
    * @see java.lang.Object#hashCode()
    */
-  public abstract int hashCode();
+//  public abstract int hashCode();
 
   /**

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/EventFactory.java

@@ -1 +1 @@
 package com.topologi.diffx.event.impl;
 
+import com.topologi.diffx.Docx4jDriver;
 import com.topologi.diffx.event.AttributeEvent;
 import com.topologi.diffx.event.CloseElementEvent;
@@ -152 +153 @@
    */
   public AttributeEvent makeAttribute(String uri, String localName, String qName, String value) {
+          
+//      if (localName.equals("space")) {
+//              Docx4jDriver.log("space!");
+//              Docx4jDriver.log(uri);
+//              Docx4jDriver.log(qName);
+//      }         
+          
     if (this.isNamespaceAware) {
       return new AttributeEventNSImpl("".equals(uri)? null : uri, localName, value);

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/LineEvent.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 import com.topologi.diffx.event.DiffXEvent;
 import com.topologi.diffx.event.TextEvent;
@@ -154 +156 @@
    * @see java.lang.Object#hashCode()
    */
-  public int hashCode() {
-    return this.characters.hashCode();
-  }
-
+//  public int hashCode() {
+//    return this.characters.hashCode();
+//  }
+
+  private int fHashCode;  
+  @Override public int hashCode() {
+            if ( fHashCode == 0) {
+                  // you pick a hard-coded, randomly chosen, non-zero, odd number
+                  // ideally different for each class
+              fHashCode = new HashCodeBuilder(17, 37).
+                                                          append(this.characters).
+                                                          toHashCode();
+            }
+            return fHashCode;
+          }  
+  
+  
   /**
    * Returns <code>true</code> if the event is a character event and the content is equivalent.  

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/OpenElementEventImpl.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 
 import com.topologi.diffx.Constants;
@@ -159 +161 @@
    * @see java.lang.Object#hashCode()
    */
-  public int hashCode() {
-    return this.name.hashCode();
-  }
-
+//  public int hashCode() {
+//    return this.name.hashCode();
+//  }
+
+  private int fHashCode;  
+  @Override public int hashCode() {
+            if ( fHashCode == 0) {
+                  // you pick a hard-coded, randomly chosen, non-zero, odd number
+                  // ideally different for each class
+              fHashCode = new HashCodeBuilder(17, 37).
+                                                          append(this.name).
+                                                          toHashCode();
+            }
+            return fHashCode;
+          }  
+  
   /**
    * Returns <code>true</code> if the event is a  

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/OpenElementEventNSImpl.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import javax.xml.parsers.DocumentBuilderFactory;
+
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 
 import com.topologi.diffx.Constants;
@@ -160 +164 @@
     if (name == null)
       throw new NullPointerException("Element must have a name.");
+        // that will happen if you forgot to setNamespaceAware(true) on your DocumentBuilderFactory
     this.uri = uri;
     this.name = name;
@@ -181 +186 @@
    * @see java.lang.Object#hashCode()
    */
-  public int hashCode() {
-    return this.uri.hashCode() + this.name.hashCode();
-  }
-
+//  public int hashCode() {
+//    return this.uri.hashCode() + this.name.hashCode();
+//  }
+
+  private int fHashCode;  
+  @Override public int hashCode() {
+            if ( fHashCode == 0) {
+                  // you pick a hard-coded, randomly chosen, non-zero, odd number
+                  // ideally different for each class
+              fHashCode = new HashCodeBuilder(17, 37).
+                                                          append(this.uri).
+                                                          append(this.name).
+                                                          toHashCode();
+            }
+            return fHashCode;
+          }  
+  
   /**
    * Returns <code>true</code> if the event is a  

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/ProcessingInstructionEvent.java

@@ -106 +106 @@
 import java.io.IOException;
 
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 import com.topologi.diffx.event.DiffXEvent;
 import com.topologi.diffx.xml.XMLWriter;
@@ -162 +164 @@
    * @see java.lang.Object#hashCode()
    */
-  public int hashCode() {
-    return this.target.hashCode() + this.data.hashCode();
-  }
-
+//  public int hashCode() {
+//    return this.target.hashCode() + this.data.hashCode();
+//  }
+
+  private int fHashCode;  
+  @Override public int hashCode() {
+            if ( fHashCode == 0) {
+                  // you pick a hard-coded, randomly chosen, non-zero, odd number
+                  // ideally different for each class
+              fHashCode = new HashCodeBuilder(17, 37).
+                                                          append(this.target).
+                                                          append(this.data).
+                                                          toHashCode();
+            }
+            return fHashCode;
+          }  
+  
   /**
    * Returns <code>true</code> if the event is a  

trunk/docx4j/src/diffx/com/topologi/diffx/event/impl/XMLBranchEvent.java

@@ -2 +2 @@
 
 import java.io.IOException;
+
+import org.apache.commons.lang.builder.HashCodeBuilder;
 
 import com.topologi.diffx.event.DiffXEvent;
@@ -36 +38 @@
   public XMLBranchEvent(DiffXEvent[] events) {
     this.branch = events;
-    int tmpHash = 0;
-    for (int i = 0; i < events.length; i++)
-      tmpHash += events[i].hashCode();
-    this.hashCode = tmpHash;
+//    int tmpHash = 0;
+//    for (int i = 0; i < events.length; i++)
+//      tmpHash += events[i].hashCode();
+//    this.hashCode = tmpHash;
+    hashCode = new HashCodeBuilder(17, 37).
+          append(events).
+          toHashCode();
   }
 

trunk/docx4j/src/diffx/com/topologi/diffx/load/DOMRecorder.java

@@ -126 +126 @@
 import org.xml.sax.InputSource;
 
+import com.topologi.diffx.Docx4jDriver;
 import com.topologi.diffx.config.DiffXConfig;
 import com.topologi.diffx.event.AttributeEvent;
@@ -459 +460 @@
     if ("http://www.w3.org/2000/xmlns/".equals(e.getURI())) {
         
+        //Docx4jDriver.log("Encountered namespace declaration: " + e.getValue() );
+        
         // Trap/handle xmlns:xmlns="",
         // which JAXB seems to produce 
@@ -465 +468 @@
         if (e.getName().equals("xmlns") &&
                         e.getValue().equals("") ) {
-                System.out.println("Ignoring xmlns:xmlns='' ");
+                Docx4jDriver.log("Ignoring xmlns:xmlns='' ");
                 return;
         }

trunk/docx4j/src/diffx/com/topologi/diffx/sequence/EventSequence.java

@@ -104 +104 @@
  */
 
+import java.io.IOException;
 import java.io.PrintWriter;
 import java.util.ArrayList;
@@ -111 +112 @@
 import java.util.NoSuchElementException;
 
+import org.apache.commons.lang.builder.HashCodeBuilder;
+
 import com.topologi.diffx.event.DiffXEvent;
+import com.topologi.diffx.format.DiffXFormatter;
 
 /**
@@ -126 +130 @@
 // Class attributes ---------------------------------------------------------------------------
 
-  /**
+/**
    * The prefix mapping for the elements in this sequence.
    */
@@ -134 +138 @@
    * The sequence of events.
    */
-  private final List sequence;
+  private final List<DiffXEvent> sequence;
 
 // Constructors -------------------------------------------------------------------------------
@@ -142 +146 @@
    */
   public EventSequence() {
-    this.sequence = new LinkedList();
+    this.sequence = new LinkedList<DiffXEvent>();
   }
   
@@ -151 +155 @@
    */
   public EventSequence(int size) {
-    this.sequence = new ArrayList(size);
+    this.sequence = new ArrayList<DiffXEvent>(size);
   }
 
@@ -243 +247 @@
    * @see java.lang.Object#hashCode()
    */
-  public int hashCode() {
-    return this.sequence.size();
-  }
-
-  /**
-   * Returns <code>true</code> if the specified event sequence is the same as this one.
-   * 
-   * @param seq The sequence of events to compare with this one.
-   * 
-   * @return <code>true</code> if the specified event sequence is equal to this one;
-   *         <code>false</code> otherwise. 
-   */
+//  public int hashCode() {
+//    return this.sequence.size();
+//  }
+  
+
+  private int fHashCode;
+
+        public int hashCode() {
+                if (fHashCode == 0) {
+                        HashCodeBuilder builder = new HashCodeBuilder();
+                        for (Iterator i = this.sequence.iterator(); i.hasNext();) {
+                                builder.append(i.next());
+                        }
+                        fHashCode = builder.toHashCode();
+                }
+                return fHashCode;
+        }
+
+  /**
+         * Returns <code>true</code> if the specified event sequence is the same
+         * as this one.
+         * 
+         * @param seq
+         *            The sequence of events to compare with this one.
+         * 
+         * @return <code>true</code> if the specified event sequence is equal to
+         *         this one; <code>false</code> otherwise.
+         */
   public boolean equals(EventSequence seq) {
     if (seq == null) return false;
@@ -313 +333 @@
     w.flush();
   }
-
-  /**
-   * Maps a uri to a prefix.
-   * 
-   * @see PrefixMapping#add(String, String)
-   * 
-   * @param uri    The namespace URI to map. 
-   * @param prefix The prefix to use.
-   * 
-   * @throws NullPointerException if the URI or prefix is <code>null</code>
-   */
+  
+  /**
+   * Send this entire EventSequence to the formatter.
+   * Used by Docx4jDriver
+   * 
+ * @param formatter
+ * @throws NullPointerException
+ * @throws IOException
+ */
+public void format(DiffXFormatter formatter) throws NullPointerException,
+                        IOException {
+                DiffXEvent x = null;
+                for (int i = 0; i < sequence.size(); i++) {
+                        x = (DiffXEvent) sequence.get(i);
+                        formatter.format(x);
+                }
+        }  
+
+  /**
+         * Maps a uri to a prefix.
+         * 
+         * @see PrefixMapping#add(String, String)
+         * 
+         * @param uri
+         *            The namespace URI to map.
+         * @param prefix
+         *            The prefix to use.
+         * 
+         * @throws NullPointerException
+         *             if the URI or prefix is <code>null</code>
+         */
   public void mapPrefix(String uri, String prefix) throws NullPointerException {
     this.prefixMapping.add(uri, prefix);
@@ -336 +376 @@
     return this.prefixMapping;
   }
-
+    
 // Inner class --------------------------------------------------------------------------------
 

trunk/docx4j/src/diffx/com/topologi/diffx/sequence/PrefixMapping.java

@@ -43 +43 @@
   }
 
+  public void add(PrefixMapping others) throws NullPointerException {
+
+                String key;
+                for (Enumeration e = others.mappings.keys(); e.hasMoreElements();) {
+                        key = (String) e.nextElement();
+                        this.mappings.put(key, others.mappings.get(key));
+                }
+        }
+  
   /**
-   * Returns an enumeration of the namespace URIs used in this mapping.
-   * 
-   * @return An enumeration of the namespace URIs used in this mapping.
-   */
+         * Returns an enumeration of the namespace URIs used in this mapping.
+         * 
+         * @return An enumeration of the namespace URIs used in this mapping.
+         */
   public Enumeration getURIs() {
     return this.mappings.keys();

trunk/docx4j/src/diffx/com/topologi/diffx/xml/NSAwareXMLWriter.java

@@ -111 +111 @@
 import java.util.List;
 
+import com.topologi.diffx.Docx4jDriver;
 import com.topologi.diffx.event.AttributeEvent;
 
@@ -594 +595 @@
     String prefix = (String)this.prefixMapping.get((uri != null)? uri : "");
     if (prefix == null) {
-      //throw new UndeclaredNamespaceException(uri);
-        
-        // Horrible temporary nasty hack
-        // TODO
-        //System.out.println("FIX ME - com.topologi.diffx.xml.NSAwareXMLWriter.getQName(NSAwareXMLWriter.java:599)");           
-        return "xml:"+name;     
+        if (uri.equals("http://www.w3.org/XML/1998/namespace")) {
+                // eg xml:space .. 
+                // per the namespace recommendation, this namespace may, but need not, be declared
+                // It is bound by definition to ...
+                return "xml:"+name;                     
+        } else {
+                Docx4jDriver.log("FIX ME - com.topologi.diffx.xml.NSAwareXMLWriter.getQName(null, " + name + ") @599)");        
+                throw new UndeclaredNamespaceException(uri + " for " + name);
+        }
     } else if ("".equals(prefix)) {
         return name;            
@@ -644 +648 @@
 
   /**
-   * Restores the prefix mapping after clsing an element.
+   * Restores the prefix mapping after closing an element.
    * 
    * <p>This costly operation need only to be done if the method
    * {@link NSAwareXMLWriter#setPrefixMapping(String, String)} have been used
-   * immediately before, therefor it should not happen often.
+   * immediately before, therefore it should not happen often.
    * 
    * @param elt The element that had some new mappings.
    */
   private void restorePrefixMapping(Element elt) {
-    if (elt.mappings != null) {
-      // for each mapping of this element
-      for (int i = 0; i < elt.mappings.size(); i++) {
-        PrefixMapping mpi = (PrefixMapping)elt.mappings.get(i);
-        if (DEBUG) System.err.print(mpi.prefix+" -< ");
-        // find the first previous namespace mapping amongst the parents
-        // that defines namespace mappings
-        for (int j = elements.size() - 1; j > 0; j--) {
-          if (((Element)this.elements.get(j)).mappings != null) {
-            List mps = ((Element)elements.get(j)).mappings;
-            // iterate through the define namespace mappings of the parent
-            for (int k = 0; k < mps.size(); k++) {
-              PrefixMapping mpk = (PrefixMapping)mps.get(k);
-              // if we found a namespace prefix for the namespace
-              if (mpk.prefix.equals(mpi.prefix)) {
-                removeIfNeeded(mpk.prefix);
-                this.prefixMapping.put(mpk.uri, mpk.prefix);
-                if (DEBUG) System.err.println(mpk.uri+" [R]");
-                j = 0; // exit from the previous loop
-                break; // exit from this one
-              }
-            }
-          }
-        }
-      }
-    }
-  }
-
-  /**
-   * Removes the mapping associated to the specified prefix.
-   * 
-   * @param prefix The prefix which mapping should be removed. 
-   */
+                if (elt.mappings != null) {
+                        // for each mapping of this element
+                        for (int i = 0; i < elt.mappings.size(); i++) {
+                                PrefixMapping mpi = (PrefixMapping) elt.mappings.get(i);
+                                if (DEBUG)
+                                        System.err.print(mpi.prefix + " -< ");
+                                // find the first previous namespace mapping amongst the parents
+                                // that defines namespace mappings
+                                for (int j = elements.size() - 1; j > 0; j--) {
+                                        if (((Element) this.elements.get(j)).mappings != null) {
+                                                List mps = ((Element) elements.get(j)).mappings;
+                                                // iterate through the define namespace mappings of the
+                                                // parent
+                                                for (int k = 0; k < mps.size(); k++) {
+                                                        PrefixMapping mpk = (PrefixMapping) mps.get(k);
+                                                        // if we found a namespace prefix for the namespace
+                                                        if (mpk.prefix.equals(mpi.prefix)) {
+                                                                removeIfNeeded(mpk.prefix);
+                                                                this.prefixMapping.put(mpk.uri, mpk.prefix);
+                                                                if (DEBUG)
+                                                                        System.err.println(mpk.uri + " [R]");
+                                                                j = 0; // exit from the previous loop
+                                                                break; // exit from this one
+                                                        }
+                                                }
+                                        }
+                                }
+                        }
+                }
+        }
+
+  /**
+         * Removes the mapping associated to the specified prefix.
+         * 
+         * @param prefix
+         *            The prefix which mapping should be removed.
+         */
   private void removeIfNeeded(String prefix) {
     // remove the previous mapping to the prefix
@@ -696 +704 @@
       }
       this.prefixMapping.remove(key); // we know key should have a value
+          if (DEBUG) System.err.println("Removed " + prefix);
+      
     }
   }

trunk/docx4j/src/diffx/org/eclipse/compare/StringComparator.java

@@ -1 +1 @@
 
-package org.docx4j.diff;
+package org.eclipse.compare;
 
 import java.util.ArrayList;

trunk/docx4j/src/main/java/org/docx4j/diff/MarkupDelete.xslt

@@ -44 +44 @@
 <xsl:param name="docPartRelsLeft"/>
 <xsl:param name="docPartRelsRight"/>
+<xsl:param name="relsDiffIdentifier"/>
 
   <xsl:output method="xml" encoding="utf-8" omit-xml-declaration="no" indent="yes" />

trunk/docx4j/src/main/java/org/docx4j/diff/MarkupInsert.xslt

@@ -44 +44 @@
 <xsl:param name="docPartRelsLeft"/>
 <xsl:param name="docPartRelsRight"/>
+<xsl:param name="relsDiffIdentifier"/>
 
 <xsl:preserve-space elements="w:t"/> 
@@ -107 +108 @@
     -->
     
-<xsl:template match="w:drawing" priority="5">
+<xsl:template match="w:drawing" priority="3">
   
         <xsl:choose>
@@ -142 +143 @@
   
   </xsl:template>
-      
-    
+          
     <xsl:template match="a:blip"  priority="5">
     
@@ -325 +325 @@
   
 
+
 </xsl:stylesheet>
 

trunk/docx4j/src/main/java/org/docx4j/diff/ParagraphDifferencer.java

@@ -56 +56 @@
 import org.docx4j.wml.R;
 
+import org.eclipse.compare.StringComparator;
 import org.eclipse.compare.rangedifferencer.RangeDifference;
-import org.docx4j.diff.StringComparator;
 import org.docx4j.jaxb.Context;
 import org.docx4j.openpackaging.parts.relationships.RelationshipsPart;
@@ -67 +67 @@
 import org.xml.sax.InputSource;
 
+import com.topologi.diffx.Docx4jDriver;
 import com.topologi.diffx.Main;
 import com.topologi.diffx.config.DiffXConfig;
@@ -84 +85 @@
         protected static Logger log = Logger.getLogger(ParagraphDifferencer.class);
 
+
         // For XSLT
         public static void log(String message ) {               
@@ -90 +92 @@
         
         
-        public static Integer nextId = 0;
 
         static org.docx4j.wml.ObjectFactory wmlFactory = new org.docx4j.wml.ObjectFactory();
@@ -159 +160 @@
         }
         
-        public final static Integer getId() {
-                
-                return ++nextId;
-                
-        }
-        
+        /**
+         * The id to be allocated to the ins/del
+         * @return
+         */
+        public final static Integer getId() {           
+                return ++nextId;                
+        }
+        public static Integer nextId = 0;
+
+        
+        /**
+         * Because the resulting document might be built out of the 
+         * results of a number of diffs, we need to be sure that the id's
+         * are unique across these diffs.
+         * 
+         * This is passed into the XSLT, where it is used as part
+         * of the generated rel id.
+         * 
+         * @return the 
+         */
+        private String relsDiffIdentifier;  
+        /**
+         * @param relsDiffIdentifier the relsDiffIdentifier to set
+         */
+        public void setRelsDiffIdentifier(String relsDiffIdentifier) {
+                this.relsDiffIdentifier = relsDiffIdentifier;
+        }
+
         /**
          * Any rel which is present in the results of the comparison must point to
@@ -171 +194 @@
          * 
          * So we pass the old and new rels objects, and
-         * progressively build up a composite one.
+         * progressively build up a List of relationships which will need to be
+         * in the resulting document.
+         * 
+         * Because the resulting document might be built out of the 
+         * results of a number of diffs, we need to be sure that the id's
+         * are unique across these diffs.
          * 
          * @return the 
@@ -190 +218 @@
                 }
                 
+                
+                log.error("Looking for rel " + relId);
                 Relationship r = docPartRels.getRelationshipByID(relId);
                 if (r==null) {
@@ -199 +229 @@
                 
                 r2.setId(newRelId);
+                log.error(".. added rel " + newRelId + " -- " + r2.getTarget() );
                 
                 pd.composedRels.add(r2);
@@ -221 +252 @@
         }
 
-        
         public void diff(org.docx4j.wml.SdtContentBlock cbLeft, 
                         org.docx4j.wml.SdtContentBlock cbRight, 
@@ -227 +257 @@
                         String author, java.util.Calendar date,
                         RelationshipsPart docPartRelsLeft, RelationshipsPart docPartRelsRight) {
+                
+                this.diffWorker(cbLeft, cbRight, result, author, date, docPartRelsLeft, docPartRelsRight);
+        }
+
+        public void diff(org.docx4j.wml.Body bodyLeft, 
+                        org.docx4j.wml.Body bodyRight, 
+                        javax.xml.transform.Result result,
+                        String author, java.util.Calendar date,
+                        RelationshipsPart docPartRelsLeft, RelationshipsPart docPartRelsRight) {
+                
+                this.diffWorker(bodyLeft, bodyRight, result, author, date, docPartRelsLeft, docPartRelsRight);
+        }
+        
+        /**
+         * This is private, in order to control what objects the user
+         * can invoke diff on.  At present there are public methods for
+         * pairs of w:body, w:sdtContent, and w:p.  
+         * 
+         * TODO: consider/test w:table! 
+         */
+        private void diffWorker(Object objectLeft, 
+                        Object objectRight, 
+                        javax.xml.transform.Result result,
+                        String author, java.util.Calendar date,
+                        RelationshipsPart docPartRelsLeft, RelationshipsPart docPartRelsRight) {
 
                 Writer diffxResult = new StringWriter();
-                
-                DiffXConfig diffxConfig = new DiffXConfig();
-                diffxConfig.setIgnoreWhiteSpace(false);
-                diffxConfig.setPreserveWhiteSpace(true);
 
                 try {
-                        Main.diff( org.docx4j.XmlUtils.marshaltoW3CDomDocument(cbLeft),
-                                           org.docx4j.XmlUtils.marshaltoW3CDomDocument(cbRight),
-                                           diffxResult, diffxConfig);
+                        Docx4jDriver.diff(org.docx4j.XmlUtils.marshaltoW3CDomDocument(objectLeft),
+                                           org.docx4j.XmlUtils.marshaltoW3CDomDocument(objectRight),
+                                           diffxResult);
                                 // The signature which takes Reader objects appears to be broken
                         diffxResult.close();
@@ -249 +300 @@
                         XMLInputFactory inputFactory = XMLInputFactory.newInstance();
                         //java.io.InputStream is = new java.io.ByteArrayInputStream(naive.getBytes("UTF-8"));
-                        Reader reader = new StringReader(diffxResult.toString());
-                        
-                        String simplified = combineAdjacent(inputFactory.createXMLStreamReader(reader) );
+                        Reader reader;
+//                      if (log.isDebugEnabled() ) {
+//                              String res = diffxResult.toString();
+//                              log.debug(res);
+//                              reader = new StringReader(res);
+//                      } else {
+                                reader = new StringReader(diffxResult.toString());                              
+//                      }
+                        
+                        String simplified = null;
+                                try {
+                                        simplified = combineAdjacent(inputFactory.createXMLStreamReader(reader) );
+                                } catch (XMLStreamException e) {
+                                        e.printStackTrace();
+                                        log.debug("left: " + XmlUtils.marshaltoString(objectLeft, true, false));
+                                        log.debug("right: " + XmlUtils.marshaltoString(objectRight, true, false));                                      
+                                }
                         
                         log.debug("\n\n Diff'd input to transform: \n\n" + simplified );
                                                         
                         StreamSource src = new StreamSource(new StringReader(simplified));
-                        Map<String, Object> transformParameters = new java.util.HashMap<String, Object>();
-                                                
-                        String dateString;
-                        if (date!=null) {                               
-                                dateString = RFC3339_FORMAT.format(date.getTime()) ;
-                        } else {
-                                // TODO FIXME - JAXB requires a real date.
-                                // What to give it?  
-                                // The alternative is to change the xslt
-                                // to omit the @date entirely if its unknown
-                                dateString = "2009-03-11T17:57:00Z";
-                        }
-                        transformParameters.put("ParagraphDifferencer", this);
-                        transformParameters.put("date", dateString);
-                        transformParameters.put("author", author);
-                        transformParameters.put("docPartRelsLeft",  docPartRelsLeft);
-                        transformParameters.put("docPartRelsRight", docPartRelsRight);
-                        
-                        XmlUtils.transform(src, xsltDiffx2Wml, transformParameters, result);
+                        transformDiffxOutputToWml(result, author, date, docPartRelsLeft,
+                                        docPartRelsRight, src);
                         
                 } catch (Exception exc) {
@@ -280 +328 @@
                 }                       
                 
+        }
+
+        /**
+         * @param result
+         * @param author
+         * @param date
+         * @param docPartRelsLeft
+         * @param docPartRelsRight
+         * @param src
+         * @throws Exception
+         */
+        private void transformDiffxOutputToWml(javax.xml.transform.Result result,
+                        String author, java.util.Calendar date,
+                        RelationshipsPart docPartRelsLeft,
+                        RelationshipsPart docPartRelsRight, StreamSource src)
+                        throws Exception {
+                Map<String, Object> transformParameters = new java.util.HashMap<String, Object>();
+                                        
+                String dateString;
+                if (date!=null) {                               
+                        dateString = RFC3339_FORMAT.format(date.getTime()) ;
+                } else {
+                        // TODO FIXME - JAXB requires a real date.
+                        // What to give it?  
+                        // The alternative is to change the xslt
+                        // to omit the @date entirely if its unknown
+                        dateString = "2009-03-11T17:57:00Z";
+                }
+                transformParameters.put("ParagraphDifferencer", this);
+                transformParameters.put("date", dateString);
+                transformParameters.put("author", author);
+                transformParameters.put("docPartRelsLeft",  docPartRelsLeft);
+                transformParameters.put("docPartRelsRight", docPartRelsRight);
+                transformParameters.put("relsDiffIdentifier", relsDiffIdentifier);  
+                
+                XmlUtils.transform(src, xsltDiffx2Wml, transformParameters, result);
         }
         
@@ -310 +394 @@
                         transformParameters.put("docPartRelsLeft",  docPartRelsLeft);
                         transformParameters.put("docPartRelsRight", null);
+                        transformParameters.put("relsDiffIdentifier", relsDiffIdentifier);  
                         XmlUtils.transform(doc, xsltMarkupInsert, transformParameters, result);
                         
@@ -346 +431 @@
                         transformParameters.put("docPartRelsLeft",  null);
                         transformParameters.put("docPartRelsRight", docPartRelsRight);
+                        transformParameters.put("relsDiffIdentifier", relsDiffIdentifier);  
                         XmlUtils.transform(doc, xsltMarkupDelete, transformParameters, result);
                         
@@ -477 +563 @@
                                 transformParameters.put("docPartRelsLeft",  docPartRelsLeft);
                                 transformParameters.put("docPartRelsRight", docPartRelsRight);
+                                transformParameters.put("relsDiffIdentifier", relsDiffIdentifier);  
                                 XmlUtils.transform(src, xsltDiffx2Wml, transformParameters, result);
                                 
@@ -707 +794 @@
                 try {
                         StreamSource src = new StreamSource(new StringReader(diffx));
-                        Map<String, Object> transformParameters = new java.util.HashMap<String, Object>();
-                        transformParameters.put("ParagraphDifferencer", this);
-                        transformParameters.put("author", author);
-                        transformParameters.put("docPartRelsLeft",  docPartRelsLeft);
-                        transformParameters.put("docPartRelsRight", docPartRelsRight);
-                        XmlUtils.transform(src, xsltDiffx2Wml, transformParameters, result);
-                        
+                        transformDiffxOutputToWml(result, author, date, docPartRelsLeft,
+                                        docPartRelsRight, src);                 
                 } catch (Exception exc) {
                         exc.printStackTrace();

trunk/docx4j/src/main/java/org/docx4j/diff/diffx2wml.xslt

@@ -573 +573 @@
   </xsl:template>
 
-  <xsl:template match="text()">
+  <xsl:template match="text()[not(ancestor::wp:*)]">
   
       <w:r>