1 #include "diff.hh"
2 #include "xutil.hh"
3 #include <libxml/tree.h>
4 #include <sstream>
5 #include <vector>
6 #include <assert.h>
7
8 #if 0
9 #include <iostream>
10
11 #define TRACE(trace_arg) std::cerr << trace_arg << std::endl
12 #else
13 #define TRACE(trace_arg)
14 #endif
15
16 using std::string;
17 using std::stringstream;
18 using namespace xutil;
19
get_node_count(xmlNodePtr n)20 static int get_node_count(xmlNodePtr n)
21 {
22 int count = 1;
23
24 xmlNodePtr ch = n->children;
25 while (ch) {
26 count += get_node_count(ch);
27 ch = ch->next;
28 }
29
30 return count;
31 }
32
new_ns(xmlNodePtr n,const string & prefix,const string & url)33 static xmlNsPtr new_ns(xmlNodePtr n, const string &prefix, const string &url)
34 {
35 xmlNsPtr ns = xmlNewNs(n,
36 reinterpret_cast<const xmlChar *>(url.c_str()),
37 reinterpret_cast<const xmlChar *>(prefix.c_str()));
38 if (!ns) {
39 string s = "cannot create ";
40 s += prefix;
41 s += ':';
42 s += url;
43 throw s;
44 }
45
46 return ns;
47 }
48
new_node(const char * name)49 static xmlNodePtr new_node(const char *name)
50 {
51 xmlNodePtr n = xmlNewNode(0,
52 reinterpret_cast<const xmlChar *>(name));
53 if (!n) {
54 string s = "cannot create ";
55 s += name;
56 throw s;
57 }
58
59 return n;
60 }
61
prune(xmlNodePtr n)62 static void prune(xmlNodePtr n)
63 {
64 xmlNodePtr ch = n->children;
65 while (ch) {
66 remove_children(ch);
67 ch = ch->next;
68 }
69 }
70
get_children(xmlNodePtr n)71 static std::vector<xmlNodePtr> get_children(xmlNodePtr n)
72 {
73 std::vector<xmlNodePtr> out;
74 xmlNodePtr ch = n->children;
75 while (ch) {
76 out.push_back(ch);
77 ch = ch->next;
78 }
79
80 return out;
81 }
82
Diff(const std::string & nsprefix,const std::string & nsurl)83 Diff::Diff(const std::string &nsprefix, const std::string &nsurl):
84 Target(nsurl),
85 nsprefix(nsprefix),
86 dest(),
87 dest_ns(0),
88 dest_point(0)
89 {
90 }
91
get_ns_prefix() const92 string Diff::get_ns_prefix() const
93 {
94 return nsprefix;
95 }
96
get_dest()97 XDoc Diff::get_dest()
98 {
99 return dest;
100 }
101
diff_nodes(xmlNodePtr m,xmlNodePtr n)102 xmlDocPtr Diff::diff_nodes(xmlNodePtr m, xmlNodePtr n)
103 {
104 diff(m, n);
105
106 xmlNodePtr top = get_root_element(dest);
107 xmlNodePtr ch = top->children;
108 while (ch) {
109 unify_namespace(dest_ns, ch);
110 ch = ch->next;
111 }
112
113 return dest.yank();
114 }
115
diff(xmlNodePtr m,xmlNodePtr n)116 void Diff::diff(xmlNodePtr m, xmlNodePtr n)
117 {
118 if (!do_diff_nodes(m, n, true)) {
119 return;
120 }
121
122 XDoc wa_dest = dest;
123 xmlNsPtr wa_dest_ns = dest_ns;
124
125 dest_point = 0;
126 dest_ns = 0;
127 dest = XDoc();
128 do_diff_nodes(m, n, false);
129
130 if (get_node_count(get_root_element(wa_dest)) <
131 get_node_count(get_root_element(dest))) {
132 dest = wa_dest;
133 dest_ns = wa_dest_ns;
134 }
135 }
136
do_diff_nodes(xmlNodePtr m,xmlNodePtr n,bool use_upd_attr)137 bool Diff::do_diff_nodes(xmlNodePtr m, xmlNodePtr n, bool use_upd_attr)
138 {
139 bool has_upd_attr = false;
140
141 dest_point = new_node("diff");
142 dest_ns = new_ns(dest_point, nsprefix, get_ns_url());
143 xmlSetNs(dest_point, dest_ns);
144
145 xmlDocSetRootElement(dest, dest_point);
146
147 std::equal_to<xmlNodePtr> is_equal;
148 if (is_equal(m, n)) {
149 append_copy();
150 } else {
151 if (compare(m, n, false)) {
152 if (use_upd_attr && m->children && n->children) {
153 descend(m, n);
154
155 string old_name = get_node_name(m);
156 xmlSetNsProp(dest_point,
157 dest_ns,
158 reinterpret_cast<const xmlChar *>("update"),
159 reinterpret_cast<const xmlChar *>(old_name.c_str()));
160
161 // std::cerr << lcsimpl::flatten(dest_point) << std::endl;
162
163 has_upd_attr = true;
164 } else {
165 replace(m, n);
166 }
167 } else {
168 descend(m, n);
169 }
170 }
171
172 return has_upd_attr;
173 }
174
descend(xmlNodePtr m,xmlNodePtr n)175 void Diff::descend(xmlNodePtr m, xmlNodePtr n)
176 {
177 xmlNodePtr seq = import_tip(n);
178
179 append_child(dest_point, seq);
180 dest_point = seq;
181
182 std::vector<xmlNodePtr> a = get_children(m);
183 std::vector<xmlNodePtr> b = get_children(n);
184 traverse_balanced(a, b);
185
186 xmlNodePtr last = seq->last;
187 if (last &&
188 (get_node_name(last) == get_scoped_name("delete"))) {
189 prune(last);
190 }
191 }
192
replace(xmlNodePtr m,xmlNodePtr n)193 void Diff::replace(xmlNodePtr m, xmlNodePtr n)
194 {
195 xmlNodePtr del = new_dm_node("delete");
196 append_child(dest_point, del);
197
198 append_child(del, import_tip(m));
199 append_insert(n);
200 }
201
combine_pair(xmlNodePtr n,bool reverse)202 bool Diff::combine_pair(xmlNodePtr n, bool reverse)
203 {
204 TRACE(this << "->combine_pair(" << get_node_name(n) << ", " \
205 << reverse << ')');
206
207 assert(dest_point);
208
209 xmlNodePtr last = dest_point->last;
210 assert(last);
211
212 xmlNodePtr m = last->last;
213 assert(m);
214
215 if ((m->type != XML_ELEMENT_NODE) ||
216 (n->type != XML_ELEMENT_NODE)) {
217 return false;
218 }
219
220 if (reverse) {
221 std::swap(m, n);
222 }
223
224 Diff dm(nsprefix, get_ns_url());
225 dm.diff(m, n);
226 XDoc dom = dm.dest;
227 xmlNodePtr root = get_root_element(dom);
228 xmlNodePtr ch = root->children;
229 assert(ch);
230
231 xmlNodePtr moved = last->last;
232 if (!moved->prev) {
233 remove_child(dest_point, last);
234 } else {
235 remove_child(last, moved);
236 }
237
238 if (combine_first_child(ch, get_scoped_name("delete")) ||
239 combine_first_child(ch, get_scoped_name("insert"))) {
240 ch = ch->next;
241 }
242
243 while (ch) {
244 xmlNodePtr subtree = import_node(ch);
245 append_child(dest_point, subtree);
246
247 ch = ch->next;
248 }
249
250 return true;
251 }
252
combine_first_child(xmlNodePtr first_child,const std::string & checked_name)253 bool Diff::combine_first_child(xmlNodePtr first_child,
254 const std::string &checked_name)
255 {
256 xmlNodePtr last = dest_point->last;
257 if (!last) {
258 return false;
259 }
260
261 if ((get_node_name(last) != checked_name) ||
262 (get_node_name(first_child) != checked_name)) {
263 return false;
264 }
265
266 xmlNodePtr cnt = first_child->children;
267 while (cnt) {
268 append_child(last, import_node(cnt));
269 cnt = cnt->next;
270 }
271
272 return true;
273 }
274
append_insert(xmlNodePtr n)275 void Diff::append_insert(xmlNodePtr n)
276 {
277 xmlNodePtr ins = new_dm_node("insert");
278 append_child(dest_point, ins);
279 append_child(ins, import_node(n));
280 }
281
append_delete(xmlNodePtr n)282 void Diff::append_delete(xmlNodePtr n)
283 {
284 xmlNodePtr del = new_dm_node("delete");
285 append_child(dest_point, del);
286 append_child(del, import_node(n));
287 }
288
append_copy()289 void Diff::append_copy()
290 {
291 xmlNodePtr copy = new_dm_node("copy");
292 append_child(dest_point, copy);
293 xmlSetProp(copy,
294 reinterpret_cast<const xmlChar *>("count"),
295 reinterpret_cast<const xmlChar *>("1"));
296 }
297
on_match()298 void Diff::on_match()
299 {
300 assert(dest_point);
301
302 xmlNodePtr last = dest_point->last;
303 if (!last) {
304 append_copy();
305 } else if (get_node_name(last) != get_scoped_name("copy")) {
306 if (get_node_name(last) == get_scoped_name("delete")) {
307 prune(last);
308 }
309 append_copy();
310 } else {
311 int count = 1 + get_count_attr(last);
312 stringstream s;
313 s << count;
314 xmlSetProp(last,
315 reinterpret_cast<const xmlChar *>("count"),
316 reinterpret_cast<const xmlChar *>(s.str().c_str()));
317 }
318 }
319
on_insert(xmlNodePtr n)320 void Diff::on_insert(xmlNodePtr n)
321 {
322 TRACE(this << "->on_insert(" << get_node_name(n) << ')');
323 assert(n);
324
325 xmlNodePtr last = dest_point->last;
326 if (!last) {
327 append_insert(n);
328 } else if (get_node_name(last) == get_scoped_name("insert")) {
329 append_child(last, import_node(n));
330 } else if (get_node_name(last) != get_scoped_name("delete")) {
331 append_insert(n);
332 } else {
333 if (!combine_pair(n, false)) {
334 append_insert(n);
335 }
336 }
337 }
338
on_delete(xmlNodePtr n)339 void Diff::on_delete(xmlNodePtr n)
340 {
341 TRACE(this << "->on_delete(" << get_node_name(n) << ')');
342 assert(n);
343
344 xmlNodePtr last = dest_point->last;
345 if (!last) {
346 append_delete(n);
347 } else if (get_node_name(last) == get_scoped_name("delete")) {
348 prune(last);
349 append_child(last, import_node(n));
350 } else if (get_node_name(last) != get_scoped_name("insert")) {
351 append_delete(n);
352 } else {
353 if (!combine_pair(n, true)) {
354 append_delete(n);
355 }
356 }
357 }
358
new_dm_node(const char * name)359 xmlNodePtr Diff::new_dm_node(const char *name)
360 {
361 xmlNodePtr n = xmlNewNode(dest_ns,
362 reinterpret_cast<const xmlChar *>(name));
363 if (!n) {
364 string s = "cannot create ";
365 s += name;
366 throw s;
367 }
368
369 xmlSetTreeDoc(n, dest);
370
371 return n;
372 }
373