helm/DEVEL/mathml_editor/src/Diff.cc

   1 /* This file is part of EdiTeX, an editor of mathematical
   2  * expressions based on TeX syntax.
   3  *
   4  * Copyright (C) 2002-2003 Luca Padovani <lpadovan@cs.unibo.it>,
   5  *                    2003 Paolo Marinelli <pmarinel@cs.unibo.it>.
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21  * For more information, please visit the project's home page
  22  * http://helm.cs.unibo.it/editex/
  23  * or send an email to <lpadovan@cs.unibo.it>
  24  */
  25
  26 #include <sstream>
  27 #include <functional>
  28 #include <vector>
  29 #include <algorithm>
  30
  31 #include "Diff.hh"
  32
  33 namespace GdomeSmartDOMExt
  34 {
  35
  36   Diff
  37   Diff::diff(const Document& dest, const Document& source, flatNodeEq flatEq)
  38   {
  39     assert(dest);
  40     assert(source);
  41     assert(flatEq);
  42
  43     return diff(dest.get_documentElement(), source.get_documentElement(), flatEq);
  44   }
  45
  46   Diff
  47   Diff::diff(const Element& dest, const Element& source, flatNodeEq flatEq)
  48   {
  49     assert(dest);
  50     assert(source);
  51     assert(flatEq);
  52
  53     DOMImplementation di;
  54     Document doc = di.createDocument(DDIFF_NS_URI, "diff:doc", DocumentType());
  55     Element root = doc.get_documentElement();
  56     root.setAttributeNS(XMLNS_NS_URI, "xmlns:diff", DDIFF_NS_URI);
  57
  58     Diff diff(dest, doc, flatEq);
  59     if (Node d = diff.diffNodes(dest, source)) root.appendChild(d);
  60     else root.appendChild(doc.createElementNS(DDIFF_NS_URI, "diff:same"));
  61
  62     return diff;
  63   }
  64
  65   struct NodeEqPredicate : std::binary_function<Node,Node,bool>
  66   {
  67     NodeEqPredicate(Diff::flatNodeEq e) : eq(e) { };
  68     bool operator()(const Node& n1, const Node& n2) const { return eq(n1, n2); };
  69
  70   private:
  71     Diff::flatNodeEq eq;
  72   };
  73
  74   std::vector<Node>
  75   collectProperAttributes(const Node& n)
  76   {
  77     assert(n);
  78     NamedNodeMap map = n.get_attributes();
  79     unsigned len = map.get_length();
  80
  81     std::vector<Node> res;
  82     res.reserve(len);
  83     for (unsigned i = 0; i < len; i++)
  84       {
  85         Node attr = map.item(i);
  86         assert(attr);
  87         if (attr.get_nodeName() != "xmlns" && attr.get_prefix() != "xmlns") res.push_back(attr);
  88       }
  89
  90     return res;
  91   }
  92
  93   bool
  94   Diff::defaultFlatNodeEq(const Node& n1, const Node& n2)
  95   {
  96     assert(n1);
  97     assert(n2);
  98
  99     unsigned nodeType = n1.get_nodeType();
 100     if (nodeType != n2.get_nodeType()) return false;
 101
 102     GdomeString ns1 = n1.get_namespaceURI();
 103     GdomeString ns2 = n2.get_namespaceURI();
 104     if (ns1 != ns2) return false;
 105
 106     switch (nodeType)
 107       {
 108       case Node::ATTRIBUTE_NODE:
 109         if (!ns1.null())
 110           {
 111             assert(!ns2.null());
 112             if (n1.get_localName() != n2.get_localName()) return false;
 113           }
 114         else
 115           {
 116             assert(ns2.null());
 117             if (n1.get_nodeName() != n2.get_nodeName()) return false;
 118           }
 119         // WARNING: fallback for checking node value
 120       case Node::TEXT_NODE:
 121       case Node::CDATA_SECTION_NODE:
 122         if (n1.get_nodeValue() != n2.get_nodeValue()) return false;
 123         return true;
 124       case Node::ELEMENT_NODE:
 125         {
 126           //cout << "comparing: " << n1.get_nodeName() << " ? " << n2.get_nodeName() << endl;
 127           if (!ns1.null())
 128             {
 129               assert(!ns2.null());
 130               if (n1.get_localName() != n2.get_localName()) return false;
 131             }
 132           else
 133             {
 134               assert(ns2.null());
 135               if (n1.get_nodeName() != n2.get_nodeName()) return false;
 136             }
 137 #if 1
 138           std::vector<Node> m1 = collectProperAttributes(n1);
 139           std::vector<Node> m2 = collectProperAttributes(n2);
 140           if (m1.size() != m2.size()) return false;
 141
 142           for (unsigned i = 0; i < m1.size(); i++)
 143             {
 144               std::vector<Node>::iterator p2 = std::find_if(m2.begin(), m2.end(), std::bind2nd(NodeEqPredicate(defaultFlatNodeEq), m1[i]));
 145               if (p2 == m2.end()) return false;
 146             }
 147 #endif
 148         }
 149         return true;
 150       default:
 151         return true;
 152       }
 153
 154   }
 155
 156   void
 157   Diff::sameChunk(const Node& res, unsigned long n) const
 158   {
 159     assert(n > 0);
 160     Element s = doc.createElementNS(DDIFF_NS_URI, "diff:same");
 161     if (n != 1)
 162       {
 163         std::ostringstream os;
 164         os << n;
 165         s.setAttribute("count", os.str());
 166       }
 167     res.appendChild(s);
 168   }
 169
 170   Node
 171   Diff::diffNodes(const Node& p1, const Node& p2) const
 172   {
 173     if (eq(p1, p2))
 174       {
 175         Element m = doc.createElementNS(DDIFF_NS_URI, "diff:merge");
 176         if (diffChildren(p1, p2, m)) return m;
 177         else return Node();
 178       }
 179     else
 180       {
 181         Element r = doc.createElementNS(DDIFF_NS_URI, "diff:replace");
 182         r.appendChild(doc.importNode(p2, true));
 183         return r;
 184       }
 185   }
 186
 187   bool
 188   Diff::diffChildren(const Node& n1, const Node& n2, const Node& res) const
 189   {
 190     assert(n1);
 191     assert(n2);
 192     assert(res);
 193
 194     Node p1 = n1.get_firstChild();
 195     Node p2 = n2.get_firstChild();
 196     bool same = true;
 197     unsigned nSame = 0;
 198     while (p1 && p2)
 199       {
 200         if (Node d = diffNodes(p1, p2))
 201           {
 202             same = false;
 203             if (nSame > 0)
 204               {
 205                 sameChunk(res, nSame);
 206                 nSame = 0;
 207               }
 208             res.appendChild(d);
 209           }
 210         else
 211           nSame++;
 212
 213         p1 = p1.get_nextSibling();
 214         p2 = p2.get_nextSibling();
 215       }
 216
 217     if (p1)
 218       {
 219         same = false;
 220         if (nSame > 0)
 221           {
 222             sameChunk(res, nSame);
 223             nSame = 0;
 224           }
 225
 226         unsigned nRemoved = 0;
 227         while (p1)
 228           {
 229             nRemoved++;
 230             p1 = p1.get_nextSibling();
 231           }
 232
 233         if (nRemoved > 0)
 234           {
 235             Element r = doc.createElementNS(DDIFF_NS_URI, "diff:remove");
 236             if (nRemoved > 1)
 237               {
 238                 std::ostringstream os;
 239                 os << nRemoved;
 240                 r.setAttribute("count", os.str());
 241               }
 242             res.appendChild(r);
 243           }
 244       }
 245
 246     if (p2)
 247       {
 248         same = false;
 249         if (nSame > 0)
 250           {
 251             sameChunk(res, nSame);
 252             nSame = 0;
 253           }
 254
 255         Element i = doc.createElementNS(DDIFF_NS_URI, "diff:insert");
 256         while (p2)
 257           {
 258             i.appendChild(doc.importNode(p2, true));
 259             p2 = p2.get_nextSibling();
 260           }
 261         res.appendChild(i);
 262       }
 263
 264     return !same;
 265   }
 266
 267   static Node
 268   getFirstElement(const Node& n)
 269   {
 270     Node p = n.get_firstChild();
 271     while (p && p.get_nodeType() != Node::ELEMENT_NODE)
 272       p = p.get_nextSibling();
 273     return p;
 274   }
 275
 276   static Node
 277   getNextElement(const Node& n)
 278   {
 279     Node p = n.get_nextSibling();
 280     while (p && p.get_nodeType() != Node::ELEMENT_NODE)
 281       p = p.get_nextSibling();
 282     return p;
 283   }
 284
 285   void
 286   Diff::patchRootNode(const Node& node, const Element& elem) const
 287   {
 288     GdomeString name = elem.get_localName();
 289     if (name == "same")
 290       {
 291         if (elem.hasAttribute("count"))
 292           {
 293             unsigned count;
 294             std::istringstream is(elem.getAttribute("count"));
 295             is >> count;
 296             assert(count == 1);
 297           }
 298       }
 299     else if (name == "replace")
 300       {
 301         Document d1 = node.get_ownerDocument();
 302         Node parent = node.get_parentNode();
 303         assert(parent);
 304 #if 0
 305         /* the following patch is because of gdome2 bug that prevents from
 306          * replacing the root element of a document.
 307          */
 308         assert(!node.get_previousSibling());
 309         assert(!node.get_nextSibling());
 310         parent.removeChild(node);
 311         parent.appendChild(d1.importNode(getFirstElement(elem), true));
 312 #endif
 313         parent.replaceChild(d1.importNode(getFirstElement(elem), true), node);
 314       }
 315     else if (name == "merge")
 316       patchChildren(node, elem);
 317     else
 318       assert(0);
 319   }
 320
 321   void
 322   Diff::patchChildren(const Node& n1, const Element& e2) const
 323   {
 324     Node p1 = n1.get_firstChild();
 325     Element p2 = getFirstElement(e2);
 326     while (p2)
 327       {
 328         GdomeString name = p2.get_localName();
 329         if (name == "same")
 330           {
 331             unsigned count = 1;
 332             if (p2.hasAttribute("count"))
 333               {
 334                 std::istringstream is(p2.getAttribute("count"));
 335                 is >> count;
 336               }
 337             while (count-- > 0)
 338               {
 339                 if (!p1) throw BADDiff("too few nodes in original document (same)");
 340                 p1 = p1.get_nextSibling();
 341               }
 342           }
 343         else if (name == "replace")
 344           {
 345             Document d1 = n1.get_ownerDocument();
 346             if (!p1) throw BADDiff("no node to replace in original document");
 347             Node next = p1.get_nextSibling();
 348             n1.replaceChild(d1.importNode(p2.get_firstChild(), true), p1);
 349             p1 = next;
 350           }
 351         else if (name == "insert")
 352           {
 353             Document d1 = n1.get_ownerDocument();
 354             for (Node i = p2.get_firstChild(); i; i = i.get_nextSibling())
 355               n1.insertBefore(d1.importNode(i, true), p1);
 356           }
 357         else if (name == "merge")
 358           {
 359             if (!p1) throw BADDiff("no node to merge in original document");
 360             patchChildren(p1, p2);
 361             p1 = p1.get_nextSibling();
 362           }
 363         else if (name == "remove")
 364           {
 365             unsigned count = 1;
 366             if (p2.hasAttribute("count"))
 367               {
 368                 std::istringstream is(p2.getAttribute("count"));
 369                 is >> count;
 370               }
 371             while (count-- > 0)
 372               {
 373                 if (!p1) throw BADDiff("too few nodes in original document (remove)");
 374                 Node next = p1.get_nextSibling();
 375                 n1.removeChild(p1);
 376                 p1 = next;
 377               }
 378           }
 379         else
 380           assert(0);
 381
 382         p2 = getNextElement(p2);
 383       }
 384   }
 385
 386   void
 387   Diff::patch() const
 388   {
 389     patchRootNode(dest, getFirstElement(doc.get_documentElement()));
 390   }
 391
 392 }