开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Internet/网络编程 > xml/soap/webservice > 查看源码
DiffgramGenerator.cs
资源名称：xmlnotepad.rar　[点击查看]
上传用户：hbhltzc
上传日期：2022-06-04
资源大小：1925k
文件大小：65k
源码类别：

xml/soap/webservice

开发平台：

Visual C++

DiffgramGenerator.cs：源码内容
  1. //------------------------------------------------------------------------------
  2. // <copyright file="DiffgramGenerator.cs" company="Microsoft">
  3. //     Copyright (c) Microsoft Corporation.  All rights reserved.
  4. // </copyright>                                                                
  5. //------------------------------------------------------------------------------
  7. using System;
  8. using System.Xml;
  9. using System.Diagnostics;
  10. using System.Collections;
  12. namespace Microsoft.XmlDiffPatch
  13. {
  15. //////////////////////////////////////////////////////////////////
  16. // DiffgramGenerator
  17. //
  18. internal class DiffgramGenerator
  19. {
  20.     //////////////////////////////////////////////////////////////////
  21.     // DiffgramGenerator.SubstituteEditScript
  22.     //
  23.     internal struct PostponedEditScriptInfo
  24.     {
  25.         internal EditScriptPostponed _firstES;
  26.         internal EditScriptPostponed _lastES;
  27.         internal int _startSourceIndex;
  28.         internal int _endSourceIndex;
  30.         internal void Reset()
  31.         {
  32.             _firstES = null;
  33.             _lastES = null;
  34.             _startSourceIndex = 0;
  35.             _endSourceIndex = 0;
  36.         }
  37.     }
  39.     internal class PrefixChange
  40.     {
  41.         internal string _oldPrefix;
  42.         internal string _newPrefix;
  43.         internal string _NS;
  44.         internal ulong _opid;
  45.         internal PrefixChange _next;
  47.         internal PrefixChange( string oldPrefix, string newPrefix, string ns, ulong opid, 
  48.                              PrefixChange next )
  49.         {
  50.             _oldPrefix = oldPrefix;
  51.             _newPrefix = newPrefix;
  52.             _NS = ns;
  53.             _opid = opid;
  54.             _next = next;
  55.         }
  56.     }
  58.     internal class NamespaceChange
  59.     {
  60.         internal string _prefix;
  61.         internal string _oldNS;
  62.         internal string _newNS;
  63.         internal ulong _opid;
  64.         internal NamespaceChange _next;
  66.         internal NamespaceChange( string prefix, string oldNamespace, string newNamespace, 
  67.                                 ulong opid, NamespaceChange next )
  68.         {
  69.             _prefix = prefix;
  70.             _oldNS = oldNamespace;
  71.             _newNS = newNamespace;
  72.             _opid = opid;
  73.             _next = next;
  74.         }
  75.     }
  77. // Fields for both generation methods
  78.     XmlDiff _xmlDiff;
  80.     // cached !XmlDiff.IgnoreChildOrder
  81.     bool _bChildOrderSignificant;
  83.     // Descriptors & operation IDs
  84.     ulong _lastOperationID;
  86.     // 'move' descriptors
  87.     internal const int MoveHashtableInitialSize = 8;
  88.     internal Hashtable _moveDescriptors = new Hashtable( MoveHashtableInitialSize );
  90.     // 'prefix' descriptors
  91.     PrefixChange _prefixChangeDescr = null;
  92.     // 'namespace' descriptors
  93.     NamespaceChange _namespaceChangeDescr = null;
  95. // Fields for generation from edit script:
  96.     // processed edit script
  97.     EditScript _editScript;
  98.     
  99.     // nodes in the post-order numbering - cached from XmlDiff 
  100.     XmlDiffNode[] _sourceNodes;
  101.     XmlDiffNode[] _targetNodes;
  103.     // current processed nodes
  104.     int _curSourceIndex;
  105.     int _curTargetIndex;
  107.     // substitute edit script 
  108.     PostponedEditScriptInfo _postponedEditScript;
  109.     bool _bBuildingAddTree = false;
  111.     // cached DiffgramPosition object
  112.     DiffgramPosition _cachedDiffgramPosition = new DiffgramPosition( null );
  114. // Fields for generation from walktree
  115.     private const int LogMultiplier = 4;
  117. // Constructor
  118. internal DiffgramGenerator( XmlDiff xmlDiff ) 
  119.     {
  120.         Debug.Assert( xmlDiff != null );
  122.         _xmlDiff = xmlDiff;
  123.         _bChildOrderSignificant = !xmlDiff.IgnoreChildOrder;
  125.         _lastOperationID = 0;
  126.     }
  128. // Methods
  129.     internal Diffgram GenerateFromEditScript( EditScript editScript )
  130.     {
  131.         Debug.Assert( editScript != null );
  133.         Debug.Assert( _xmlDiff._sourceNodes != null );
  134.         Debug.Assert( _xmlDiff._targetNodes != null );
  135.         _sourceNodes = _xmlDiff._sourceNodes;
  136.         _targetNodes = _xmlDiff._targetNodes;
  138.         Diffgram diffgram = new Diffgram( _xmlDiff );
  140.         // root nodes always match; remove them from the edit script
  141.         EditScriptMatch esm = editScript as EditScriptMatch;
  142.         if ( editScript.Operation == EditScriptOperation.Match  && 
  143.              ( esm._firstSourceIndex + esm._length == _sourceNodes.Length  &&
  144.                esm._firstTargetIndex + esm._length == _targetNodes.Length ) )
  145.         {
  146.             esm._length--;
  147.             if ( esm._length == 0 )
  148.                 editScript = esm._nextEditScript;
  149.         }
  150.         else
  151.             Debug.Assert( false, "The root nodes does not match!" );
  153.         // init globals
  154.         _curSourceIndex = _sourceNodes.Length - 2;
  155.         _curTargetIndex = _targetNodes.Length - 2;
  156.         _editScript = editScript;
  158.         // generate diffgram
  159.         GenerateDiffgramMatch( diffgram, 1, 1 );
  161.         // add descriptors
  162.         AppendDescriptors( diffgram );
  164.         return diffgram;
  165.     }
  167.     private void AppendDescriptors( Diffgram diffgram ) {
  168.         IDictionaryEnumerator en = _moveDescriptors.GetEnumerator();
  169.         while ( en.MoveNext() )
  170.             diffgram.AddDescriptor( new OperationDescrMove( (ulong)en.Value ) );
  171.         NamespaceChange nsChange = _namespaceChangeDescr;
  172.         while ( nsChange != null )
  173.         {
  174.             diffgram.AddDescriptor( new OperationDescrNamespaceChange( nsChange ) );
  175.             nsChange = nsChange._next;
  176.         }
  178.         PrefixChange prefixChange = _prefixChangeDescr;
  179.         while ( prefixChange != null )
  180.         {
  181.             diffgram.AddDescriptor( new OperationDescrPrefixChange( prefixChange ) );
  182.             prefixChange = prefixChange._next;
  183.         }
  184.     }
  186.     private void GenerateDiffgramMatch( DiffgramParentOperation parent, int sourceBorderIndex, int targetBorderIndex )
  187.     {
  188.         bool bNeedPosition = false;
  190.         while ( _curSourceIndex >= sourceBorderIndex  ||
  191.                 _curTargetIndex >= targetBorderIndex )
  192.         {
  193.             Debug.Assert( _editScript != null );
  195.             switch ( _editScript.Operation )
  196.             {
  197.                 case EditScriptOperation.Match:
  198.                     OnMatch( parent, bNeedPosition );
  199.                     bNeedPosition = false;
  200.                     break;
  201.                 case EditScriptOperation.Add:
  202.                     bNeedPosition = OnAdd( parent, sourceBorderIndex, targetBorderIndex );
  203.                     break;
  204.                 case EditScriptOperation.Remove:
  205.                     if ( _curSourceIndex < sourceBorderIndex )
  206.                         return;
  207.                     OnRemove( parent );
  208.                     break;
  209.                 case EditScriptOperation.ChangeNode:
  210.                     if ( _curSourceIndex < sourceBorderIndex )
  211.                         return;
  212.                     OnChange( parent );
  213.                     break;
  214.                 case EditScriptOperation.EditScriptPostponed:
  215.                     if ( _curSourceIndex < sourceBorderIndex )
  216.                         return;
  217.                     OnEditScriptPostponed( parent, targetBorderIndex );
  218.                     break;
  219.                 default:
  220.                     Debug.Assert( false, "Invalid edit script operation type in final edit script." );
  221.                     break;
  222.             }
  223.         }
  224.     }
  226.     private void GenerateDiffgramAdd( DiffgramParentOperation parent, int sourceBorderIndex, int targetBorderIndex )
  227.     {
  228.         while ( _curTargetIndex >= targetBorderIndex )
  229.         {
  230.             Debug.Assert( _editScript != null );
  232.             switch ( _editScript.Operation )
  233.             {
  234.                 case EditScriptOperation.Match:
  235.                     OnMatch( parent, false );
  236.                     break;
  237.                 case EditScriptOperation.Add:
  238.                     OnAdd( parent, sourceBorderIndex, targetBorderIndex );
  239.                     break;
  240.                 case EditScriptOperation.Remove:
  241.                     OnRemove( parent );
  242.                     break;
  243.                 case EditScriptOperation.ChangeNode:
  244.                     OnChange( parent );
  245.                     break;
  246.                 case EditScriptOperation.EditScriptPostponed:
  247.                     OnEditScriptPostponed( parent, targetBorderIndex );
  248.                     break;
  249.                 default:
  250.                     Debug.Assert( false, "Invalid edit script operation type in final edit script." );
  251.                     break;
  252.             }
  253.         }
  254.     }
  256.     private void GenerateDiffgramPostponed( DiffgramParentOperation parent, ref EditScript editScript, int sourceBorderIndex, int targetBorderIndex )
  257.     {
  258.         while ( _curSourceIndex >= sourceBorderIndex  &&  editScript != null )
  259.         {
  260.             EditScriptPostponed esp = editScript as EditScriptPostponed;
  261.             if ( esp == null ) {
  262.                 GenerateDiffgramMatch( parent, sourceBorderIndex, targetBorderIndex );
  263.                 return;
  264.             }
  265.                 
  266.             Debug.Assert( esp._endSourceIndex == _curSourceIndex );
  267.             
  268.             int sourceStartIndex = esp._startSourceIndex;
  269.             int sourceLeft = _sourceNodes[ esp._endSourceIndex ].Left;
  270.             DiffgramOperation diffOp = esp._diffOperation;
  272.             // adjust current source index
  273.             _curSourceIndex = esp._startSourceIndex - 1;
  274.            
  275.             // move to next edit script
  276.             editScript = esp._nextEditScript;
  278.             // not a subtree or leaf node operation -> process child operations
  279.             if ( sourceStartIndex > sourceLeft ) {
  280.                 GenerateDiffgramPostponed( (DiffgramParentOperation) diffOp, ref editScript, sourceLeft, targetBorderIndex );
  281.             }
  283.             // insert operation
  284.             parent.InsertAtBeginning( diffOp );
  285.         }
  286.     }
  288.     private void OnMatch( DiffgramParentOperation parent, bool bNeedPosition )
  289.     {
  290.         EditScriptMatch matchOp = _editScript as EditScriptMatch;
  292.         Debug.Assert( _curSourceIndex == matchOp._firstSourceIndex + matchOp._length - 1 );
  293.         Debug.Assert( _curTargetIndex == matchOp._firstTargetIndex + matchOp._length - 1 );
  295.         // cache
  296.         int endTargetIndex = matchOp._firstTargetIndex + matchOp._length - 1;
  297.         int endSourceIndex = matchOp._firstSourceIndex + matchOp._length - 1;
  298.         XmlDiffNode targetRoot = _targetNodes[ endTargetIndex ];
  299.         XmlDiffNode sourceRoot = _sourceNodes[ endSourceIndex ];
  301.         // a subtree or leaf node matches
  302.         if ( matchOp._firstTargetIndex <= targetRoot.Left  &&
  303.              matchOp._firstSourceIndex <= sourceRoot.Left )
  304.         {
  305.             if ( _bBuildingAddTree )
  306.             {
  307.                 Debug.Assert( !bNeedPosition );
  309.                 ulong opid = GenerateOperationID( XmlDiffDescriptorType.Move );
  311.                 // output <add match=" "> to diffgram and "remove" to substitute script
  312.                 parent.InsertAtBeginning( new DiffgramCopy( sourceRoot, true, opid ) );
  314.                 // add 'remove' operation to postponed operations
  315.                 PostponedRemoveSubtrees( sourceRoot, opid, 
  316.                 //AddToPosponedOperations( new DiffgramRemoveSubtrees( sourceRoot, opid ), 
  317.                                         sourceRoot.Left, 
  318.                                         endSourceIndex );
  319.             }
  320.             else
  321.             {
  322.                 // matched element -> check attributes if they really match (hash values of attributes matches)
  323.                 if ( sourceRoot.NodeType == XmlDiffNodeType.Element )
  324.                 {
  325.                     DiffgramPosition diffPos = _cachedDiffgramPosition;
  326.                     diffPos._sourceNode = sourceRoot;
  328.                     GenerateChangeDiffgramForAttributes( diffPos, (XmlDiffElement)sourceRoot, (XmlDiffElement)targetRoot );
  330.                     if ( diffPos._firstChildOp != null || bNeedPosition )
  331.                     {
  332.                         parent.InsertAtBeginning( diffPos );
  333.                         _cachedDiffgramPosition = new DiffgramPosition( null );
  334.                         bNeedPosition = false;
  335.                     }
  336.                 }
  337.                 // otherwise output <node> - only if we need the position (<=> preceding operation was 'add')
  338.                 else
  339.                 {
  340.                     if ( bNeedPosition )
  341.                     {
  342.                         parent.InsertAtBeginning( new DiffgramPosition( sourceRoot, targetRoot ) );
  343.                         bNeedPosition = false;
  344.                     }
  345.                     // xml declaration, DTD
  346.                     else if ( !_bChildOrderSignificant && (int)sourceRoot.NodeType < 0 ) {
  347.                         DiffgramOperation op = parent._firstChildOp;
  348.                         if ( op is DiffgramAddNode || op is DiffgramAddSubtrees || op is DiffgramCopy ) {
  349.                             parent.InsertAtBeginning( new DiffgramPosition( sourceRoot, targetRoot ) );
  350.                         }
  351.                     }
  352.                 }
  353.             }
  355.             // adjust current position
  356.             _curSourceIndex = sourceRoot.Left - 1;
  357.             _curTargetIndex = targetRoot.Left - 1;
  359.             // adjust boundaries in the edit script or move to next edit script operation
  360.             matchOp._length -= endTargetIndex - targetRoot.Left + 1;
  361.             if ( matchOp._length <= 0 )
  362.                 _editScript = _editScript._nextEditScript;
  363.         }
  364.         // single but non-leaf node matches (-> recursively generate the diffgram subtree)
  365.         else
  366.         {
  367.             // adjust current position
  368.             _curSourceIndex--;
  369.             _curTargetIndex--;
  371.             // adjust boundaries in the edit script or move to next edit script operation
  372.             matchOp._length--;
  373.             if ( matchOp._length <= 0 )
  374.                 _editScript = _editScript._nextEditScript;
  376.             DiffgramParentOperation diffgramNode;
  377.             if ( _bBuildingAddTree )
  378.             {
  379.                 Debug.Assert( !bNeedPosition );
  381.                 ulong opid = GenerateOperationID( XmlDiffDescriptorType.Move );
  382.                 bool bCopySubtree = sourceRoot.NodeType != XmlDiffNodeType.Element;
  384.                 // output <add match=".." subtree="no">
  385.                 diffgramNode = new DiffgramCopy( sourceRoot, bCopySubtree, opid );
  386.                 // add 'remove' operation to postponed operations
  387.                 PostponedRemoveNode( sourceRoot, bCopySubtree, opid, 
  388.                                      endSourceIndex, 
  389.                                      endSourceIndex );
  391.                 // recursively generate the diffgram subtree
  392.                 GenerateDiffgramAdd( diffgramNode, sourceRoot.Left, targetRoot.Left );
  394.                 // insert to diffgram tree
  395.                 parent.InsertAtBeginning( diffgramNode );
  396.             }
  397.             else
  398.             {
  399.                 // output <node>
  400.                 diffgramNode = new DiffgramPosition( sourceRoot, targetRoot );
  402.                 // recursively generate the diffgram subtree
  403.                 GenerateDiffgramMatch( diffgramNode, sourceRoot.Left, targetRoot.Left );
  405.                 // insert to diffgram tree
  406.                 if ( diffgramNode._firstChildOp != null )
  407.                     parent.InsertAtBeginning( diffgramNode );
  408.             }
  409.         }
  410.     }
  412.     // returns true if a positioning <node> element is needed in diffgram
  413.     private bool OnAdd( DiffgramParentOperation parent, int sourceBorderIndex, int targetBorderIndex )
  414.     {
  415.         EditScriptAdd addOp = _editScript as EditScriptAdd;
  416.         
  417.         Debug.Assert( addOp._endTargetIndex == _curTargetIndex );
  418.         XmlDiffNode targetRoot = _targetNodes[ addOp._endTargetIndex ];
  420.         // add subtree or leaf node and no descendant node matches (= has been moved from somewhere else)
  421.         if ( addOp._startTargetIndex <= targetRoot.Left &&
  422.              !targetRoot._bSomeDescendantMatches )
  423.         {
  424.             switch ( targetRoot.NodeType )
  425.             {
  426.                 case XmlDiffNodeType.ShrankNode:
  427.     XmlDiffShrankNode shrankNode = (XmlDiffShrankNode)targetRoot;
  429.                     if ( _xmlDiff.IgnoreChildOrder && ParentMatches( shrankNode.MatchingShrankNode, shrankNode, parent ) ) {
  430.                         break;
  431.                     }
  432.                     else {
  433.         if ( shrankNode.MoveOperationId == 0 )
  434.         shrankNode.MoveOperationId = GenerateOperationID( XmlDiffDescriptorType.Move );
  436.         parent.InsertAtBeginning( new DiffgramCopy( shrankNode.MatchingShrankNode, true, shrankNode.MoveOperationId ) );
  437.                     }
  438.                     break;
  440.                 case XmlDiffNodeType.XmlDeclaration:
  441.                 case XmlDiffNodeType.DocumentType:
  442.                 case XmlDiffNodeType.EntityReference:
  443.      parent.InsertAtBeginning( new DiffgramAddNode( targetRoot, 0 ) );
  444.                     break;
  446.                 default:
  447.                     if ( !parent.MergeAddSubtreeAtBeginning( targetRoot ) )
  448.                     {
  449.                         parent.InsertAtBeginning( new DiffgramAddSubtrees( targetRoot, 0, !_xmlDiff.IgnoreChildOrder ) );
  450.                     }
  451.                     break;
  452.             }
  453.             // adjust current position
  454.             _curTargetIndex = targetRoot.Left - 1;
  456.             // adjust boundaries in the edit script or move to next edit script operation
  457.             addOp._endTargetIndex = targetRoot.Left - 1;
  458.             if ( addOp._startTargetIndex > addOp._endTargetIndex )
  459.                 _editScript = _editScript._nextEditScript;
  460.         }
  461.         // add single but non-leaf node, or some descendant matches (= has been moved from somewhere else )
  462.         // -> recursively process diffgram subtree  
  463.         else
  464.         {
  465. Debug.Assert( !( targetRoot is XmlDiffShrankNode) );
  466.             DiffgramAddNode addNode = new DiffgramAddNode( targetRoot, 0 );
  468.             // adjust current position
  469.             _curTargetIndex--;
  471.             // adjust boundaries in the edit script or move to next edit script operation
  472.             addOp._endTargetIndex--;
  473.             if ( addOp._startTargetIndex > addOp._endTargetIndex )
  474.                 _editScript = _editScript._nextEditScript;
  476.             if ( _bBuildingAddTree )
  477.             {
  478.                 GenerateDiffgramAdd( addNode, sourceBorderIndex, targetRoot.Left );
  479.             }
  480.             else
  481.             {
  482.                 // switch to 'building add-tree' mode
  483.                 _postponedEditScript.Reset();
  484.                 _bBuildingAddTree = true;
  486.                 // generate new tree
  487.                 GenerateDiffgramAdd( addNode, sourceBorderIndex, targetRoot.Left );
  489.                 _bBuildingAddTree = false;
  491.                 // attach postponed edit script to _editScript for futher processing
  492.                 if ( _postponedEditScript._firstES != null )
  493.                 {
  494.                     Debug.Assert( _postponedEditScript._lastES != null );
  495.                     Debug.Assert( _postponedEditScript._startSourceIndex != 0 );
  496.                     Debug.Assert( _postponedEditScript._endSourceIndex != 0 );
  497.                     _curSourceIndex = _postponedEditScript._endSourceIndex;
  498.                     _postponedEditScript._lastES._nextEditScript = _editScript;
  499.                     _editScript = _postponedEditScript._firstES;
  500.                 }
  501.             }
  503.             // add attributes
  504.             if ( targetRoot.NodeType == XmlDiffNodeType.Element ) 
  505.                 GenerateAddDiffgramForAttributes( addNode, (XmlDiffElement)targetRoot );
  506.             
  507.             parent.InsertAtBeginning( addNode );
  508.         }
  510.         // return true if positioning <node> element is needed in diffgram
  511.         if ( _bChildOrderSignificant ) {
  512.             return !_bBuildingAddTree;
  513.         }
  514.         else {
  515.             return false;
  516.         }
  517.     }
  519.     private void OnRemove( DiffgramParentOperation parent )
  520.     {
  521.         EditScriptRemove remOp = _editScript as EditScriptRemove;
  523.         Debug.Assert( remOp._endSourceIndex == _curSourceIndex );
  524.         XmlDiffNode sourceRoot = _sourceNodes[ remOp._endSourceIndex ];
  526.         // remove subtree or leaf node and no descendant node matches (=has been moved somewhere else)
  527.         if ( remOp._startSourceIndex <= sourceRoot.Left )
  528.         {
  529.             bool bShrankNode = sourceRoot is XmlDiffShrankNode;
  531.             if ( sourceRoot._bSomeDescendantMatches && !bShrankNode )
  532.             {
  533.                 DiffgramOperation newDiffOp = GenerateDiffgramRemoveWhenDescendantMatches( (XmlDiffParentNode)sourceRoot );
  534.                 if ( _bBuildingAddTree )
  535.                 {
  536.                     PostponedOperation( newDiffOp, sourceRoot.Left, remOp._endSourceIndex );
  537.                 }
  538.                 else
  539.                 {
  540.                     parent.InsertAtBeginning( newDiffOp );
  541.                 }
  542.             }
  543.             else
  544.             {
  545.     ulong opid = 0;
  546.                 // shrank node -> output as 'move' operation
  547.     if ( bShrankNode )
  548.     {
  549.     XmlDiffShrankNode shrankNode = (XmlDiffShrankNode) sourceRoot;
  550.                     if ( _xmlDiff.IgnoreChildOrder && ParentMatches( shrankNode, shrankNode.MatchingShrankNode, parent ) ) {
  551.                         goto End;
  552.                     }
  553.     if ( shrankNode.MoveOperationId == 0 )
  554.     shrankNode.MoveOperationId = GenerateOperationID( XmlDiffDescriptorType.Move );
  555.     opid = shrankNode.MoveOperationId;
  557.     Debug.Assert( sourceRoot == _sourceNodes[ sourceRoot.Left ] );
  558.     }
  560.                 // insert 'remove' operation 
  561.     if ( _bBuildingAddTree )
  562.                 {
  563.                     PostponedRemoveSubtrees( sourceRoot, opid, sourceRoot.Left, remOp._endSourceIndex );
  564.                 }
  565.     else
  566.     {
  567.     if ( opid != 0 ||
  568.     !parent.MergeRemoveSubtreeAtBeginning( sourceRoot ) )
  569.     {
  570.     parent.InsertAtBeginning( new DiffgramRemoveSubtrees( sourceRoot, opid, !_xmlDiff.IgnoreChildOrder ) );
  571.     }
  572.     }
  573.             }
  574.         End:
  575.             // adjust current position
  576.             _curSourceIndex = sourceRoot.Left - 1;
  578.             // adjust boundaries in the edit script or move to next edit script operation
  579.             remOp._endSourceIndex = sourceRoot.Left - 1;
  580.             if ( remOp._startSourceIndex > remOp._endSourceIndex )
  581.                 _editScript = _editScript._nextEditScript;
  582.         }
  583.         // remove single but non-leaf node or some descendant matches (=has been moved somewhere else)
  584.         // -> recursively process diffgram subtree  
  585.         else
  586.         {
  587. Debug.Assert( !( sourceRoot is XmlDiffShrankNode) );
  589.             // adjust current position
  590.             _curSourceIndex--;
  592.             // adjust boundaries in the edit script or move to next edit script operation
  593.             remOp._endSourceIndex--;
  594.             if ( remOp._startSourceIndex > remOp._endSourceIndex )
  595.                 _editScript = _editScript._nextEditScript;
  597.             bool bRemoveSubtree = sourceRoot.NodeType != XmlDiffNodeType.Element;
  599.             if ( _bBuildingAddTree )
  600.             {
  601.                 // add 'remove' to postponed operations 
  602.                 PostponedRemoveNode( sourceRoot, bRemoveSubtree, 0,
  603.                 //AddToPosponedOperations( new DiffgramRemoveNode( sourceRoot, bRemoveSubtree, 0 ), 
  604.                     remOp._endSourceIndex + 1, remOp._endSourceIndex + 1 );
  605.                 
  606.                 // recursively parse subtree
  607.                 GenerateDiffgramAdd( parent, sourceRoot.Left, _targetNodes[ _curTargetIndex ].Left );
  608.             }
  609.             else
  610.             {
  611.                 // 'remove' operation
  612.                 DiffgramRemoveNode remNode = new DiffgramRemoveNode( sourceRoot, bRemoveSubtree, 0 );
  613.                 
  614.                 // parse subtree
  615.                 GenerateDiffgramMatch( remNode, sourceRoot.Left, _targetNodes[ _curTargetIndex ].Left );
  616.                 
  617.                 parent.InsertAtBeginning( remNode );
  618.             }
  619.         }
  620.     }
  622.     // produces <change> element in diffgram
  623.     private void OnChange( DiffgramParentOperation parent )
  624.     {
  625.         EditScriptChange chOp = _editScript as EditScriptChange;
  627.         Debug.Assert( chOp._targetIndex == _curTargetIndex );
  628.         Debug.Assert( chOp._sourceIndex == _curSourceIndex );
  630.         XmlDiffNode sourceRoot = _sourceNodes[ chOp._sourceIndex ];
  631.         XmlDiffNode targetRoot = _targetNodes[ chOp._targetIndex ];
  633. Debug.Assert( !( sourceRoot is XmlDiffShrankNode) );
  634. Debug.Assert( !( targetRoot is XmlDiffShrankNode) );
  636.         // adjust current position
  637.         _curSourceIndex--;
  638.         _curTargetIndex--;
  640.         // move to next edit script operation
  641.         _editScript = _editScript._nextEditScript;
  643.         DiffgramOperation diffgramNode = null;
  645.         if ( _bBuildingAddTree )
  646.         {
  647.             // <add> changed node to the new location
  648.             if ( targetRoot.NodeType == XmlDiffNodeType.Element )
  649.                 diffgramNode = new DiffgramAddNode( targetRoot, 0 );
  650.             else
  651.                 diffgramNode = new DiffgramAddSubtrees( targetRoot, 0, !_xmlDiff.IgnoreChildOrder );
  653.             // <remove> old node from old location -> add to postponed operations
  654.             bool bSubtree = sourceRoot.NodeType != XmlDiffNodeType.Element;
  655.             PostponedRemoveNode( sourceRoot, bSubtree, 0,
  656.             //AddToPosponedOperations( new DiffgramRemoveNode( sourceRoot, bSubtree, 0 ), 
  657.                 chOp._sourceIndex, chOp._sourceIndex );
  659.             // recursively process children
  660.             if ( sourceRoot.Left < chOp._sourceIndex ||
  661.                 targetRoot.Left < chOp._targetIndex )
  662.             {
  663.                 Debug.Assert( targetRoot.NodeType == XmlDiffNodeType.Element );
  664.                 GenerateDiffgramAdd( (DiffgramParentOperation)diffgramNode, sourceRoot.Left, targetRoot.Left );
  665.             }
  667.             // add attributes, if element
  668.             if ( targetRoot.NodeType == XmlDiffNodeType.Element )
  669.                 GenerateAddDiffgramForAttributes( (DiffgramParentOperation)diffgramNode, (XmlDiffElement)targetRoot );
  670.         }
  671.         else
  672.         {
  673.             ulong opid = 0;
  675.             // change of namespace or prefix -> get the appropriate operation id
  676.             if ( !_xmlDiff.IgnoreNamespaces && 
  677.                  sourceRoot.NodeType == XmlDiffNodeType.Element )
  678.             {
  679.                 XmlDiffElement sourceEl = (XmlDiffElement)sourceRoot;
  680.                 XmlDiffElement targetEl = (XmlDiffElement)targetRoot;
  682.                 if ( sourceEl.LocalName == targetEl.LocalName )
  683.                 {
  684.                     opid = GetNamespaceChangeOpid( sourceEl.NamespaceURI, sourceEl.Prefix,
  685.                                                    targetEl.NamespaceURI, targetEl.Prefix );
  686.                 }  
  687.             }
  689.             if ( sourceRoot.NodeType == XmlDiffNodeType.Element )
  690.             {
  691.                 if ( XmlDiff.IsChangeOperationOnAttributesOnly( chOp._changeOp ) )
  692.                     diffgramNode = new DiffgramPosition( sourceRoot );
  693.                 else
  694.                 {
  695.                     Debug.Assert( (int)chOp._changeOp == (int)XmlDiffOperation.ChangeElementName ||
  696.                                   ( (int)chOp._changeOp >= (int)XmlDiffOperation.ChangeElementNameAndAttr1 &&
  697.                                     (int)chOp._changeOp <= (int)XmlDiffOperation.ChangeElementNameAndAttr2 ) );
  699.                     diffgramNode = new DiffgramChangeNode( sourceRoot, targetRoot, XmlDiffOperation.ChangeElementName, opid );
  700.                 }
  702.                 // recursively process children
  703.                 if ( sourceRoot.Left < chOp._sourceIndex ||
  704.                     targetRoot.Left < chOp._targetIndex )
  705.                 {
  706.                     GenerateDiffgramMatch( (DiffgramParentOperation) diffgramNode, sourceRoot.Left, targetRoot.Left );
  707.                 }
  709.                 GenerateChangeDiffgramForAttributes( (DiffgramParentOperation)diffgramNode, (XmlDiffElement)sourceRoot, (XmlDiffElement)targetRoot );
  710.             }
  711.             else
  712.             {
  713.                 // '<change>'
  714.                 diffgramNode = new DiffgramChangeNode( sourceRoot, targetRoot, chOp._changeOp, opid );
  715.                 Debug.Assert( !sourceRoot.HasChildNodes );
  716.             }
  717.         }
  719.         parent.InsertAtBeginning( diffgramNode );
  720.     }
  722.     private void PostponedRemoveNode( XmlDiffNode sourceNode, bool bSubtree, ulong operationID,
  723.                                       int startSourceIndex, int endSourceIndex )
  724.     {
  725.         Debug.Assert( sourceNode != null );
  726.         PostponedOperation( new DiffgramRemoveNode( sourceNode, bSubtree, operationID ), startSourceIndex, endSourceIndex );
  727.     }
  729.     private void PostponedRemoveSubtrees( XmlDiffNode sourceNode, ulong operationID,
  730.                                           int startSourceIndex, int endSourceIndex )
  731.     {
  732.         Debug.Assert( _bBuildingAddTree );
  733.         Debug.Assert( sourceNode != null );
  735.         if ( operationID == 0 &&
  736.              _postponedEditScript._firstES != null )
  737.         {
  738.             Debug.Assert( _postponedEditScript._lastES._startSourceIndex > endSourceIndex );
  740.             DiffgramRemoveSubtrees remSubtrees = _postponedEditScript._lastES._diffOperation as DiffgramRemoveSubtrees;
  741.             if ( remSubtrees != null  && 
  742.                 remSubtrees.SetNewFirstNode( sourceNode ) )
  743.             {
  744.                 _postponedEditScript._lastES._startSourceIndex = startSourceIndex;
  745.                 _postponedEditScript._startSourceIndex = startSourceIndex;
  746.                 return;
  747.             }
  748.         }
  749.         
  750.         PostponedOperation( new DiffgramRemoveSubtrees( sourceNode, operationID, !_xmlDiff.IgnoreChildOrder ), startSourceIndex, endSourceIndex );
  751.     }
  753.     private void PostponedOperation( DiffgramOperation op, int startSourceIndex, int endSourceIndex )
  754.     {
  755.         Debug.Assert( _bBuildingAddTree );
  756.         Debug.Assert( op != null );
  758.         EditScriptPostponed es = new EditScriptPostponed( op, startSourceIndex, endSourceIndex );
  760.         if ( _postponedEditScript._firstES == null )
  761.         {
  762.             _postponedEditScript._firstES = es;
  763.             _postponedEditScript._lastES = es;
  764.             _postponedEditScript._startSourceIndex = startSourceIndex;
  765.             _postponedEditScript._endSourceIndex = endSourceIndex;
  766.         }
  767.         else
  768.         {
  769.             Debug.Assert( _postponedEditScript._lastES != null );
  770.             Debug.Assert( _postponedEditScript._lastES._startSourceIndex > endSourceIndex );
  772.             _postponedEditScript._lastES._nextEditScript = es;
  773.             _postponedEditScript._lastES = es;
  775.             _postponedEditScript._startSourceIndex = startSourceIndex;
  776.         }
  777.     }
  779.     // generates a new operation ID
  780.     private ulong GenerateOperationID( XmlDiffDescriptorType descriptorType )
  781.     {
  782.         ulong opid = ++_lastOperationID;
  784.         if ( descriptorType == XmlDiffDescriptorType.Move )
  785.             _moveDescriptors.Add( opid, opid );
  786.         return opid;
  787.     }
  789.     // returns appropriate operation ID for this namespace or prefix change
  790.     private ulong GetNamespaceChangeOpid( string oldNamespaceURI, string oldPrefix, 
  791.                                           string newNamespaceURI, string newPrefix )
  792.     {
  793.         Debug.Assert( !_xmlDiff.IgnoreNamespaces );
  795.         ulong opid = 0;
  797.         // namespace change
  798.         if ( oldNamespaceURI != newNamespaceURI )
  799.         {
  800.             // prefix must remain the same
  801.             if ( oldPrefix != newPrefix )
  802.                 return 0;
  804.             // lookup this change in the list of namespace changes
  805.             NamespaceChange nsChange = _namespaceChangeDescr;
  806.             while ( nsChange != null )
  807.             {
  808.                 if ( nsChange._oldNS == oldNamespaceURI &&
  809.                      nsChange._prefix == oldPrefix &&
  810.                      nsChange._newNS == newNamespaceURI )
  811.                 {
  812.                     return nsChange._opid;
  813.                 }
  815.                 nsChange = nsChange._next;
  816.             }
  817.             
  818.             // the change record was not found -> create a new one
  819.             opid = GenerateOperationID( XmlDiffDescriptorType.NamespaceChange );
  820.             _namespaceChangeDescr = new NamespaceChange( oldPrefix, oldNamespaceURI, newNamespaceURI,
  821.                                                          opid, _namespaceChangeDescr );
  822.         }
  823.         // prefix change
  824.         else if ( !_xmlDiff.IgnorePrefixes && 
  825.                   oldPrefix != newPrefix )
  826.         {
  827.             // lookup this change in the list of prefix changes
  828.             PrefixChange prefixChange = _prefixChangeDescr;
  829.             while ( prefixChange != null )
  830.             {
  831.                 if ( prefixChange._NS == oldNamespaceURI &&
  832.                      prefixChange._oldPrefix == oldPrefix &&
  833.                      prefixChange._newPrefix == newPrefix )
  834.                 {
  835.                     return prefixChange._opid;
  836.                 }
  838.                 prefixChange = prefixChange._next;
  839.             }
  841.             // the change record was not found -> create a new one
  842.             opid = GenerateOperationID( XmlDiffDescriptorType.PrefixChange );
  843.             _prefixChangeDescr = new PrefixChange( oldPrefix, newPrefix, 
  844.                                                    oldNamespaceURI,
  845.                                                    opid, 
  846.                                                    _prefixChangeDescr );
  847.         }
  849.         return opid;
  850.     }
  852. internal Diffgram GenerateEmptyDiffgram()
  853. {
  854. return new Diffgram( _xmlDiff );
  855. }
  857.     private void GenerateChangeDiffgramForAttributes( DiffgramParentOperation diffgramParent, 
  858.                                                       XmlDiffElement sourceElement, 
  859.                                                       XmlDiffElement targetElement )
  860.     {
  861.         XmlDiffAttributeOrNamespace sourceAttr = sourceElement._attributes;
  862.         XmlDiffAttributeOrNamespace targetAttr = targetElement._attributes;
  863.         int nCompare;
  864.         ulong opid;
  866.         while ( sourceAttr != null && targetAttr != null ) 
  867.         {
  868.             opid = 0;
  870.             if ( sourceAttr.NodeType == targetAttr.NodeType )
  871.             {
  872.                 if ( sourceAttr.NodeType == XmlDiffNodeType.Attribute ) 
  873.                 {
  874.                     if ( (nCompare = XmlDiffDocument.OrderStrings( sourceAttr.LocalName, targetAttr.LocalName )) == 0 )
  875.                     {
  876.                         if ( _xmlDiff.IgnoreNamespaces )
  877.                         {
  878.                             if ( XmlDiffDocument.OrderStrings( sourceAttr.Value, targetAttr.Value ) == 0 )
  879.                             {
  880.                                 // attributes match
  881.                                 goto Next;
  882.                             }
  883.                         }
  884.                         else
  885.                         {
  886.                             if ( XmlDiffDocument.OrderStrings( sourceAttr.NamespaceURI, targetAttr.NamespaceURI ) == 0  &&  
  887.                          (_xmlDiff.IgnorePrefixes || XmlDiffDocument.OrderStrings( sourceAttr.Prefix, targetAttr.Prefix )  == 0 ) &&
  888.                                 XmlDiffDocument.OrderStrings( sourceAttr.Value, targetAttr.Value ) == 0 )
  889.                             {
  890.                                 // attributes match
  891.                                 goto Next;
  892.                             }
  893.                         }
  895.                         diffgramParent.InsertAtBeginning( new DiffgramChangeNode( sourceAttr, targetAttr, XmlDiffOperation.ChangeAttr, 0 ) );
  896.                         goto Next;
  897.                     }
  899.                     goto AddRemove;
  900.                 }
  901.                 else // sourceAttr.NodeType != XmlDiffNodeType.Attribute 
  902.                 {
  903.                     if ( _xmlDiff.IgnorePrefixes ) {
  904.                         if ( ( nCompare = XmlDiffDocument.OrderStrings( sourceAttr.NamespaceURI, targetAttr.NamespaceURI ) ) == 0 )
  905.                             goto Next;
  906.                         else
  907.                             goto AddRemove;
  908.                     }
  909.                     else if ( ( nCompare = XmlDiffDocument.OrderStrings( sourceAttr.Prefix, targetAttr.Prefix ) ) == 0 ) {
  910.                         if ( ( nCompare = XmlDiffDocument.OrderStrings( sourceAttr.NamespaceURI, targetAttr.NamespaceURI ) ) == 0 )
  911.                             goto Next;
  912.                         else {
  913.                             // change of namespace
  914.                             opid = GetNamespaceChangeOpid( sourceAttr.NamespaceURI, sourceAttr.Prefix, 
  915.                                                         targetAttr.NamespaceURI, targetAttr.Prefix );
  916.                             goto AddRemoveBoth;
  917.                         }
  918.                     }
  919.                     else {
  920.                         if ( ( nCompare = XmlDiffDocument.OrderStrings( sourceAttr.NamespaceURI, targetAttr.NamespaceURI ) ) == 0 ) {
  921.                             // change of prefix
  922.                             opid = GetNamespaceChangeOpid( sourceAttr.NamespaceURI, sourceAttr.Prefix, 
  923.                                                         targetAttr.NamespaceURI, targetAttr.Prefix );
  924.                             goto AddRemoveBoth;
  925.                         }
  926.                         else {
  927.                             goto AddRemove;
  928.                         }
  929.                     }
  930.                 }
  931.             }
  932.             else // ( sourceAttr.NodeType != targetAttr.NodeType )
  933.             {
  934.     if ( sourceAttr.NodeType == XmlDiffNodeType.Namespace )
  935.          goto RemoveSource;
  936.          else
  937.          goto AddTarget;
  938.             }
  940.         Next:
  941.             sourceAttr = (XmlDiffAttributeOrNamespace)sourceAttr._nextSibling;
  942.             targetAttr = (XmlDiffAttributeOrNamespace)targetAttr._nextSibling;
  943.             continue;
  945.         AddRemove:
  946.             if ( nCompare == -1 )
  947.                 goto RemoveSource;
  948.             else
  949.             {
  950.                 Debug.Assert( nCompare == 1 );
  951.                 goto AddTarget;
  952.             }
  953.                 
  954.         AddRemoveBoth:
  955.             if ( !diffgramParent.MergeRemoveAttributeAtBeginning( sourceAttr ) )
  956.                 diffgramParent.InsertAtBeginning( new DiffgramRemoveNode( sourceAttr, true, opid ) );
  957.             sourceAttr = (XmlDiffAttributeOrNamespace)sourceAttr._nextSibling;
  959.             diffgramParent.InsertAtBeginning( new DiffgramAddNode( targetAttr, opid ) );
  960.             targetAttr = (XmlDiffAttributeOrNamespace)targetAttr._nextSibling;
  961.             continue;
  962.             
  963.         RemoveSource:
  964.             if ( !diffgramParent.MergeRemoveAttributeAtBeginning( sourceAttr ) )
  965.                 diffgramParent.InsertAtBeginning( new DiffgramRemoveNode( sourceAttr, true, opid ) );
  966.             sourceAttr = (XmlDiffAttributeOrNamespace)sourceAttr._nextSibling;
  967.             continue;
  968.                 
  969.         AddTarget:
  970.             diffgramParent.InsertAtBeginning( new DiffgramAddNode( targetAttr, opid ) );
  971.             targetAttr = (XmlDiffAttributeOrNamespace)targetAttr._nextSibling;
  972.             continue;
  973.         }
  975.         while ( sourceAttr != null ) 
  976.         {
  977.             if ( !diffgramParent.MergeRemoveAttributeAtBeginning( sourceAttr ) )
  978.                 diffgramParent.InsertAtBeginning( new DiffgramRemoveNode( sourceAttr, true, 0 ) );
  979.             sourceAttr = (XmlDiffAttributeOrNamespace)sourceAttr._nextSibling;
  980.         }
  982.         while ( targetAttr != null )
  983.         {
  984.             diffgramParent.InsertAtBeginning( new DiffgramAddNode( targetAttr, 0 ) );
  985.             targetAttr = (XmlDiffAttributeOrNamespace)targetAttr._nextSibling;
  986.         }
  987.     }
  989.     private void GenerateAddDiffgramForAttributes( DiffgramParentOperation diffgramParent, XmlDiffElement targetElement )
  990.     {
  991.         XmlDiffAttributeOrNamespace attr = targetElement._attributes;
  992.         while ( attr != null )
  993.         {
  994.             diffgramParent.InsertAtBeginning( new DiffgramAddNode( attr, 0 ) );
  995.             attr = (XmlDiffAttributeOrNamespace)attr._nextSibling;
  996.         }
  997.     }
  999.     private DiffgramOperation GenerateDiffgramRemoveWhenDescendantMatches( XmlDiffNode sourceParent )
  1000.     {
  1001.         Debug.Assert( sourceParent._bSomeDescendantMatches );
  1002.         Debug.Assert( sourceParent.NodeType != XmlDiffNodeType.ShrankNode );
  1004.         DiffgramParentOperation diffOp = new DiffgramRemoveNode( sourceParent, false, 0 );
  1005.         XmlDiffNode child = ((XmlDiffParentNode)sourceParent)._firstChildNode;
  1006.         while ( child != null )
  1007.         {
  1008.             if ( child.NodeType == XmlDiffNodeType.ShrankNode )
  1009.             {
  1010.                 XmlDiffShrankNode shrankNode = (XmlDiffShrankNode) child;
  1012.                 if ( shrankNode.MoveOperationId == 0 )
  1013.      shrankNode.MoveOperationId = GenerateOperationID( XmlDiffDescriptorType.Move );
  1015. diffOp.InsertAtEnd( new DiffgramRemoveSubtrees( child, shrankNode.MoveOperationId, !_xmlDiff.IgnoreChildOrder ) );
  1017.             }
  1018.             else if ( child.HasChildNodes && child._bSomeDescendantMatches )
  1019.             {
  1020.                 diffOp.InsertAtEnd( GenerateDiffgramRemoveWhenDescendantMatches( (XmlDiffParentNode)child ) );
  1021.             }
  1022.             else
  1023.             {
  1024.                 if ( !diffOp.MergeRemoveSubtreeAtEnd( child ) )
  1025.                     diffOp.InsertAtEnd( new DiffgramRemoveSubtrees( child, 0, !_xmlDiff.IgnoreChildOrder ) );
  1026.             }
  1028.             child = child._nextSibling;
  1029.         }
  1030.         return diffOp;
  1031.     }
  1033.     private DiffgramOperation GenerateDiffgramAddWhenDescendantMatches( XmlDiffNode targetParent ) {
  1034.         Debug.Assert( targetParent.HasChildNodes );
  1035.         Debug.Assert( targetParent._bSomeDescendantMatches );
  1036.         Debug.Assert( targetParent.NodeType != XmlDiffNodeType.ShrankNode );
  1038.         DiffgramParentOperation diffOp = new DiffgramAddNode( targetParent, 0 );
  1039.         if ( targetParent.NodeType == XmlDiffNodeType.Element ) {
  1040.             XmlDiffAttributeOrNamespace attr = ((XmlDiffElement)targetParent)._attributes;
  1041.             while ( attr != null ) {
  1042.                 diffOp.InsertAtEnd( new DiffgramAddNode( attr, 0 ) );
  1043.                 attr = (XmlDiffAttributeOrNamespace) attr._nextSibling;
  1044.             }
  1045.         }
  1046.         
  1047.         XmlDiffNode child = ((XmlDiffParentNode)targetParent)._firstChildNode;
  1048.         while ( child != null )
  1049.         {
  1050.             if ( child.NodeType == XmlDiffNodeType.ShrankNode )
  1051.             {
  1052.                 XmlDiffShrankNode shrankNode = (XmlDiffShrankNode) child;
  1054.                 if ( shrankNode.MoveOperationId == 0 )
  1055.      shrankNode.MoveOperationId = GenerateOperationID( XmlDiffDescriptorType.Move );
  1057. diffOp.InsertAtEnd( new DiffgramCopy( shrankNode.MatchingShrankNode, true, shrankNode.MoveOperationId ) );
  1058.             }
  1059.             else if ( child.HasChildNodes && child._bSomeDescendantMatches )
  1060.             {
  1061.                 diffOp.InsertAtEnd( GenerateDiffgramAddWhenDescendantMatches( (XmlDiffParentNode)child ) );
  1062.             }
  1063.             else
  1064.             {
  1065.                 if ( !diffOp.MergeAddSubtreeAtEnd( child ) )
  1066.                     diffOp.InsertAtEnd( new DiffgramAddSubtrees( child, 0, !_xmlDiff.IgnoreChildOrder ) );
  1067.             }
  1069.             child = child._nextSibling;
  1070.         }
  1071.         return diffOp;
  1072.     }
  1074.     void OnEditScriptPostponed( DiffgramParentOperation parent, int targetBorderIndex ) {
  1075.         EditScriptPostponed esp = (EditScriptPostponed)_editScript;
  1076.         Debug.Assert( _curSourceIndex == esp._endSourceIndex );
  1078.         DiffgramOperation diffOp = esp._diffOperation;
  1079.         int sourceStartIndex = esp._startSourceIndex;
  1080.         int sourceLeft = _sourceNodes[ esp._endSourceIndex ].Left;
  1082.         // adjust current source index
  1083.         _curSourceIndex = esp._startSourceIndex - 1;
  1084.            
  1085.         // move to next edit script
  1086.         _editScript = esp._nextEditScript;
  1088.         // not a subtree or leaf node operation -> process child operations
  1089.         if ( sourceStartIndex > sourceLeft ) {
  1090.             GenerateDiffgramPostponed( (DiffgramParentOperation)diffOp, ref _editScript, sourceLeft, targetBorderIndex );
  1091.         }
  1093.         parent.InsertAtBeginning( diffOp );
  1094.     }
  1096. // Walktree diffgram generation
  1098.     internal Diffgram GenerateFromWalkTree() {
  1099.         Diffgram diffgram = new Diffgram( _xmlDiff );
  1100.         WalkTreeGenerateDiffgramMatch( diffgram, _xmlDiff._sourceDoc, _xmlDiff._targetDoc );
  1101.         AppendDescriptors( diffgram );
  1102.         return diffgram;
  1103.     }
  1105.     private void WalkTreeGenerateDiffgramMatch( DiffgramParentOperation diffParent, XmlDiffParentNode sourceParent, XmlDiffParentNode targetParent ) {
  1106.         XmlDiffNode sourceNode = sourceParent.FirstChildNode;
  1107.         XmlDiffNode targetNode = targetParent.FirstChildNode;
  1108.         XmlDiffNode needPositionSourceNode = null;
  1110.         while ( sourceNode != null || targetNode != null ) {
  1111.             if ( sourceNode != null ) {
  1112.                 if ( targetNode != null ) {
  1113.                     XmlDiffOperation op = sourceNode.GetDiffOperation( targetNode, _xmlDiff );
  1114.                     // match
  1115.                     if ( op == XmlDiffOperation.Match ) {
  1116.                         WalkTreeOnMatchNode( diffParent, sourceNode, targetNode, ref needPositionSourceNode );
  1117.                     }
  1118.                     // no match
  1119.                     else {
  1120.                         int walkNodesCount = ( sourceNode._parent.ChildNodesCount + targetNode._parent.ChildNodesCount ) / 2;
  1121.                         walkNodesCount = (int)( LogMultiplier * Math.Log( (double)walkNodesCount ) + 1 );
  1123.                         XmlDiffNode sourceClosestMatchNode = targetNode;
  1124.                         XmlDiffNode targetClosestMatchNode = sourceNode;
  1125.                         XmlDiffOperation sourceOp = op;
  1126.                         XmlDiffOperation targetOp = op;
  1127.                         int sourceNodesToAddCount = targetNode.NodesCount;
  1128.                         int targetNodesToRemoveCount = sourceNode.NodesCount;
  1130.                         XmlDiffNode nextSourceNode = sourceNode._nextSibling;
  1131.                         XmlDiffNode nextTargetNode = targetNode._nextSibling;
  1133.                         // walk limited number of siblings to find the closest matching node
  1134.                         for ( int i = 0; i < walkNodesCount && ( nextTargetNode != null || nextSourceNode != null ); i++ ) {
  1135.                             if ( nextTargetNode != null && sourceOp != XmlDiffOperation.Match ) {
  1136.                                 XmlDiffOperation o = sourceNode.GetDiffOperation( nextTargetNode, _xmlDiff );
  1137.                                 if ( MinimalTreeDistanceAlgo.OperationCost[(int)o] < MinimalTreeDistanceAlgo.OperationCost[(int)sourceOp] ) {
  1138.                                     sourceOp = o;
  1139.                                     sourceClosestMatchNode = nextTargetNode;
  1140.                                 }
  1141.                                 else {
  1142.                                     sourceNodesToAddCount += nextTargetNode.NodesCount;
  1143.                                     nextTargetNode = nextTargetNode._nextSibling;
  1144.                                 }
  1145.                             }
  1147.                             if ( nextSourceNode != null && targetOp != XmlDiffOperation.Match ) {
  1148.                                 XmlDiffOperation o = targetNode.GetDiffOperation( nextSourceNode, _xmlDiff );
  1149.                                 if ( MinimalTreeDistanceAlgo.OperationCost[(int)o] < MinimalTreeDistanceAlgo.OperationCost[(int)targetOp] ) {
  1150.                                     targetOp = o;
  1151.                                     targetClosestMatchNode = nextSourceNode;
  1152.                                 }
  1153.                                 else {
  1154.                                     targetNodesToRemoveCount += nextSourceNode.NodesCount;
  1155.                                     nextSourceNode = nextSourceNode._nextSibling;
  1156.                                 }
  1157.                             }
  1159.                             if ( sourceOp == XmlDiffOperation.Match || targetOp == XmlDiffOperation.Match ) {
  1160.                                 break;
  1161.                             }
  1163.                             if ( _xmlDiff.IgnoreChildOrder ) {
  1164.                                 if ( nextTargetNode != null ) {
  1165.                                     if ( XmlDiffDocument.OrderChildren( sourceNode, nextTargetNode ) < 0 ) {
  1166.                                         nextTargetNode = null;
  1167.                                     }
  1168.                                 }
  1169.                                 if ( nextSourceNode != null ) {
  1170.                                     if ( XmlDiffDocument.OrderChildren( targetNode, nextSourceNode ) < 0 ) {
  1171.                                         nextSourceNode = null;
  1172.                                     }
  1173.                                 }
  1174.                             }
  1175.                         }
  1177.                         // source match exists and is better
  1178.                         if ( sourceOp == XmlDiffOperation.Match ) {
  1179.                             if ( targetOp != XmlDiffOperation.Match || sourceNodesToAddCount < targetNodesToRemoveCount ) {
  1180.                                 while ( targetNode != sourceClosestMatchNode ) {
  1181.                                     WalkTreeOnAddNode( diffParent, targetNode, needPositionSourceNode );
  1182.                                     needPositionSourceNode = null;
  1183.                                     targetNode = targetNode._nextSibling;
  1184.                                 }
  1185.                                 WalkTreeOnMatchNode( diffParent, sourceNode, targetNode, ref needPositionSourceNode ); 
  1186.                                 goto MoveToNextPair;
  1187.                             }
  1188.                         }
  1189.                         // target match exists and is better
  1190.                         else if ( targetOp == XmlDiffOperation.Match ) {
  1191.                             while ( sourceNode != targetClosestMatchNode ) {
  1192.                                 WalkTreeOnRemoveNode( diffParent, sourceNode );
  1193.                                 sourceNode = sourceNode._nextSibling;
  1194.                             }
  1195.                             needPositionSourceNode = null;
  1196.                             WalkTreeOnMatchNode( diffParent, sourceNode, targetNode, ref needPositionSourceNode );
  1197.                             goto MoveToNextPair;
  1198.                         }
  1199.                         // partial match
  1200.                         else {
  1201.                             Debug.Assert( sourceOp != XmlDiffOperation.Match && targetOp != XmlDiffOperation.Match );
  1203.                             int sourceOpCost = MinimalTreeDistanceAlgo.OperationCost[ (int)sourceOp ];
  1204.                             int targetOpCost = MinimalTreeDistanceAlgo.OperationCost[ (int)targetOp ];
  1206.                             if ( sourceOpCost < targetOpCost || ( sourceOpCost == targetOpCost && sourceNodesToAddCount < targetNodesToRemoveCount ) ) {
  1207.                                 while ( targetNode != sourceClosestMatchNode ) {
  1208.                                     WalkTreeOnAddNode( diffParent, targetNode, needPositionSourceNode );
  1209.                                     needPositionSourceNode = null;
  1210.                                     targetNode = targetNode._nextSibling;
  1211.                                 }
  1212.                                 op = sourceOp;
  1213.                             }
  1214.                             else {
  1215.                                 while ( sourceNode != targetClosestMatchNode ) {
  1216.                                     WalkTreeOnRemoveNode( diffParent, sourceNode );
  1217.                                     sourceNode = sourceNode._nextSibling;
  1218.                                 }
  1219.                                 op = targetOp;
  1220.                             }
  1221.                         }
  1223.                         // decide whether do 'change' or 'add / delete'
  1224.                         switch ( op ) {
  1225.                             case XmlDiffOperation.ChangeElementName:
  1226.                                 WalkTreeOnChangeElement( diffParent, (XmlDiffElement)sourceNode, (XmlDiffElement)targetNode, op );
  1227.                                 needPositionSourceNode = null;
  1228.                                 break;
  1229.                             case XmlDiffOperation.ChangeElementAttr1:
  1230.                             case XmlDiffOperation.ChangeElementAttr2:
  1231.                             case XmlDiffOperation.ChangeElementAttr3:
  1232.                             case XmlDiffOperation.ChangeElementNameAndAttr1:
  1233.                             case XmlDiffOperation.ChangeElementNameAndAttr2:
  1234.                             case XmlDiffOperation.ChangeElementNameAndAttr3:
  1235.                                 if ( GoForElementChange( (XmlDiffElement)sourceNode, (XmlDiffElement)targetNode ) ) {
  1236.                                     WalkTreeOnChangeElement( diffParent, (XmlDiffElement) sourceNode, (XmlDiffElement)targetNode, op );
  1237.                                     needPositionSourceNode = null;
  1238.                                 }
  1239.                                 else {
  1240.                                     goto case XmlDiffOperation.Undefined;
  1241.                                 }
  1242.                                 break;
  1243.                             case XmlDiffOperation.ChangePI:
  1244.                             case XmlDiffOperation.ChangeER:
  1245.                             case XmlDiffOperation.ChangeCharacterData:
  1246.                             case XmlDiffOperation.ChangeXmlDeclaration:
  1247.                             case XmlDiffOperation.ChangeDTD:
  1248.                                 diffParent.InsertAtEnd( new DiffgramChangeNode( sourceNode, targetNode, op, 0 ) );
  1249.                                 needPositionSourceNode = null;
  1250.                                 break;
  1252.                             case XmlDiffOperation.Undefined:
  1253.                                 // Prefer inserts against removes
  1254.                                 WalkTreeOnAddNode( diffParent, targetNode, needPositionSourceNode );
  1255.                                 needPositionSourceNode = null;
  1256.                                 targetNode = targetNode._nextSibling;
  1257.                                 continue;
  1258.                             default:
  1259.                                 Debug.Assert( false );
  1260.                                 break;
  1261.                         }
  1262.                     }
  1264.                 MoveToNextPair:
  1265.                     sourceNode = sourceNode._nextSibling;
  1266.                     targetNode = targetNode._nextSibling;
  1267.                 }
  1268.                 else { // targetNode == null
  1269.                     do {
  1270.                         WalkTreeOnRemoveNode( diffParent, sourceNode );
  1271.                         sourceNode = sourceNode._nextSibling;
  1272.                     } while ( sourceNode != null );
  1273.                 }
  1274.             } 
  1275.             else { // sourceNode == null
  1276.                 Debug.Assert( targetNode != null );
  1278.                 while ( targetNode != null ) {
  1279.                     WalkTreeOnAddNode( diffParent, targetNode, needPositionSourceNode );
  1280.                     needPositionSourceNode = null;
  1281.                     targetNode = targetNode._nextSibling;
  1282.                 }
  1283.             }
  1284.         }
  1285.     }
  1287.     // returns true if the two elements have at least 50% in common (common name & attributes)
  1288.     private bool GoForElementChange( XmlDiffElement sourceElement, XmlDiffElement targetElement ) {
  1289.         int identicalAttrCount = 0;
  1290.         int addedAttrCount = 0;
  1291.         int removedAttrCount = 0;
  1292.         int changedAttrCount = 0;
  1293.         bool bNameChange;
  1295.         bNameChange = ( sourceElement.LocalName != targetElement.LocalName );
  1297.         XmlDiffAttributeOrNamespace sourceAttr = sourceElement._attributes;
  1298.         XmlDiffAttributeOrNamespace targetAttr = targetElement._attributes;
  1299.         while ( sourceAttr != null && targetAttr != null ) {
  1300.             if ( sourceAttr.LocalName == targetAttr.LocalName ) {
  1301.                 if ( ( _xmlDiff.IgnorePrefixes || _xmlDiff.IgnoreNamespaces || sourceAttr.Prefix == targetAttr.Prefix ) &&
  1302.                      ( _xmlDiff.IgnoreNamespaces || sourceAttr.NamespaceURI == targetAttr.NamespaceURI ) ) {
  1303.                     if ( sourceAttr.Value == targetAttr.Value ) {
  1304.                         identicalAttrCount++;
  1305.                     }
  1306.                     else {
  1307.                         changedAttrCount++;
  1308.                     }
  1309.                 }
  1310.                 else {
  1311.                     changedAttrCount++;
  1312.                 }
  1313.                 sourceAttr = (XmlDiffAttributeOrNamespace)sourceAttr._nextSibling;
  1314.                 targetAttr = (XmlDiffAttributeOrNamespace)targetAttr._nextSibling;
  1315.             }
  1316.             else {
  1317.                 int compare = XmlDiffDocument.OrderAttributesOrNamespaces( sourceAttr, targetAttr );
  1318.                 if ( compare < 0 ) {
  1319.                     removedAttrCount++;
  1320.                     sourceAttr = (XmlDiffAttributeOrNamespace)sourceAttr._nextSibling;
  1321.                 }
  1322.                 else {
  1323.                     addedAttrCount++;
  1324.                     targetAttr = (XmlDiffAttributeOrNamespace)targetAttr._nextSibling;
  1325.                 }
  1326.             }
  1327.         }
  1329.         while ( sourceAttr != null ) {
  1330.             removedAttrCount++;
  1331.             sourceAttr = (XmlDiffAttributeOrNamespace)sourceAttr._nextSibling;
  1332.         }
  1334.         while ( targetAttr != null ) {
  1335.             addedAttrCount++;
  1336.             targetAttr = (XmlDiffAttributeOrNamespace)targetAttr._nextSibling;
  1337.         }
  1339.         if ( bNameChange ) {
  1340.             // total number of changes is less than 50%
  1341.             if ( removedAttrCount + addedAttrCount + changedAttrCount <= identicalAttrCount )
  1342.                 return true;
  1344.             return false;
  1345.         }
  1346.         else {
  1347.             // only added
  1348.             if ( removedAttrCount + changedAttrCount == 0 )
  1349.                 return true;
  1351.             // only removed
  1352.             if ( addedAttrCount + changedAttrCount == 0 )
  1353.                 return true;
  1355.             // no removed or added: 
  1356.             if ( removedAttrCount + addedAttrCount == 0 ) {
  1357.                 return true;
  1358.             }
  1360.             // total number of changes is less than 75% - or - 
  1361.             // no other sibling node
  1362.             if ( removedAttrCount + addedAttrCount + changedAttrCount <= identicalAttrCount * 3 ||
  1363.                 sourceElement._nextSibling == null )
  1364.                 return true;
  1366.             return false;
  1367.         }
  1368.     }
  1370.     private void WalkTreeOnRemoveNode( DiffgramParentOperation diffParent, XmlDiffNode sourceNode ) {
  1371.         bool bShrankNode = sourceNode is XmlDiffShrankNode;
  1373.         if ( sourceNode._bSomeDescendantMatches && !bShrankNode )
  1374.         {
  1375.             DiffgramOperation removeOp = GenerateDiffgramRemoveWhenDescendantMatches( (XmlDiffParentNode)sourceNode );
  1376.             diffParent.InsertAtEnd( removeOp );
  1377.         }
  1378.         else
  1379.         {
  1380. ulong opid = 0;
  1381.             // shrank node -> output as 'move' operation
  1382. if ( bShrankNode )
  1383. {
  1384. XmlDiffShrankNode shrankNode = (XmlDiffShrankNode) sourceNode;
  1385. if ( shrankNode.MoveOperationId == 0 )
  1386. shrankNode.MoveOperationId = GenerateOperationID( XmlDiffDescriptorType.Move );
  1387. opid = shrankNode.MoveOperationId;
  1388. }
  1390. if ( opid != 0 ||
  1391. !diffParent.MergeRemoveSubtreeAtEnd( sourceNode ) )
  1392. {
  1393. diffParent.InsertAtEnd( new DiffgramRemoveSubtrees( sourceNode, opid, !_xmlDiff.IgnoreChildOrder ) );
  1394. }
  1395.         }
  1396.     }
  1398.     private void WalkTreeOnAddNode( DiffgramParentOperation diffParent, XmlDiffNode targetNode, XmlDiffNode sourcePositionNode ) {
  1399.         bool bShrankNode = targetNode is XmlDiffShrankNode;
  1401.         if ( _bChildOrderSignificant ) {
  1402.             if ( sourcePositionNode != null ) {
  1403.                 diffParent.InsertAtEnd( new DiffgramPosition( sourcePositionNode ) );
  1404.             }
  1405.         }
  1406.         else {
  1407.             if ( diffParent._firstChildOp == null && diffParent is Diffgram ) {
  1408.                 diffParent.InsertAtEnd( new DiffgramPosition( sourcePositionNode ) );
  1409.             }
  1410.         }
  1411.         
  1412.         if ( targetNode._bSomeDescendantMatches && !bShrankNode ) {
  1413.             DiffgramOperation addOp = GenerateDiffgramAddWhenDescendantMatches( (XmlDiffParentNode)targetNode );
  1414.             diffParent.InsertAtEnd( addOp );
  1415.         }
  1416.         else {
  1417.             // shrank node -> output as 'move' operation
  1418.             if ( bShrankNode ) {
  1419.                 ulong opid = 0;
  1420.                 XmlDiffShrankNode shrankNode = (XmlDiffShrankNode) targetNode;
  1421.                 if ( shrankNode.MoveOperationId == 0 )
  1422.                     shrankNode.MoveOperationId = GenerateOperationID( XmlDiffDescriptorType.Move );
  1423.                 opid = shrankNode.MoveOperationId;
  1425.                 diffParent.InsertAtEnd( new DiffgramCopy( shrankNode.MatchingShrankNode, true, opid ) );
  1426.             }
  1427.             else {
  1428.                 switch ( targetNode.NodeType ) {
  1429.                     case XmlDiffNodeType.XmlDeclaration:
  1430.                     case XmlDiffNodeType.DocumentType:
  1431.                     case XmlDiffNodeType.EntityReference:
  1432.          diffParent.InsertAtEnd( new DiffgramAddNode( targetNode, 0 ) );
  1433.                         break;
  1434.                     default:
  1435.                         if ( !diffParent.MergeAddSubtreeAtEnd( targetNode ) ) {
  1436.                             diffParent.InsertAtEnd( new DiffgramAddSubtrees( targetNode, 0, !_xmlDiff.IgnoreChildOrder ) );
  1437.                         }
  1438.                         break;
  1439.                 }
  1440.             }
  1441.         }
  1442.     }
  1444.     private void WalkTreeOnChangeNode( DiffgramParentOperation diffParent, XmlDiffNode sourceNode, XmlDiffNode targetNode, XmlDiffOperation op ) {
  1445.         Debug.Assert( sourceNode.NodeType != XmlDiffNodeType.Element && targetNode.NodeType != XmlDiffNodeType.Element );
  1447.         DiffgramChangeNode changeOp = new DiffgramChangeNode( sourceNode, targetNode, op, 0 );
  1448.         if ( sourceNode.HasChildNodes || targetNode.HasChildNodes ) {
  1449.             WalkTreeGenerateDiffgramMatch( changeOp, (XmlDiffParentNode) sourceNode, (XmlDiffParentNode) targetNode );
  1450.         }
  1451.         diffParent.InsertAtEnd( changeOp );
  1452.     }
  1454.     private void WalkTreeOnChangeElement( DiffgramParentOperation diffParent, XmlDiffElement sourceElement, XmlDiffElement targetElement, XmlDiffOperation op ) {
  1456.         DiffgramParentOperation diffOp;
  1458.         if ( XmlDiff.IsChangeOperationOnAttributesOnly( op ) ) {
  1459.             diffOp = new DiffgramPosition( sourceElement );
  1460.         }
  1461.         else
  1462.         {
  1463.             ulong opid = 0;
  1464.             if ( !_xmlDiff.IgnoreNamespaces && sourceElement.LocalName == targetElement.LocalName)
  1465.             {
  1466.                 opid = GetNamespaceChangeOpid( sourceElement.NamespaceURI, sourceElement.Prefix,
  1467.                                                targetElement.NamespaceURI, targetElement.Prefix );
  1468.             }
  1470.             Debug.Assert( (int)op >= (int)XmlDiffOperation.ChangeElementName &&
  1471.                           (int)op <= (int)XmlDiffOperation.ChangeElementNameAndAttr3 );
  1473.             diffOp = new DiffgramChangeNode( sourceElement, targetElement, XmlDiffOperation.ChangeElementName, opid );
  1474.         }
  1476.         GenerateChangeDiffgramForAttributes( diffOp, sourceElement, targetElement );
  1478.         if ( sourceElement.HasChildNodes || targetElement.HasChildNodes ) {
  1479.             WalkTreeGenerateDiffgramMatch( diffOp, sourceElement, targetElement );
  1480.         }
  1482.         diffParent.InsertAtEnd( diffOp );
  1483.     }
  1485.     private void WalkTreeOnMatchNode( DiffgramParentOperation diffParent, XmlDiffNode sourceNode, XmlDiffNode targetNode, ref XmlDiffNode needPositionSourceNode ) {
  1486.         if ( sourceNode.HasChildNodes || targetNode.HasChildNodes ) {
  1487.             DiffgramPosition diffMatch = new DiffgramPosition( sourceNode, targetNode );
  1488.             WalkTreeGenerateDiffgramMatch( diffMatch, (XmlDiffParentNode)sourceNode, (XmlDiffParentNode)targetNode );
  1489.             diffParent.InsertAtEnd( diffMatch );
  1490.             needPositionSourceNode = null;
  1491.         }
  1492.         else {
  1493.             if ( sourceNode.NodeType == XmlDiffNodeType.ShrankNode ) {
  1494.                 needPositionSourceNode = ((XmlDiffShrankNode)sourceNode)._lastNode;
  1495.             }
  1496.             else {
  1497.                 needPositionSourceNode = sourceNode;
  1498.             }
  1499.         }
  1500.     }
  1502.     private bool ParentMatches( XmlDiffNode sourceNode, XmlDiffNode targetNode, DiffgramOperation diffParent ) {
  1503.         switch ( diffParent.Operation ) {
  1504.             case XmlDiffOperation.Match:
  1505.                 DiffgramPosition diffMatch = diffParent as DiffgramPosition;
  1506.                 if ( diffMatch != null ) {
  1507.                     return ( diffMatch._sourceNode == sourceNode._parent && 
  1508.                              diffMatch._targetNode == targetNode._parent );
  1509.                 }
  1510.                 return false;
  1511.             case XmlDiffOperation.Remove:
  1512.                 DiffgramRemoveNode diffRemove = diffParent as DiffgramRemoveNode;
  1513.                 if ( diffRemove != null && diffRemove._sourceNode == sourceNode._parent ) {
  1514.                     return ParentMatches( diffRemove._sourceNode, targetNode, diffParent._parent );
  1515.                 }
  1516.                 return false;
  1517.             case XmlDiffOperation.Add:
  1518.                 return false;
  1519.             default:
  1520.                 DiffgramChangeNode diffChange = diffParent as DiffgramChangeNode;
  1521.                 if ( diffChange != null ) {
  1522.                     return ( diffChange._sourceNode == sourceNode._parent &&
  1523.                              diffChange._targetNode == targetNode._parent );
  1524.                 }
  1525.                 return false;
  1526.         }
  1528.     }
  1529. }
  1530. }