helm/DEVEL/mathml_editor/src/Diff.cc

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