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 #include <cassert>
  31
  32 #include "Diff.hh"
  33
  34 namespace GdomeSmartDOMExt
  35 {
  36
  37   Diff
  38   Diff::diff(const Document& dest, const Document& source, flatNodeEq flatEq)
  39   {
  40     assert(dest);
  41     assert(source);
  42     assert(flatEq);
  43
  44     return diff(dest.get_documentElement(), source.get_documentElement(), flatEq);
  45   }
  46
  47   Diff
  48   Diff::diff(const Element& dest, const Element& source, flatNodeEq flatEq)
  49   {
  50     assert(dest);
  51     assert(source);
  52     assert(flatEq);
  53
  54     DOMImplementation di;
  55     Document doc = di.createDocument(DDIFF_NS_URI, "diff:doc", DocumentType());
  56     Element root = doc.get_documentElement();
  57     root.setAttributeNS(XMLNS_NS_URI, "xmlns:diff", DDIFF_NS_URI);
  58
  59     Diff diff(dest, doc, flatEq);
  60     if (Node d = diff.diffNodes(dest, source)) root.appendChild(d);
  61     else root.appendChild(doc.createElementNS(DDIFF_NS_URI, "diff:same"));
  62
  63     return diff;
  64   }
  65
  66   struct NodeEqPredicate : std::binary_function<Node,Node,bool>
  67   {
  68     NodeEqPredicate(Diff::flatNodeEq e) : eq(e) { };
  69     bool operator()(const Node& n1, const Node& n2) const { return eq(n1, n2); };
  70
  71   private:
  72     Diff::flatNodeEq eq;
  73   };
  74
  75   std::vector<Node>
  76   collectProperAttributes(const Node& n)
  77   {
  78     assert(n);
  79     NamedNodeMap map = n.get_attributes();
  80     unsigned len = map.get_length();
  81
  82     std::vector<Node> res;
  83     res.reserve(len);
  84     for (unsigned i = 0; i < len; i++)
  85       {
  86         Node attr = map.item(i);
  87         assert(attr);
  88         if (attr.get_nodeName() != "xmlns" && attr.get_prefix() != "xmlns") res.push_back(attr);
  89       }
  90
  91     return res;
  92   }
  93
  94   bool
  95   Diff::defaultFlatNodeEq(const Node& n1, const Node& n2)
  96   {
  97     assert(n1);
  98     assert(n2);
  99
 100     unsigned nodeType = n1.get_nodeType();
 101     if (nodeType != n2.get_nodeType()) return false;
 102
 103     GdomeString ns1 = n1.get_namespaceURI();
 104     GdomeString ns2 = n2.get_namespaceURI();
 105     if (ns1 != ns2) return false;
 106
 107     switch (nodeType)
 108       {
 109       case Node::ATTRIBUTE_NODE:
 110         if (!ns1.null())
 111           {
 112             assert(!ns2.null());
 113             if (n1.get_localName() != n2.get_localName()) return false;
 114           }
 115         else
 116           {
 117             assert(ns2.null());
 118             if (n1.get_nodeName() != n2.get_nodeName()) return false;
 119           }
 120         // WARNING: fallback for checking node value
 121       case Node::TEXT_NODE:
 122       case Node::CDATA_SECTION_NODE:
 123         if (n1.get_nodeValue() != n2.get_nodeValue()) return false;
 124         return true;
 125       case Node::ELEMENT_NODE:
 126         {
 127           //cout << "comparing: " << n1.get_nodeName() << " ? " << n2.get_nodeName() << endl;
 128           if (!ns1.null())
 129             {
 130               assert(!ns2.null());
 131               if (n1.get_localName() != n2.get_localName()) return false;
 132             }
 133           else
 134             {
 135               assert(ns2.null());
 136               if (n1.get_nodeName() != n2.get_nodeName()) return false;
 137             }
 138 #if 1
 139           std::vector<Node> m1 = collectProperAttributes(n1);
 140           std::vector<Node> m2 = collectProperAttributes(n2);
 141           if (m1.size() != m2.size()) return false;
 142
 143           for (unsigned i = 0; i < m1.size(); i++)
 144             {
 145               std::vector<Node>::iterator p2 = std::find_if(m2.begin(), m2.end(), std::bind2nd(NodeEqPredicate(defaultFlatNodeEq), m1[i]));
 146               if (p2 == m2.end()) return false;
 147             }
 148 #endif
 149         }
 150         return true;
 151       default:
 152         return true;
 153       }
 154
 155   }
 156
 157   void
 158   Diff::sameChunk(const Node& res, unsigned long n) const
 159   {
 160     assert(n > 0);
 161     Element s = doc.createElementNS(DDIFF_NS_URI, "diff:same");
 162     if (n != 1)
 163       {
 164         std::ostringstream os;
 165         os << n;
 166         s.setAttribute("count", os.str());
 167       }
 168     res.appendChild(s);
 169   }
 170
 171   Node
 172   Diff::diffNodes(const Node& p1, const Node& p2) const
 173   {
 174     if (eq(p1, p2))
 175       {
 176         Element m = doc.createElementNS(DDIFF_NS_URI, "diff:merge");
 177         if (diffChildren(p1, p2, m)) return m;
 178         else return Node();
 179       }
 180     else
 181       {
 182         Element r = doc.createElementNS(DDIFF_NS_URI, "diff:replace");
 183         r.appendChild(doc.importNode(p2, true));
 184         return r;
 185       }
 186   }
 187
 188   bool
 189   Diff::diffChildren(const Node& n1, const Node& n2, const Node& res) const
 190   {
 191     assert(n1);
 192     assert(n2);
 193     assert(res);
 194
 195     Node p1 = n1.get_firstChild();
 196     Node p2 = n2.get_firstChild();
 197     bool same = true;
 198     unsigned nSame = 0;
 199     while (p1 && p2)
 200       {
 201         if (Node d = diffNodes(p1, p2))
 202           {
 203             same = false;
 204             if (nSame > 0)
 205               {
 206                 sameChunk(res, nSame);
 207                 nSame = 0;
 208               }
 209             res.appendChild(d);
 210           }
 211         else
 212           nSame++;
 213
 214         p1 = p1.get_nextSibling();
 215         p2 = p2.get_nextSibling();
 216       }
 217
 218     if (p1)
 219       {
 220         same = false;
 221         if (nSame > 0)
 222           {
 223             sameChunk(res, nSame);
 224             nSame = 0;
 225           }
 226
 227         unsigned nRemoved = 0;
 228         while (p1)
 229           {
 230             nRemoved++;
 231             p1 = p1.get_nextSibling();
 232           }
 233
 234         if (nRemoved > 0)
 235           {
 236             Element r = doc.createElementNS(DDIFF_NS_URI, "diff:remove");
 237             if (nRemoved > 1)
 238               {
 239                 std::ostringstream os;
 240                 os << nRemoved;
 241                 r.setAttribute("count", os.str());
 242               }
 243             res.appendChild(r);
 244           }
 245       }
 246
 247     if (p2)
 248       {
 249         same = false;
 250         if (nSame > 0)
 251           {
 252             sameChunk(res, nSame);
 253             nSame = 0;
 254           }
 255
 256         Element i = doc.createElementNS(DDIFF_NS_URI, "diff:insert");
 257         while (p2)
 258           {
 259             i.appendChild(doc.importNode(p2, true));
 260             p2 = p2.get_nextSibling();
 261           }
 262         res.appendChild(i);
 263       }
 264
 265     return !same;
 266   }
 267
 268   static Node
 269   getFirstElement(const Node& n)
 270   {
 271     Node p = n.get_firstChild();
 272     while (p && p.get_nodeType() != Node::ELEMENT_NODE)
 273       p = p.get_nextSibling();
 274     return p;
 275   }
 276
 277   static Node
 278   getNextElement(const Node& n)
 279   {
 280     Node p = n.get_nextSibling();
 281     while (p && p.get_nodeType() != Node::ELEMENT_NODE)
 282       p = p.get_nextSibling();
 283     return p;
 284   }
 285
 286   void
 287   Diff::patchRootNode(const Node& node, const Element& elem) const
 288   {
 289     GdomeString name = elem.get_localName();
 290     if (name == "same")
 291       {
 292         if (elem.hasAttribute("count"))
 293           {
 294             unsigned count;
 295             std::istringstream is(elem.getAttribute("count"));
 296             is >> count;
 297             assert(count == 1);
 298           }
 299       }
 300     else if (name == "replace")
 301       {
 302         Document d1 = node.get_ownerDocument();
 303         Node parent = node.get_parentNode();
 304         assert(parent);
 305 #if 0
 306         /* the following patch is because of gdome2 bug that prevents from
 307          * replacing the root element of a document.
 308          */
 309         assert(!node.get_previousSibling());
 310         assert(!node.get_nextSibling());
 311         parent.removeChild(node);
 312         parent.appendChild(d1.importNode(getFirstElement(elem), true));
 313 #endif
 314         parent.replaceChild(d1.importNode(getFirstElement(elem), true), node);
 315       }
 316     else if (name == "merge")
 317       patchChildren(node, elem);
 318     else
 319       assert(0);
 320   }
 321
 322   void
 323   Diff::patchChildren(const Node& n1, const Element& e2) const
 324   {
 325     Node p1 = n1.get_firstChild();
 326     Element p2 = getFirstElement(e2);
 327     while (p2)
 328       {
 329         GdomeString name = p2.get_localName();
 330         if (name == "same")
 331           {
 332             unsigned count = 1;
 333             if (p2.hasAttribute("count"))
 334               {
 335                 std::istringstream is(p2.getAttribute("count"));
 336                 is >> count;
 337               }
 338             while (count-- > 0)
 339               {
 340                 if (!p1) throw BADDiff("too few nodes in original document (same)");
 341                 p1 = p1.get_nextSibling();
 342               }
 343           }
 344         else if (name == "replace")
 345           {
 346             Document d1 = n1.get_ownerDocument();
 347             if (!p1) throw BADDiff("no node to replace in original document");
 348             Node next = p1.get_nextSibling();
 349             n1.replaceChild(d1.importNode(p2.get_firstChild(), true), p1);
 350             p1 = next;
 351           }
 352         else if (name == "insert")
 353           {
 354             Document d1 = n1.get_ownerDocument();
 355             for (Node i = p2.get_firstChild(); i; i = i.get_nextSibling())
 356               n1.insertBefore(d1.importNode(i, true), p1);
 357           }
 358         else if (name == "merge")
 359           {
 360             if (!p1) throw BADDiff("no node to merge in original document");
 361             patchChildren(p1, p2);
 362             p1 = p1.get_nextSibling();
 363           }
 364         else if (name == "remove")
 365           {
 366             unsigned count = 1;
 367             if (p2.hasAttribute("count"))
 368               {
 369                 std::istringstream is(p2.getAttribute("count"));
 370                 is >> count;
 371               }
 372             while (count-- > 0)
 373               {
 374                 if (!p1) throw BADDiff("too few nodes in original document (remove)");
 375                 Node next = p1.get_nextSibling();
 376                 n1.removeChild(p1);
 377                 p1 = next;
 378               }
 379           }
 380         else
 381           assert(0);
 382
 383         p2 = getNextElement(p2);
 384       }
 385   }
 386
 387   void
 388   Diff::patch() const
 389   {
 390     patchRootNode(dest, getFirstElement(doc.get_documentElement()));
 391   }
 392
 393 }