|
1
19
20 package org.netbeans.modules.xml.xdm.diff;
21
22 import java.util.ArrayList  ;
23 import java.util.Collections ;
24 import java.util.HashMap ;
25 import java.util.Iterator ;
26 import java.util.List ;
27 import java.util.Map ;
28 import org.netbeans.modules.xml.spi.dom.NodeListImpl;
29 import org.netbeans.modules.xml.xam.dom.ElementIdentity;
30 import org.netbeans.modules.xml.xdm.nodes.Document;
31 import org.netbeans.modules.xml.xdm.nodes.Element;
32 import org.netbeans.modules.xml.xdm.nodes.Node;
33 import org.netbeans.modules.xml.xdm.nodes.NodeImpl;
34 import org.netbeans.modules.xml.xdm.nodes.Text;
35 import org.netbeans.modules.xml.xdm.nodes.Token;
36 import org.netbeans.modules.xml.xdm.visitor.PathFromRootVisitor;
37 import org.netbeans.modules.xml.xdm.nodes.Attribute;
38 import org.w3c.dom.DOMException ;
39 import org.w3c.dom.NamedNodeMap ;
40 import org.w3c.dom.NodeList ;
41
42
48 public class DiffFinder {
49 protected DiffFinder() {
50 }
51
52 public DiffFinder(ElementIdentity eID) {
53 this.eID = eID;
54 }
55
56
62 public List <Difference> findDiff(Document d1, Document d2) {
63 this.oldDoc = d1;
64 this.newDoc = d2;
65
66 List <Difference> deList = new ArrayList <Difference>();
67 List <Change.Type> changes = checkChange( d1, d2, 0, 0);
68 if (changes.size() > 0) {
69 markChange( new ArrayList <Node>(), d1, d2, 0, 0, changes,
70 new ArrayList <Node>(), deList );
71 }
72
73 List <Node> ancestors1 = new ArrayList <Node>();
74 List <Node> ancestors2 = new ArrayList <Node>();
75 ancestors1.add(oldDoc);
76 ancestors2.add(newDoc);
77 compareChildren(ancestors1, ancestors2, deList);
78
79 if( deList.size() > 0 ) {
81 deList = findOptimized(deList);
82 }
83
84 return deList;
85 }
86
87 protected void compareChildren(List <Node> ancestors1,
88 List <Node> ancestors2, List <Difference> deList) {
89 Node parent1 = ancestors1.get(0);
90 Node parent2 = ancestors2.get(0);
91 NodeList p1ChildNodes = parent1.getChildNodes();
92 NodeList p2ChildNodes = parent2.getChildNodes();
93
94 if ( p1ChildNodes == NodeListImpl.EMPTY &&
95 p2ChildNodes == NodeListImpl.EMPTY )
96 return;
97
98 cInfo1 = new ChildInfo(parent1);
99 cInfo2 = new ChildInfo(parent2);
100 List <Node> p2ChildList = getChildList(parent2);
101
102 List <int[]> pairList = new ArrayList <int[]>();
103 List <Node> foundList = new ArrayList <Node>();
104 if ( p1ChildNodes != null ) {
105 int length = p1ChildNodes.getLength();
106 for ( int i = 0; i < length; i++ ) {
107 Node child = (Node) p1ChildNodes.item(i);
108 Node foundNode = null;
109 if ( child instanceof Element ) {
110 foundNode = findMatch( (Element)child, p2ChildList, parent1);
111 } else if ( child instanceof Text ) {
112 foundNode = findMatch( (Text)child, p2ChildList);
113 }
114 if( foundNode == null ) {
115 List <Node> path1 = copy(ancestors1);
116 List <Node> path2 = copy(ancestors2);
117 markDelete(path1, child, i, cInfo1.getSiblingBefore( child ),
118 path2, deList );
119 } else {
120 cInfo2.addMatchNode( foundNode, child);
121 foundList.add( foundNode );
122 p2ChildList.remove( foundNode );
123 int[] pair = new int[] {i,cInfo2.getIndex(foundNode)};
124 pairList.add( pair );
125 }
126 }
127
128 for ( int i = 0; i < p2ChildList.size() ; i++ ) {
129 Node child = (Node) p2ChildList.get(i);
130 SiblingInfo sInfo = new SiblingInfo(child, p2ChildNodes, foundList);
131 Node originalSiblingBefore = null;
132 if (sInfo.getNode() != null) {
133 originalSiblingBefore = cInfo2.getMatchNode(sInfo.getNode());
134 }
135
136 int absolutePos = cInfo2.getIndex( child );
137 markAdd( copy(ancestors1), child, absolutePos, sInfo.getPosition(),
138 originalSiblingBefore, copy(ancestors2), deList );
139 }
140
141 Collections.sort(pairList, new PairComparator());
143
144 for ( int i=0; i < pairList.size(); i++ ) {
145 int[] pair = pairList.get(i);
146 int px1 = pair[0];
147 int px2 = pair[1];
148 Node p1 = (Node) parent1.getChildNodes().item(px1);
149 Node p2 = (Node) parent2.getChildNodes().item(px2);
150
151 int tp1 = cInfo1.getPosition(p1);
152 int tp2 = cInfo2.getPosition(p2);
153
154 List <Change.Type> changes = checkChange( p1, p2, tp1, tp2);
156 if (changes.size() > 0) {
157 markChange( copy(ancestors1), p1, p2, px1, px2, changes,
158 copy(ancestors2), deList );
159 }
160 }
161 cInfo1 = null;
163 cInfo2 = null;
164
165 for ( int i=0; i < pairList.size(); i++ ) {
166 int[] pair = pairList.get(i);
167 int px1 = pair[0];
168 int px2 = pair[1];
169 Node p1 = (Node) parent1.getChildNodes().item(px1);
170 Node p2 = (Node) parent2.getChildNodes().item(px2);
171 if ( p1 instanceof Element ) {
172 ancestors1.add(0, p1);
173 ancestors2.add(0, p2);
174 compareChildren( ancestors1, ancestors2, deList );
176 ancestors1.remove(0);
177 ancestors2.remove(0);
178 }
179 }
180 }
181 }
182
183 private List <Node> copy(List <Node> l) {
184 return new ArrayList <Node>(l);
185 }
186
187 public class PairComparator implements java.util.Comparator {
188 public int compare(Object o1, Object o2) {
189 int[] pair1 = (int[]) o1;
190 int[] pair2 = (int[]) o2;
191 int px2_1 = pair1[1];
192 int px2_2 = pair2[1];
193 if(px2_1 < px2_2)
194 return -1;
195 else if(px2_1 > px2_2)
196 return +1;
197 else
198 return 0;
199 }
200 }
201
202 public static NodeInfo.NodeType getNodeType(final Node child)
203 throws DOMException {
204 NodeInfo.NodeType nodeType = NodeInfo.NodeType.ELEMENT;
205 if ( child instanceof Text )
206 if ( isWhiteSpaceOnly((Text) child) )
207 nodeType = NodeInfo.NodeType.WHITE_SPACE;
208 else
209 nodeType = NodeInfo.NodeType.TEXT;
210 else if ( child instanceof Attribute )
211 nodeType = NodeInfo.NodeType.ATTRIBUTE;
212 return nodeType;
213 }
214
215 protected List <Change.Type> checkChange(final Node n1, final Node n2,
216 final int p1, final int p2) {
217 List <Change.Type> changes = checkChange(n1, n2);
218 if(p1 != p2)
219 changes.add(Change.Type.POSITION);
220 return changes;
221 }
222
223 protected List <Change.Type> checkChange(final Node p1, final Node p2) {
224 List <Change.Type> changes = new ArrayList <Change.Type>();
225 if ( ! checkTokensEqual(p1, p2)) {
226 changes.add(Change.Type.TOKEN);
227 }
228 if (p1 instanceof Element && p2 instanceof Element) {
229 if ( ! checkAttributesEqual((Element)p1, (Element)p2)) {
230 changes.add(Change.Type.ATTRIBUTE);
231 }
232 } else if (! p1.getClass().isAssignableFrom(p2.getClass()) ||
233 ! p2.getClass().isAssignableFrom(p1.getClass())) {
234 changes.add(Change.Type.UNKNOWN);
235 }
236 return changes;
237 }
238
239 protected boolean checkTokensEqual(final Node p1, final Node p2) {
240 if (p1 instanceof NodeImpl && p2 instanceof NodeImpl) {
241 List <Token> t1List = ((NodeImpl)p1).getTokens();
242 List <Token> t2List = ((NodeImpl)p2).getTokens();
243 return compareTokenEquals( t1List, t2List );
244 }
245 return false;
246 }
247
248 protected boolean checkAttributesEqual(final Element p1, final Element p2) {
249 if (p1 == null || p2 == null) return false;
250 NamedNodeMap nm1 = p1.getAttributes();
251 NamedNodeMap nm2 = p2.getAttributes();
252 if( nm1.getLength() != nm2.getLength() ) return false;
253
254 for ( int i = 0; i < nm1.getLength(); i++ ) {
255 Node attr2 = (Node) nm2.getNamedItem(nm1.item(i).getNodeName());
256 if ( attr2 == null ) return false;
257 if(nm2.item(i) != attr2) return false;
258 List <Token> t1List = ((NodeImpl)nm1.item(i)).getTokens();
259 List <Token> t2List = ( (NodeImpl) attr2 ).getTokens();
260 boolean status = compareTokenEquals( t1List, t2List );
261 if ( !status ) return false;
262 }
263 return true;
264 }
265
266 protected boolean compareTokenEquals(List <Token> t1List,
267 List <Token> t2List) {
268 if( t1List.size() != t2List.size() )
269 return false;
270
271 for ( int i=0; i<t1List.size(); i++ ) {
273 Token t1 = t1List.get( i );
274 Token t2 = t2List.get( i );
275 if ( t1.getValue().intern() != t2.getValue().intern() )
276 return false;
277 }
278
279 return true;
280 }
281
282 protected Node findMatch(Element child, List <Node> childNodes,
283 org.w3c.dom.Node parent1) {
284 for (Node otherChild : childNodes ) {
285 if ( otherChild instanceof Element ) {
286 if ( ((DefaultElementIdentity)eID).compareElement(
287 child, (Element) otherChild , parent1, this.oldDoc, this.newDoc) )
288 return otherChild;
289 }
290 }
291 return null;
292 }
293
294 protected Node findMatch(Text child, List <Node> childNodes) {
295 for (Node otherChild:childNodes) {
296 if ( otherChild instanceof Text &&
297 compareText( child, (Text) otherChild ) )
298 return otherChild;
299 }
300 return null;
301 }
302
303 protected Difference createAddEvent(List <Node> ancestors1, Node n,
304 int absolutePos,
305 List <Node> ancestors2) {
306 assert n != null : "add node null";
307 return new Add( getNodeType( n ), ancestors1, ancestors2, n, absolutePos);
308 }
309
310 protected Difference createDeleteEvent(List <Node> ancestors1, Node n, int pos,
311 List <Node> ancestors2) {
312 assert n != null : "delete node null";
313 return new Delete( getNodeType( n ), ancestors1, ancestors2, n, pos) ;
314 }
315
316 protected Difference createChangeEvent(List <Node> ancestors1, Node n1, Node n2,
317 int n1Pos, int n2Pos, List <Change.Type> changes, List <Node> ancestors2) {
318 assert n1 != null && n2 != null : "change nodes null";
319 if(n1 instanceof Element)
320 assert n1.getLocalName().equals(n2.getLocalName());
321 Change de = new Change(getNodeType(n1), ancestors1, ancestors2, n1,
322 n2, n1Pos, n2Pos, changes);
323
324 if (de.getNewNodeInfo().getNewAncestors().size() > 0) {
325 assert de.getNewNodeInfo().getNode().getId() !=
326 de.getNewNodeInfo().getNewAncestors().get(0).getId();
327 }
328
329 return de;
330 }
331
332 protected void markAdd(List <Node> ancestors1, Node n, int absolutePos,
333 int posFromSibling,
334 Node siblingBefore, List <Node> ancestors2, List <Difference> deList) {
335 deList.add( createAddEvent( ancestors1, n, absolutePos, ancestors2 ) );
336 }
337
338 protected void markDelete(List <Node> ancestors1, Node n, int pos, Node siblingBefore,
339 List <Node> ancestors2, List <Difference> deList) {
340 deList.add( createDeleteEvent( ancestors1, n, pos, ancestors2 ));
341 }
342
343 protected void markChange(List <Node> ancestors1, Node n1, Node n2, int n1Pos, int n2Pos,
344 List <Change.Type> changes, List <Node> ancestors2, List <Difference> deList) {
345 deList.add( createChangeEvent( ancestors1, n1, n2, n1Pos, n2Pos, changes, ancestors2 ) );
346 }
347
348 public static List <Difference> filterWhitespace(List <Difference> deList) {
349 List <Difference> returnList = new ArrayList <Difference>();
350 for ( Difference de:deList ) {
351 NodeInfo.NodeType nodeType = de.getNodeType();
352 if ( de.getNodeType() != NodeInfo.NodeType.WHITE_SPACE )
353 returnList.add(de);
354 }
355 return returnList;
356 }
357
358 public static List <Node> getPathToRoot(Node node) {
359 assert node.getOwnerDocument() != null;
360 List <Node> pathToRoot = new PathFromRootVisitor().findPath(
361 node.getOwnerDocument(), node);
362 return pathToRoot;
364 }
365
366 public List <Difference> findOptimized(List <Difference> deList) {
367 if(deList == null || deList.isEmpty()) return Collections.emptyList();
368 List <Difference> optimizedList = new ArrayList <Difference>();
369 HashMap <Node, List <Difference>> deMap = new HashMap <Node, List <Difference>>();
370 List <Node> parentList = new ArrayList <Node>();
371 for ( Difference de: deList ) {
372 Node parent = de.getOldNodeInfo().getParent();
373 List <Difference> childDeList = deMap.get(parent);
374 if ( childDeList == null ) {
375 parentList.add(parent);
376 childDeList = new ArrayList <Difference>();
377 deMap.put( parent, childDeList );
378 }
379 childDeList.add( de );
380 }
381
382 for (Node parent:parentList) {
383 List <Difference> childDeList = deMap.get(parent);
384 Collections.sort(childDeList, new PairComparator2());
385 HashMap <Difference, Integer > oldPosMap = new HashMap <Difference, Integer >();
386 for ( int i=0; i < childDeList.size(); i++ ) {
387 Difference de = childDeList.get(i);
388 modifyPositionFromIndex( i+1, childDeList, de , oldPosMap);
389 }
390
391 for ( int i=0; i < childDeList.size(); i++ ) {
393 Difference de = childDeList.get(i);
394 Integer oldPos = oldPosMap.get(de);
395 int px1 = oldPos!=null?oldPos.intValue():
396 de.getOldNodeInfo().getPosition();
397 int px2 = de.getNewNodeInfo().getPosition();
398 if(de instanceof Change &&
399 ((Change)de).isPositionChanged()) {
400 if(px1 == px2 && px1 != -1)
401 ((Change)de).setPositionChanged(false); if(((Change)de).isValid())
403 optimizedList.add(de);
404 } else
405 optimizedList.add(de);
406 }
407 }
408 return optimizedList;
409 }
410
411 public class PairComparator2 implements java.util.Comparator {
412 public int compare(Object o1, Object o2) {
413 Difference de1 = (Difference) o1;
414 Difference de2 = (Difference) o2;
415 int px2_1 = de1.getNewNodeInfo().getPosition();
416 int px2_2 = de2.getNewNodeInfo().getPosition();
417 if(px2_1 < px2_2)
418 return -1;
419 else if(px2_1 > px2_2)
420 return +1;
421 else
422 return 0;
423 }
424 }
425
426 protected void modifyPositionFromIndex(int index,
427 List <Difference> childDeList, Difference de,
428 HashMap <Difference, Integer > oldPosMap) {
429 Integer oldx = oldPosMap.get(de);
431 int x = oldx!=null?oldx.intValue():
432 de.getOldNodeInfo().getPosition();
433 int y = de.getNewNodeInfo().getPosition();
434 for ( int i=index; i < childDeList.size(); i++ ) {
435 Difference cde = childDeList.get(i);
436 Integer oldp1 = oldPosMap.get(cde);
437 int p1 = oldp1!=null?oldp1.intValue():
438 cde.getOldNodeInfo().getPosition();
439 int p2 = cde.getNewNodeInfo().getPosition();
440
441 if( de instanceof Add &&
442 x==-1 && y>=0 && y<=p1) {
443 oldPosMap.put(cde, p1+1);
444 } else if( de instanceof Delete &&
445 x>=0 && y==-1 && x<=p1) {
446 oldPosMap.put(cde, p1-1);
447 } else if( de instanceof Change && x!=y) {
448 if(x>p1 && y<=p1)
449 oldPosMap.put(cde, p1+1);
450 else if(y>p1 && x<=p1)
451 oldPosMap.put(cde, p1-1);
452 }
453 }
454 }
455
456 public static boolean isPossibleWhiteSpace(String text) {
457 return text.length() > 0 &&
458 Character.isWhitespace(text.charAt(0)) &&
459 Character.isWhitespace(text.charAt(text.length()-1));
460 }
461
462 public static boolean isWhiteSpaceOnly(Text txt) {
463 String tn = "";
464 if(((NodeImpl)txt).getTokens().size() == 1)
465 tn = ((NodeImpl)txt).getTokens().get(0).getValue();
466 else
467 tn = txt.getNodeValue();
468 return isPossibleWhiteSpace(tn) &&
469 tn.trim().length() == 0;
470 }
471
472 protected boolean compareText(Text n1, Text n2) {
473 if( isWhiteSpaceOnly(n1) && isWhiteSpaceOnly(n2))
474 return compareWhiteSpaces( n1, n2 );
475 else
476 return compareTextByValue( n1, n2 );
477 }
478
479 protected boolean compareWhiteSpaces(Text n1, Text n2) {
480 Node nodeBefore1 = cInfo1.getSiblingBefore( n1 );
481 Node nodeBefore2 = cInfo2.getSiblingBefore( n2 );
482 boolean siblingCompare = false;
483 if( nodeBefore1 == null && nodeBefore2 == null )
484 siblingCompare = true;
485 else if ( nodeBefore1 instanceof Element &&
486 nodeBefore2 instanceof Element ) {
487 if( cInfo2.getMatchNode(nodeBefore2) == nodeBefore1 ||
488 eID.compareElement( (Element) nodeBefore1,
489 (Element) nodeBefore2, this.oldDoc, this.newDoc ) )
490 siblingCompare = true;
491 } else if ( nodeBefore1 instanceof Text && nodeBefore2 instanceof Text &&
492 nodeBefore1.getNodeValue().intern() ==
493 nodeBefore2.getNodeValue().intern() )
494 siblingCompare = true;
495
496 if ( siblingCompare )
497 return compareTextByValue( n1, n2 );
498
499 return false;
500 }
501
502 protected boolean compareTextByValue(Text n1, Text n2) {
503 return n1.getNodeValue().intern() == n2.getNodeValue().intern();
504 }
505
506 protected List <Node> getChildList(Node parent) {
507 NodeList childs = parent.getChildNodes();
508 List <Node> childList = new ArrayList <Node>(childs.getLength());
509 for ( int i = 0; i < childs.getLength() ; i++ ) {
510 Node child = (Node) childs.item(i);
511 childList.add( child );
512 }
513 return childList;
514 }
515
516 static class ChildInfo {
517
518 public ChildInfo(Node parent) {
519 NodeList childNodes = parent.getChildNodes();
520 compareNodeMap = new HashMap <Node, Node>();
521 siblingBeforeMap = new HashMap <Node, Node>(childNodes.getLength());
522 posMap = new HashMap <Node, int[]>(childNodes.getLength());
523 HashMap <Class , Integer > posCounter = new HashMap <Class , Integer >(7);
524 Node siblingBefore = null;
525 for ( int i = 0; i < childNodes.getLength() ; i++ ) {
526 Node child = (Node) childNodes.item(i);
527 siblingBeforeMap.put( child, siblingBefore );
528 siblingBefore = child;
529 Class bucket = getBucket(child);
536 Integer count = posCounter.get(bucket);
537 if(count == null)
538 posCounter.put(bucket, -1);
539 int newCount = posCounter.get(bucket) + 1;
540 posCounter.put(bucket, newCount);
541 int[] pos = new int[] {i,newCount};
542 posMap.put( child, pos );
543 }
544 }
545
546
549 private Class getBucket(Node child) {
550 return child instanceof Text ? Text.class:child.getClass();
551 }
552
553 public Node getSiblingBefore(Node n) {
554 return siblingBeforeMap.get(n);
555 }
556
557 public int getIndex(Node n) {
558 return posMap.get(n)[0];
559 }
560
561 public int getPosition(Node n) {
562 return posMap.get(n)[1];
563 }
564
565 public Node getMatchNode(Node n) {
566 return compareNodeMap.get(n);
567 }
568
569 public void addMatchNode(Node n1, Node n2) {
570 compareNodeMap.put(n1, n2);
571 }
572
573 public void clear() {
574 compareNodeMap.clear();
575 siblingBeforeMap.clear();
576 posMap.clear();
577 }
578
579 HashMap <Node, int[]> posMap;
580 HashMap <Node, Node> siblingBeforeMap;
581 HashMap <Node, Node> compareNodeMap;
582 }
583
584 static class SiblingInfo {
585
586 public SiblingInfo(Node child, NodeList p2ChildNodes, List <Node> foundList) {
587 for ( int j=0; j < p2ChildNodes.getLength(); j++ ) {
588 Node node = (Node) p2ChildNodes.item(j);
589 if ( node == child ) {
590 if ( j-1 >= 0 ) {
591 for ( int k=j-1; k >= 0 ; k-- ) { if ( p2ChildNodes.item( k ) instanceof Element &&
594 foundList.contains( p2ChildNodes.item( k ) ) ) {
595 siblingBefore = (Node) p2ChildNodes.item( k ) ;
596 relativePos = j-k;
597 break;
598 }
599 }
600 }
601 if ( siblingBefore != null )
602 break;
603 }
604 }
605 }
606
607 public Node getNode() {
608 return siblingBefore;
609 }
610
611 public int getPosition() {
612 return relativePos;
613 }
614
615 Node siblingBefore;
616 int relativePos = 0;
617 }
618
619
623 private ElementIdentity eID;
624
625 private ChildInfo cInfo1;
626
627 private ChildInfo cInfo2;
628
629 private Document oldDoc;
630
631 private Document newDoc;
632 }
633 |
Popular Tags |
Java API By Example, From Geeks To Geeks.