]> matita.cs.unibo.it Git - helm.git/blob - helm/software/DEVEL/mathml_editor/src/Diff.cc
reordered cases
[helm.git] / helm / software / 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 }