Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

out_xupdate.cc

Go to the documentation of this file.
00001 /* ===========================================================================
00002  *        Filename:  out_xupdate.cc
00003  *     Description:  the "xupdate" output format
00004  * 
00005  *         Version:  $Rev: 6 $
00006  *         Changed:  $Date: 2005-05-10 15:55:44 -0700 (Di, 10 Mai 2005) $
00007  *         Licence:  GPL (read COPYING file for details)
00008  * 
00009  *          Author:  Erich Schubert (eS), erich@debian.org
00010  *                   Institut für Informatik, LMU München
00011  * ======================================================================== */
00012 #include <iostream>
00013 #include <sstream>
00014 #include "config.h"
00015 #include "doc.h"
00016 #include "diff.h"
00017 #include <libxml/tree.h>
00018 #include "util.h"
00019 #include "out_xupdate.h"
00020 #include "out_common.h"
00021 
00022 using namespace SSD;
00023 namespace SSD {
00024 
00025 #define NAMESPACE_XUPDATE (xmlChar*)"http://www.xmldb.org/xupdate"
00026 #define XUPDATE_VARIABLE  (xmlChar*)"variable"
00027 #define XUPDATE_VARNAME   (xmlChar*)"name"
00028 #define XUPDATE_VARSEL    (xmlChar*)"select"
00029 #define XUPDATE_REMOVE    (xmlChar*)"remove"
00030 #define XUPDATE_REMSEL    (xmlChar*)"select"
00031 #define XUPDATE_APPEND    (xmlChar*)"append"
00032 #define XUPDATE_APPSEL    (xmlChar*)"select"
00033 #define XUPDATE_INSERTA   (xmlChar*)"insert-after"
00034 #define XUPDATE_INSASEL   (xmlChar*)"select"
00035 #define XUPDATE_INSERTB   (xmlChar*)"insert-before"
00036 #define XUPDATE_INSBSEL   (xmlChar*)"select"
00037 #define XUPDATE_VALUE     (xmlChar*)"value-of"
00038 #define XUPDATE_VALUESEL  (xmlChar*)"select"
00039 #define XUPDATE_ELEMENT   (xmlChar*)"element"
00040 #define XUPDATE_ELEMNAME  (xmlChar*)"name"
00041 #define XUPDATE_TEXT      (xmlChar*)"text"
00042 
00043 #define DUMMY_TAG         (xmlChar*)"dummy"
00044 
00045 #define A_INSERTED   (xmlChar*)"a-ins"
00046 #define A_DELETED    (xmlChar*)"a-del"
00047 #define A_MOVED_AWAY (xmlChar*)"a-m-away"
00048 #define A_MOVED_HERE (xmlChar*)"a-m-here"
00049 #define A_SEPARATOR (xmlChar*)";"
00050 
00051 /* make an xpath describing the location of pos (helper) */
00052 void XUpdateWriter::makePathBuf(xmlBufferPtr buf, xmlNodePtr pos) {
00053         const xmlChar* label=NULL;
00054         int count=1;
00055         /* get node label or use text() */
00056         if (pos == (xmlNodePtr) pos->doc) {
00057                 label=BAD_CAST "";
00058         } else
00059         if (xmlNodeIsText(pos)) {
00060                 label = (const xmlChar*) "text()";
00061                 for (xmlNodePtr p = pos->prev; p; p=p->prev)
00062                         if (xmlNodeIsText(p)) count++;
00063         } else {
00064                 label = pos->name;
00065                 for (xmlNodePtr p = pos->prev; p; p=p->prev)
00066                         if (p->name && (strcmp((char*)label, (char*)p->name) == 0)) count++;
00067         }
00068 
00069         /* construct xpath */
00070         /* we are using two buffers here: in a stringstream we can add+convert numbers */
00071         ostringstream buffer;
00072         buffer << "/" << label << "[" << count << "]";
00073         /* we construct the buffer child-to-parent, thus use addhead */
00074         xmlBufferAddHead(buf, (xmlChar*) buffer.str().c_str(), buffer.str().length());
00075         /* ascend to parent */
00076         if (pos->parent && (pos->parent != (xmlNodePtr)pos->doc))
00077                 makePathBuf(buf, pos->parent);
00078 }
00079 
00080 /* make an xpath describing the location of pos */
00081 xmlChar* XUpdateWriter::makePath(xmlNodePtr pos) {
00082 #ifdef CAREFUL
00083         if (!pos) throw "XUpdateWrite::makePath called with NULL pos";
00084 #endif
00085         xmlBufferPtr buf = xmlBufferCreate();
00086 
00087         makePathBuf(buf, pos);
00088 
00089         xmlChar* result = (xmlChar*)strdup((char*)xmlBufferContent(buf));
00090         xmlBufferFree(buf);
00091         return result;
00092 }
00093 
00094 /* recursively initialize a map of nodes from one document to its cloned copy */
00095 void XUpdateWriter::initCloneMap(xmlNodePtr r1, xmlNodePtr r3) {
00096         /* insert nodes into hashmap */
00097         map_clone.insert(make_pair(r1,r3));
00098         map_clone_back.insert(make_pair(r3,r1));
00099 
00100         /* recurse into children */
00101         xmlNodePtr pos1 = r1->children;
00102         xmlNodePtr pos3 = r3->children;
00103         while (pos1 && pos3) {
00104                 initCloneMap(pos1, pos3);
00105                 pos1 = pos1->next;
00106                 pos3 = pos3->next;
00107         }
00108         /* FIXME: process attributes, ensure they have the same ordering */
00109 }
00110 
00111 
00112 #define INSERT_MODE_CHILD 1
00113 #define INSERT_MODE_FOSIB 2
00114 #define INSERT_MODE_PRSIB 3
00115 #define INSERT_MODE_APPEND 4
00116 
00117 /* print the command to store a subtree */
00118 xmlNodePtr XUpdateWriter::writeStoreSubtree(int num, const xmlChar* path) {
00119         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_VARIABLE);
00120         std::ostringstream label;
00121         label << "m" << num;
00122         xmlSetProp(cmd,XUPDATE_VARNAME,(xmlChar*) label.str().c_str());
00123         xmlSetProp(cmd,XUPDATE_VARSEL, path);
00124         xmlAddChild(output,cmd);
00125         xmlNodeAddContent(output,(xmlChar*)"\n");
00126         return cmd;
00127 }
00128 
00129 xmlNodePtr XUpdateWriter::writeDeleteSubtree(const xmlChar* path) {
00130         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_REMOVE);
00131         xmlSetProp(cmd,XUPDATE_REMSEL,path);
00132         xmlAddChild(output,cmd);
00133         xmlNodeAddContent(output,(xmlChar*)"\n");
00134         return cmd;
00135 }
00136 
00137 xmlNodePtr XUpdateWriter::writeAppend(const xmlChar* path) {
00138         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_APPEND);
00139         xmlSetProp(cmd,XUPDATE_APPSEL,path);
00140         xmlAddChild(output,cmd);
00141         xmlNodeAddContent(output,(xmlChar*)"\n");
00142         return cmd;
00143 }
00144 
00145 xmlNodePtr XUpdateWriter::writeInsertAfter(const xmlChar* path) {
00146         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_INSERTA);
00147         xmlSetProp(cmd,XUPDATE_INSASEL,path);
00148         xmlAddChild(output,cmd);
00149         xmlNodeAddContent(output,(xmlChar*)"\n");
00150         return cmd;
00151 }
00152 
00153 xmlNodePtr XUpdateWriter::writeInsertBefore(const xmlChar* path) {
00154         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_INSERTB);
00155         xmlSetProp(cmd,XUPDATE_INSBSEL,path);
00156         xmlAddChild(output,cmd);
00157         xmlNodeAddContent(output,(xmlChar*)"\n");
00158         return cmd;
00159 }
00160 
00161 xmlNodePtr XUpdateWriter::writeValueOf(xmlNodePtr where, const xmlChar* path) {
00162         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_VALUE);
00163         xmlSetProp(cmd,XUPDATE_VALUESEL,path);
00164         xmlAddChild(where,cmd);
00165 //      xmlNodeAddContent(where,(xmlChar*)"\n");
00166         return cmd;
00167 }
00168 
00169 xmlNodePtr XUpdateWriter::writeElement(xmlNodePtr where, const xmlChar* elem) {
00170         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_ELEMENT);
00171         xmlSetProp(cmd,XUPDATE_ELEMNAME,elem);
00172         xmlAddChild(where,cmd);
00173 //      xmlNodeAddContent(where,(xmlChar*)"\n");
00174         return cmd;
00175 }
00176 
00177 xmlNodePtr XUpdateWriter::writeText(xmlNodePtr where) {
00178         xmlNodePtr cmd = xmlNewNode(ns, XUPDATE_TEXT);
00179         xmlAddChild(where,cmd);
00180 //      xmlNodeAddContent(where,(xmlChar*)"\n");
00181         return cmd;
00182 }
00183 
00184 #define OUTPUT_NONE     0
00185 #define OUTPUT_FIRST    1
00186 #define OUTPUT_SECOND   2
00187 #define OUTPUT_BOTH     3
00188 
00189 /* make an insert command, dependant on the value of insert_mode */
00190 xmlNodePtr XUpdateWriter::doInsertCmd(xmlNodePtr insertpos, int insert_mode) {
00191         xmlNodePtr cmd;
00192         if (!insertpos) throw "XUpdateWrite::doInsertCmd called with NULL insertpos";
00193         if (insert_mode == INSERT_MODE_PRSIB) {
00194                 xmlChar* path = makePath(insertpos);
00195                 cmd = writeInsertBefore(path);
00196                 free(path);
00197         } else if (insert_mode == INSERT_MODE_FOSIB) {
00198                 xmlChar* path = makePath(insertpos);
00199                 cmd = writeInsertAfter(path);
00200                 free(path);
00201         } else if (insert_mode == INSERT_MODE_APPEND) {
00202                 xmlChar* path = makePath(insertpos);
00203                 cmd = writeAppend(path);
00204                 free(path);
00205         } else if (insert_mode == INSERT_MODE_CHILD) {
00206                 if (insertpos->children) {
00207                         xmlChar* path = makePath(insertpos->children);
00208                         cmd = writeInsertBefore(path);
00209                         free(path);
00210                 } else {
00211                         xmlChar* path = makePath(insertpos);
00212                         cmd = writeAppend(path);
00213                         free(path);
00214                 }
00215         } else throw "Undefined insert_mode";
00216         return cmd;
00217 }
00218 
00219 /* execute an insert command, dependant on the value of insert_mode */
00220 void XUpdateWriter::execInsert(xmlNodePtr insertpos, xmlNodePtr data, int insert_mode) {
00221         /* are we changing the root node? */
00222         if (insertpos == (xmlNodePtr) insertpos->doc) {
00223                 xmlDocSetRootElement(insertpos->doc,data);
00224         /* other insertion modes */
00225         } else if (insert_mode == INSERT_MODE_PRSIB) {
00226                 xmlAddPrevSibling(insertpos,data);
00227         } else if (insert_mode == INSERT_MODE_FOSIB) {
00228                 xmlAddNextSibling(insertpos,data);
00229         } else if (insert_mode == INSERT_MODE_APPEND) {
00230                 xmlAddChild(insertpos,data);
00231         } else if (insert_mode == INSERT_MODE_CHILD) {
00232                 if (insertpos->children) {
00233                         xmlAddPrevSibling(insertpos->children,data);
00234                 } else {
00235                         xmlAddChild(insertpos,data);
00236                 }
00237         } else throw "Undefined insert_mode";
00238 }
00239 
00240 /* try to delete a text node "out of sequence" */
00241 bool XUpdateWriter::tryDeleteTextNode(xmlNodePtr pos3) {
00242         if (!xmlNodeIsText(pos3)) return true;
00243         /* is this a node cloned from the second document? */
00244         if (map_clone_back.find(pos3) == map_clone_back.end()) return false;
00245         /* get same node in second document */
00246         xmlNodePtr pos2 = map_clone_back[pos3];
00247         /* check if we "know" this node */
00248         if (known.find(pos2) == known.end()) return false;
00249         /* find the node this will map to */
00250         if (map.find(pos2) == map.end()) {
00251                 xmlChar* path = makePath(pos3);
00252                 /* we need to store this value */
00253                 writeDeleteSubtree(path);
00254                 xmlUnlinkNode(pos3);
00255                 free(path);
00256                 known.erase(pos2);
00257                 return true;
00258         }
00259         return false;
00260 }
00261 
00262 /* insert a dummy node if needed */
00263 void XUpdateWriter::insertDummyIfNeededForInsert(xmlNodePtr &insertpos, int &insert_mode) {
00264         bool need_dummy = false;
00265         switch (insert_mode) {
00266                 case INSERT_MODE_FOSIB:
00267                 case INSERT_MODE_PRSIB:
00268                         if (insertpos->next || xmlNodeIsText(insertpos->next))
00269                                 if (!tryDeleteTextNode(insertpos->next)) need_dummy = true;
00270                         if (insertpos->prev || xmlNodeIsText(insertpos->prev))
00271                                 if (!tryDeleteTextNode(insertpos->prev)) need_dummy = true;
00272                 break;
00273                 case INSERT_MODE_CHILD:
00274                         if (insertpos->children)
00275                                 if (xmlNodeIsText(insertpos->children))
00276                                         if (!tryDeleteTextNode(insertpos->children))
00277                                                 need_dummy = true;
00278                 break;
00279                 case INSERT_MODE_APPEND:
00280                         if (insertpos->children) {
00281                                 xmlNodePtr iter = insertpos->children;
00282                                 while (iter->next) iter = iter->next;
00283                                 if (xmlNodeIsText(iter))
00284                                         if (!tryDeleteTextNode(iter))
00285                                                 need_dummy = true;
00286                         }
00287                 break;
00288                 default:
00289                         throw "Undefined insert_mode";
00290         }
00291         if (!need_dummy) return;
00292         
00293         xmlNodePtr cmd;
00294         cmd = doInsertCmd(insertpos,insert_mode);
00295         writeElement(cmd, DUMMY_TAG);
00296         xmlNodePtr dummy = xmlNewNode(NULL, DUMMY_TAG);
00297         execInsert(insertpos, dummy, insert_mode);
00298         dummy_nodes.insert(dummy);
00299         insertpos = dummy;
00300         if (insert_mode == INSERT_MODE_CHILD)  insert_mode = INSERT_MODE_PRSIB;
00301         if (insert_mode == INSERT_MODE_APPEND) insert_mode = INSERT_MODE_FOSIB;
00302 }
00303 
00304 void XUpdateWriter::insertDummyIfNeededForDelete(xmlNodePtr deletepos, xmlNodePtr& insertpos, int& insert_mode) {
00305         if (!deletepos->prev || !deletepos->next) return;
00306         if (xmlNodeIsText(deletepos->prev) && xmlNodeIsText(deletepos->next)) {
00307                 /* try to solve by deleting text nodes first */
00308                 if (tryDeleteTextNode(deletepos->prev)) return;
00309                 if (tryDeleteTextNode(deletepos->next)) return;
00310                 /* insert a dummy node */
00311                 xmlNodePtr cmd;
00312                 xmlChar* path = makePath(deletepos);
00313                 cmd = writeInsertAfter(path);
00314                 free(path);
00315                 writeElement(cmd, DUMMY_TAG);
00316                 xmlNodePtr dummy = xmlNewNode(NULL, DUMMY_TAG);
00317                 xmlAddNextSibling(deletepos,dummy);
00318                 dummy_nodes.insert(dummy);
00319 /*              insertpos = dummy;
00320                 insert_mode = INSERT_MODE_FOSIB;*/
00321         }
00322 }
00323 
00324 void XUpdateWriter::deleteDummyNodesRec(xmlNodePtr pos) {
00325         while (pos) {
00326                 xmlNodePtr next = pos->next;
00327                 if (dummy_nodes.find(pos) != dummy_nodes.end()) {
00328                         xmlChar* path = makePath(pos);
00329                         writeDeleteSubtree(path);
00330                         /* unlink and free the nodes */
00331                         xmlUnlinkNode(pos);
00332                         xmlFreeNode(pos);
00333                         free(path);
00334                 } else {
00335                         if (pos->children) deleteDummyNodesRec(pos->children);
00336                 }
00337                 pos = next;
00338         }
00339 }
00340 
00341 void XUpdateWriter::deleteDummyNodes(xmlNodePtr pos) {
00342         deleteDummyNodesRec(pos);
00343         dummy_nodes.clear();
00344 }
00345 
00346 // FIXME: i think i'll need special handling for the case of a nesting inversion
00347 // i.e. <a><b/></a> -> <b><a/></b> with additional changes
00348 void XUpdateWriter::recDiff(xmlNodePtr pos1, xmlNodePtr pos2, xmlNodePtr insertpos, xmlNodePtr addedpos, int output) {
00349         hash_map<xmlNodePtr, xmlNodePtr, hash<void*> >::iterator i;
00350         hash_map<xmlNodePtr, int,        hash<void*> >::iterator ix;
00351         int insert_mode = INSERT_MODE_CHILD;
00352         if (!pos1 && !pos2 && !insertpos) return;
00353 
00354         /* assure we have a useable inserting position */
00355         if (!insertpos) {
00356                 xmlNodePtr iter = pos1;
00357                 while (! (insertpos = map_clone[iter]) ) {
00358                         iter = iter->parent;
00359                         if (!iter) throw "iter got NULL, have no insert position - root node changed?";
00360                 }
00361         }
00362 
00363         /* for a good output we need the longest common subsequence at each level.
00364          * this is easier here, since each node can match only once, this
00365          * boils down to longest-increasing-subsequence */
00366         vector<pair<xmlNodePtr, xmlNodePtr> > lcs;
00367         {
00368                 vector<pair<xmlNodePtr, xmlNodePtr> > p1;
00369                 vector<xmlNodePtr> p2;
00370                 for (xmlNodePtr i=pos1; i; i=i->next) {
00371                         hash_map<xmlNodePtr, xmlNodePtr, hash<void*> >::iterator f = map.find(i);
00372                         if (f != map.end()) p1.push_back(make_pair(i,f->second));
00373                 }
00374                 for (xmlNodePtr i=pos2; i; i=i->next)
00375                         if (known.find(i) != known.end()) p2.push_back(i);
00376                 calcLIS(p1, p2, lcs);
00377         }
00378         vector<pair<xmlNodePtr, xmlNodePtr> >::iterator lcsi = lcs.begin();
00379 
00380         while (pos1 || pos2) {
00381                 /* Longest-Subsequence checkpoints */
00382                 xmlNodePtr check1 = NULL;
00383                 xmlNodePtr check2 = NULL;
00384                 if (lcsi != lcs.end()) {
00385                         check1 = lcsi->first;
00386                         check2 = lcsi->second;
00387                         lcsi++;
00388                 }
00389 
00390                 /* process nodes in first document until LIS point */
00391                 /* FIXME: new sequence needed:
00392                  * - Descend into nodes in first document if needed
00393                  * - Insert new nodes in second document
00394                  * - Delete nodes from first
00395                  * (this reduces amount of dummy nodes needed when in whitespace mode
00396                  */
00397                 while (pos1 && (pos1 != check1)) {
00398                         if (output & OUTPUT_FIRST) {
00399                                 /* ignored nodes are just dumped if applicable */
00400                                 if (known.find(pos1) == known.end()) {
00401                                         /* whitespace etc. in first document is ignored */
00402                                 } else {
00403                                         /* find clone position */
00404                                         xmlNodePtr clone = map_clone[pos1];
00405 
00406                                         i = map.find(pos1);
00407                                         if (i != map.end()) {
00408                                                 // FIXME: descent into attributes, too.
00409                                                 // FIXME: is this behaviour correct (i->second->children)?
00410                                                 recDiff(pos1->children, i->second->children, clone, NULL, output & ~OUTPUT_SECOND);
00411                                                 /* Nodes moved away */
00412 
00413                                                 ix = map_index.find(pos1);
00414                                                 if (ix == map_index.end()) {
00415 
00416                                                         int num = index_num++;
00417                                                         map_index.insert(make_pair(pos1, num));
00418                                                         map_index.insert(make_pair(i->second, num));
00419 
00420                                                         if ((pos1->parent == (xmlNodePtr)pos1->doc) || (map.find(pos1->parent) != map.end()))
00421                                                                 insertDummyIfNeededForDelete(clone, insertpos, insert_mode);
00422                                                         /* we need to store this value */
00423                                                         xmlChar* path = makePath(clone);
00424                                                         writeStoreSubtree(num, path);
00425                                                         /* FIXME: does the following part go here or outside? */
00426                                                         /* do delete when root node, or parent is not deleted as well */
00427                                                         if ((pos1->parent == (xmlNodePtr)pos1->doc) || (map.find(pos1->parent) != map.end())) {
00428                                                                 /* if needed, insert a dummy tag */
00429                                                                 writeDeleteSubtree(path);
00430                                                                 /* we can now unlink this subtree from the document */
00431                                                                 xmlUnlinkNode(clone);
00432                                                                 /* store it for later insertion */
00433                                                                 map_move_subtrees[num] = clone;
00434                                                         } else {
00435                                                                 map_move_subtrees[num] = xmlCopyNode(clone,1);
00436                                                                 insertpos = clone;
00437                                                                 insert_mode = INSERT_MODE_FOSIB;
00438                                                         }
00439                                                         free(path);
00440                                                 }
00441                                         } else {
00442                                                 // FIXME: descent into attributes, too.
00443                                                 // FIXME: is this descending behaviour correct?
00444                                                 recDiff(pos1->children, NULL, clone, NULL, output & ~OUTPUT_SECOND);
00445 
00446                                                 /* nodes removed altogether */
00447                                                 /* do delete when root node, or parent is not deleted as well */
00448                                                 if ((pos1->parent == (xmlNodePtr)pos1->doc) || (map.find(pos1->parent) != map.end())) {
00449                                                         insertDummyIfNeededForDelete(clone, insertpos, insert_mode);
00450                                                         xmlChar* path = makePath(clone);
00451                                                         writeDeleteSubtree(path);
00452                                                         /* unlink and free the nodes */
00453                                                         xmlUnlinkNode(clone);
00454                                                         xmlFreeNode(clone);
00455                                                         free(path);
00456                                                 }
00457                                         }
00458                                 }
00459                         }
00460                         pos1 = pos1->next;
00461                 }
00462                 
00463                 while (pos2 && (pos2 != check2)) {
00464                         if (output & OUTPUT_SECOND) {
00465                                 /* ignored nodes are just dumped if applicable */
00466                                 if (known.find(pos2) == known.end()) {
00467                                         /* ignore whitespace and similar nodes in second document */
00468                                         /* except when we are inserting subtrees or text would collapse */
00469                                         if (addedpos && !xmlNodeIsText(xmlGetLastChild(addedpos))) {
00470                                                 xmlNodePtr newt = xmlCopyNode(pos2,0);
00471                                                 xmlAddChild(addedpos,newt);
00472                                                 xmlNodePtr copy3 = xmlCopyNode(pos2,0);
00473                                                 execInsert(insertpos, copy3, insert_mode);
00474                                                 insertpos = copy3; insert_mode = INSERT_MODE_FOSIB;
00475                                         }
00476                                 } else {
00477                                         i = map.find(pos2);
00478                                         if (i != map.end()) {
00479                                                 /* Nodes moved here */
00480                                                 int num=-1;
00481                                                 ix = map_index.find(pos2);
00482                                                 if (ix == map_index.end()) {
00483                                                         xmlNodePtr clone = map_clone[i->second];
00484                                                         num = index_num++;
00485                                                         map_index.insert(make_pair(pos2, num));
00486                                                         map_index.insert(make_pair(i->second, num));
00487                                                         /* we have to select the other contents now, this is difficult, but in order to
00488                                                         * have a reasonable variable ordering and execution sequence we need to do
00489                                                         * it this way... */
00490                                                         // FIXME: descent into attributes, too.
00491                                                         // FIXME: is this behaviour correct (i->second->children)?
00492                                                         recDiff(i->second->children, pos2->children, clone, NULL, output & ~OUTPUT_SECOND);
00493                                                         insertDummyIfNeededForDelete(clone, insertpos, insert_mode);
00494                                                         xmlChar* path = makePath(clone);
00495                                                         /* we need to store this value */
00496                                                         writeStoreSubtree(num, path);
00497                                                         /* we can now delete this value */
00498                                                         writeDeleteSubtree(path);
00499                                                         free(path);
00500                                                         /* we can now unlink this subtree from the document */
00501                                                         xmlUnlinkNode(clone);
00502                                                         /* store it for later insertion */
00503                                                         map_move_subtrees[num] = clone;
00504                                                 } else {
00505                                                         num = ix->second;
00506                                                 }
00507 #ifdef CAREFUL
00508                                                 if (num == -1) throw "Didn't get a valid move operation number.";
00509 #endif
00510                                                 xmlNodePtr clone2 = map_move_subtrees[num];
00511                                                 if (xmlNodeIsText(clone2)) insertDummyIfNeededForInsert(insertpos, insert_mode);
00512                                                 /* we can insert the previously stored contents here */
00513                                                 xmlNodePtr cmd = doInsertCmd(insertpos, insert_mode);
00514                                                 /* add value-of selection for previous contents */
00515                                                 std::ostringstream label;
00516                                                 label << "$m" << num;
00517                                                 writeValueOf(cmd, (xmlChar*) label.str().c_str());
00518                                                 /* re-insert the subtree here */
00519                                                 execInsert(insertpos, clone2, insert_mode);
00520                                                 insertpos = clone2; insert_mode = INSERT_MODE_FOSIB;
00521                                                 //FIXME: handle attributes
00522                                                 recDiff(i->second->children, pos2->children, clone2, NULL, output & ~OUTPUT_FIRST);
00523                                         } else {
00524                                                 if (xmlNodeIsText(pos2)) insertDummyIfNeededForInsert(insertpos, insert_mode);
00525                                                 /* if the parent was inserted as well, we can just add the new node as child */
00526                                                 if (!(addedpos && !xmlNodeIsText(xmlGetLastChild(addedpos))) &&
00527                                                         ((pos2->parent == (xmlNodePtr)pos2->doc) || (map.find(pos2->parent) != map.end()))) {
00528                                                         /* we can insert the previously stored contents here */
00529                                                         xmlNodePtr cmd = doInsertCmd(insertpos, insert_mode);
00530                                                         xmlNodePtr was_added = NULL;
00531                                                         /* nodes inserted */
00532                                                         if (xmlNodeIsText(pos2)) {
00533                                                                 xmlNodePtr elem = writeText(cmd);
00534                                                                 was_added = xmlCopyNode(pos2,0);
00535                                                                 xmlAddChild(elem,was_added);
00536                                                         } else
00537                                                                 was_added = writeElement(cmd, pos2->name);
00538                                                         //xmlNodePtr copy = xmlCopyNode(pos2,0);
00539                                                         //xmlAddChild(cmd,copy);
00540                                                         //xmlNodeAddContent(cmd,(xmlChar*)"\n");
00541                                                         /* insert into reference tree */
00542                                                         xmlNodePtr copy3 = xmlCopyNode(pos2,0);
00543                                                         execInsert(insertpos,copy3,insert_mode);
00544                                                         insertpos = copy3; insert_mode = INSERT_MODE_FOSIB;
00545                                                         //FIXME: handle attributes
00546                                                         recDiff(NULL, pos2->children, copy3, was_added, output & ~OUTPUT_FIRST);
00547                                                 } else {
00548                                                         xmlNodePtr newt = xmlCopyNode(pos2,0);
00549                                                         xmlAddChild(addedpos,newt);
00550                                                         xmlNodePtr copy3 = xmlCopyNode(pos2,0);
00551                                                         execInsert(insertpos, copy3, insert_mode);
00552                                                         insertpos = copy3; insert_mode = INSERT_MODE_FOSIB;
00553                                                         //FIXME: handle attributes
00554                                                         recDiff(NULL, pos2->children, copy3, newt, output & ~OUTPUT_FIRST);
00555                                                 }
00556                                         }
00557                                 }
00558                         }
00559                         pos2 = pos2->next;
00560                 }
00561 
00562                 /* we now arrived at the LIS point */
00563                 if (pos1 && pos2) {
00564                         //xmlNodePtr copy = xmlCopyNode(pos2,0);
00565                         //xmlAddChild(diff,copy);
00566                         //attr_diff(copy, ns, pos1, pos2, map, known, output_only);
00567                         insertpos = map_clone[pos1];
00568                         insert_mode = INSERT_MODE_FOSIB;
00569                         recDiff(pos1->children, pos2->children, insertpos, NULL, output);
00570                         pos1 = pos1->next;
00571                         pos2 = pos2->next;
00572                 }
00573         }
00574 }
00575 
00576 XUpdateWriter::XUpdateWriter()
00577         : output(NULL), ns(NULL), map(), map_index(), index_num(0), map_move_subtrees(), known(), map_clone(), result(NULL) {
00578         result = xmlNewDoc((xmlChar*)"1.0");
00579 
00580         xmlNodePtr root = xmlNewNode(NULL,(xmlChar*)"modifications");
00581         xmlDocSetRootElement(result,root);
00582         xmlNodeAddContent(root,(xmlChar*)"\n");
00583         xmlSetProp(root,(xmlChar*)"version",(xmlChar*)"1.0");
00584         output=root;
00585 
00586         ns = xmlNewNs(root, NAMESPACE_XUPDATE,(xmlChar*)"xupdate");
00587         xmlSetNs(root,ns);
00588 }
00589 
00590 void XUpdateWriter::run(Doc& doc1, Doc& doc2, DiffDijkstra& diff) {
00591         /* build a map for lookups node-in-second -> node-in-first */
00592         for (NodeAssignments* iter = diff.result->ass; iter; iter = iter->next) {
00593                 if (iter->n1 && iter->n2) {
00594                         map.insert(make_pair((xmlNode*)iter->n1->data,(xmlNode*)iter->n2->data));
00595                         map.insert(make_pair((xmlNode*)iter->n2->data,(xmlNode*)iter->n1->data));
00596                 }
00597         }
00598 
00599         /* this only works because we know that sizeof(xmlNodePtr) == sizeof(void*) */
00600         set<xmlNodePtr>* k1 = (set<xmlNodePtr>*) &doc1.processed;
00601         set<xmlNodePtr>* k2 = (set<xmlNodePtr>*) &doc2.processed;
00602 
00603         set_union(k1->begin(), k1->end(), k2->begin(), k2->end(),
00604                         inserter(known, known.begin()));
00605 
00606         /* make a working copy of the first document for diff construction */
00607         xmlDocPtr doc3 = xmlNewDoc((xmlChar*)"1.0");
00608         xmlNodePtr doc3root = xmlCopyNode(xmlDocGetRootElement(doc1.getDOM()),1);
00609         xmlDocSetRootElement(doc3,doc3root);
00610         /* make a mapping of original nodes to cloned copies */
00611         initCloneMap(xmlDocGetRootElement(doc1.getDOM()),doc3root);
00612         
00613         recDiff(xmlDocGetRootElement(doc1.getDOM()), xmlDocGetRootElement(doc2.getDOM()), (xmlNodePtr)doc3, NULL, OUTPUT_BOTH);
00614 
00615         deleteDummyNodes(doc3root);
00616         /* we can destroy doc3 now */
00617 #if 1
00618         cout << "With the result document: " << endl;
00619         xmlDocDump(stdout,doc3);
00620 #endif
00621         xmlFreeDoc(doc3);
00622 }
00623 
00624 void XUpdateWriter::dump() {
00625         xmlDocDump(stdout,result);
00626 }
00627 
00628 XUpdateWriter::~XUpdateWriter() {
00629         xmlFreeDoc(result); result = NULL, output = NULL;
00630 }
00631 } // namespace SSD

Generated on Thu Aug 4 17:57:12 2005 for SSDDiff by  doxygen 1.4.3-20050530