source: subversion/applications/utils/planetdiff/planetdiff.c @ 2605

Last change on this file since 2605 was 2406, checked in by jonb, 12 years ago

planetdiff & planetpatch tool - Allows incremental planet.osm updates using a custom XML diff format

File size: 17.2 KB
Line 
1/*
2#-----------------------------------------------------------------------------
3# planetdiff - Calculates the differences between 2 planet.osm
4# Roughly equivalent to 'diff' but optimised for planet.osm files
5#
6# Use:
7#      planetdiff planetA.osm planetB.osm > delta-AB.xml
8#
9#      planetpatch planetA.osm delta-AB.xml > planetB.osm
10#
11# Note: the planet.osm files must be UTF-8 clean
12# (e.g. run through UTF8sanitizer first)
13#
14# One of the input files may come from STDIN by specifying - as the filename
15#
16#-----------------------------------------------------------------------------
17# Written by Jon Burgess, Copyright 2007
18#
19# This program is free software; you can redistribute it and/or
20# modify it under the terms of the GNU General Public License
21# as published by the Free Software Foundation; either version 2
22# of the License, or (at your option) any later version.
23#
24# This program is distributed in the hope that it will be useful,
25# but WITHOUT ANY WARRANTY; without even the implied warranty of
26# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
27# GNU General Public License for more details.
28#
29# You should have received a copy of the GNU General Public License
30# along with this program; if not, write to the Free Software
31# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
32#-----------------------------------------------------------------------------
33*/
34
35/* TODO:
36 * - Empty!
37 *
38 * DONE:
39 * Escape key/values on output (&"'<>)
40 * write patch tool
41 * Error if file not in required sequence (node/segment/way with increasing ID)
42 * Warn if generator is not planet.rb since others tend to violate ordering above
43 * Generate run-time stats on stderr
44 * Allow direct reading of .gz and .bz2 files
45 * Perform UTF8sanitize on input
46 */
47
48#include <stdio.h>
49#include <unistd.h>
50#include <stdlib.h>
51#include <string.h>
52#include <assert.h>
53
54#include <libxml/xmlstring.h>
55#include <libxml/xmlreader.h>
56
57#include "keyvals.h"
58#include "sanitizer.h"
59
60/* Since {node,segment,way} elements are not nested we can
61 *  accumulates the attributes, tags and segments in global data.
62 * This is maintained independently for planetA and planetB
63 */
64enum type { invalid, node, segment, way, eof } current[2];
65static int osm_id[2];
66static struct keyval tags[2], segs[2], attrs[2];
67static xmlTextReaderPtr reader[2];
68static const char *files[2];
69
70
71
72static int compareTypeID() {
73    // Compare object types
74    if (current[0] < current[1])
75        return -1;
76    if (current[0] > current[1])
77        return +1;
78
79    if (osm_id[0] < osm_id[1])
80        return -1;
81    if (osm_id[0] > osm_id[1])
82        return +1;
83
84    return 0;
85}
86
87static int compareKeyval(struct keyval kv[2])
88{
89    struct keyval *p[2];
90    int r;
91
92    p[0] = kv[0].next;
93    p[1] = kv[1].next;
94#define END(x) (p[x] == &kv[x])
95
96    while(1) {
97        if (END(0) && END(1))
98            return 0;
99        if (END(0))
100            return -1;
101        if (END(1))
102            return +1;
103
104        r = strcmp(p[0]->key, p[1]->key);
105        if (r) return r;
106
107        r = strcmp(p[0]->value, p[1]->value);
108        if (r) return r;
109
110        p[0] = p[0]->next;
111        p[1] = p[1]->next;
112    }
113    return 0;
114}
115
116static int compareOther(void)
117{
118    int c;
119
120    c = compareKeyval(attrs);
121    if (c) return c;
122
123    c = compareKeyval(tags);
124    if (c) return c;
125
126    c = compareKeyval(segs);
127    if (c) return c;
128
129    return 0;
130}
131
132static void collectAttributes(int i)
133{
134    int ret;
135    const xmlChar *name, *value;
136    while ((ret = xmlTextReaderMoveToNextAttribute(reader[i])) == 1) {
137        name  = xmlTextReaderConstName(reader[i]);
138        value = xmlTextReaderConstValue(reader[i]);
139        addItem(&attrs[i], (char *)name, (char *)value, 0);
140        //fprintf(stderr, "%s = %s\n", (char *)name, (char *)value);
141    }
142    if (ret != 0) {
143        fprintf(stderr, "%s : failed to parse attributes\n", files[i]);
144        exit(1);
145    }
146}
147
148static void StartElement(int i, const xmlChar *name)
149{
150    xmlChar *xk, *xv, *xid, *xgen;
151    static int warn = 1;
152
153    if (xmlStrEqual(name, BAD_CAST "node")) {
154        current[i] = node;
155        collectAttributes(i);
156    } else if (xmlStrEqual(name, BAD_CAST "segment")) {
157        current[i] = segment;
158        collectAttributes(i);
159    } else if (xmlStrEqual(name, BAD_CAST "tag")) {
160        xk = xmlTextReaderGetAttribute(reader[i], BAD_CAST "k");
161        xv = xmlTextReaderGetAttribute(reader[i], BAD_CAST "v");
162        addItem(&tags[i], (char *)xk, (char *)xv, 0);
163        xmlFree(xk);
164        xmlFree(xv);
165    } else if (xmlStrEqual(name, BAD_CAST "way")) {
166        current[i] = way;
167        collectAttributes(i);
168    } else if (xmlStrEqual(name, BAD_CAST "seg")) {
169        xid  = xmlTextReaderGetAttribute(reader[i], BAD_CAST "id");
170        addItem(&segs[i], "id", (char *)xid, 0);
171        xmlFree(xid);
172    } else if (xmlStrEqual(name, BAD_CAST "osm")) {
173        if (warn) {
174            xgen = xmlTextReaderGetAttribute(reader[i], BAD_CAST "generator");
175            if (!xmlStrEqual(xgen, BAD_CAST "OpenStreetMap planet.rb")) {
176                fprintf(stderr, "Warning: The input file %s was generated by %s\n", files[i], (char *)xgen);
177                fprintf(stderr, "this tool relies on the planet.osm format of the format of the planet.osm file\n");
178                fprintf(stderr, "generated by planet.rb of planet.openstreetmap.org and may not work with other osm files.\n\n");
179                warn = 0;
180            }
181            xmlFree(xgen);
182        }
183    } else {
184        fprintf(stderr, "%s: Unknown element name: %s\n", __FUNCTION__, name);
185    }
186}
187
188static int EndElement(int i, const xmlChar *name)
189{
190    // Return 0 for closing tag of node/segment/way
191    int ret;
192    if (xmlStrEqual(name, BAD_CAST "node")) {
193        ret = 0;
194    } else if (xmlStrEqual(name, BAD_CAST "segment")) {
195        ret = 0;
196    } else if (xmlStrEqual(name, BAD_CAST "way")) {
197        ret = 0;
198    } else if (xmlStrEqual(name, BAD_CAST "tag")) {
199        ret = 1;
200    } else if (xmlStrEqual(name, BAD_CAST "seg")) {
201        ret = 1;
202    } else if (xmlStrEqual(name, BAD_CAST "osm")) {
203        ret = 1; // maybe should be 0
204    } else {
205        fprintf(stderr, "%s: Unknown element name: %s\n", __FUNCTION__, name);
206        ret = 1;
207    }
208    return ret;
209}
210
211// Process an XML node, returns 0 for the closing tag for a node/segment/way
212static int processNode(int i)
213{
214    int ret = 1;
215    int empty;
216    xmlChar *name = xmlTextReaderName(reader[i]);
217    if (name == NULL)
218        name = xmlStrdup(BAD_CAST "--");
219       
220    switch(xmlTextReaderNodeType(reader[i])) {
221        case XML_READER_TYPE_ELEMENT:
222            empty = xmlTextReaderIsEmptyElement(reader[i]);
223            StartElement(i, name);     
224            if (!empty)
225                break;
226            /* Drop through for self closing tags since these generate no end_element */
227        case XML_READER_TYPE_END_ELEMENT:
228            ret = EndElement(i, name);
229            break;
230        case XML_READER_TYPE_SIGNIFICANT_WHITESPACE:
231            /* Ignore */
232            break;
233        default:
234            fprintf(stderr, "Unknown node type %d\n", xmlTextReaderNodeType(reader[i]));
235            break;
236    }
237    xmlFree(name);
238    return ret;
239}
240
241static const char *getName(int i)
242{
243    switch (current[i]) {
244        case node: return "node";
245        case segment: return "segment";
246        case way: return "way";
247        case invalid: return "invalid";
248        default:
249            break;
250    }
251    fprintf(stderr, "Unhandled type %d\n", current[i]);
252    exit(5);
253}
254
255// Reads in a complete OSM object, e.g. <node> to <node/>
256static void getobject(int i)
257{
258    int ret = 1;
259    const char *id;
260    enum type last_type = current[i];
261    const char *last_name = getName(i);
262    int last_id = osm_id[i];
263    static int count;
264
265    // Delete data for previous object
266    resetList(&attrs[i]);
267    resetList(&segs[i]);
268    resetList(&tags[i]);
269
270    current[i] = eof;
271    if (!reader[i])
272        return; // EOF
273
274    while(ret == 1) {
275        ret = xmlTextReaderRead(reader[i]);
276        if (ret == 0) {
277            //fprintf(stderr, "EOF %s\n", files[i]);
278            xmlFreeTextReader(reader[i]);
279            reader[i] = NULL;
280            return;
281        }
282        if (ret != 1) {
283            fprintf(stderr, "Error parsing file %s\n", files[i]);
284            exit(3);
285        }
286
287        ret = processNode(i);
288    }
289    // Retrieve osm_id for node/segment/way
290    id = getItem(&attrs[i], "id");
291    osm_id[i] = id ? atoi(id) : 0;
292    //fprintf(stderr, "%d: object %d, id=%d\n", i, current[i], osm_id[i]);
293
294    // Perform sanity checking on element sequence. The output of planet.rb conforms to this and
295    // the current diff/patch algorithm relies on these properties.
296    if (current[i] < last_type) {
297        fprintf(stderr, "Error: <%s> seen after <%s>. The file must be strictly ordered node/segment/way.\n", getName(i), last_name);
298        fprintf(stderr, "The planet.osm generated by the planet export (planet.rb) is consistent with this.\n");
299        exit(8);
300    }
301    if ((current[i] == last_type) && (osm_id[i] < last_id)) {
302        fprintf(stderr, "Error: <%s id=%d> seen after <%s id=%d>. The IDs must be in increasing order.\n", getName(i), osm_id[i], getName(i), last_id);
303        fprintf(stderr, "The planet.osm generated by the planet export (planet.rb) is consistent with this.\n");
304        exit(9);
305    }
306
307    // Some run-time stats, only count first stream
308    if (i == 0) {
309        count++;
310        if (current[i] != last_type) {
311            count = 0;
312            fprintf(stderr, "\n");
313        }
314        if ((count % 10000) == 0)
315            fprintf(stderr, "\rProcessing: %s(%dk)", getName(i), count/1000);
316    }
317}
318
319
320static void displayNode(int i, const char *indent)
321{
322    struct keyval *p;
323
324    printf("%s<%s", indent,getName(i));
325
326    while ((p = popItem(&attrs[i])) != NULL) {
327        printf(" %s=\"%s\"", p->key, p->value);
328        freeItem(p);
329    }
330
331    if (listHasData(&tags[i]) || listHasData(&segs[i])) {
332        printf(">\n");
333
334        while ((p = popItem(&segs[i])) != NULL) {
335            printf("%s  <seg id=\"%s\" />\n", indent, p->value);
336            freeItem(p);
337        }
338        while ((p = popItem(&tags[i])) != NULL) {
339            printf("%s  <tag k=\"%s\" v=\"%s\" />\n", indent, p->key, p->value);
340            freeItem(p);
341        }
342        printf("%s</%s>\n", indent,getName(i));
343    } else {
344        printf("/>\n");
345    }
346}
347
348static void displayDiff(int i)
349{
350    const char *operation = i ? "add" : "delete";
351    printf("  <%s>\n", operation);
352    displayNode(i, "    ");
353    printf("  </%s>\n", operation);
354}
355
356static void displayPatch(int i)
357{
358    displayNode(i, "  ");
359}
360
361
362static void process(void)
363{
364    int c;
365
366    getobject(0);
367    getobject(1);
368
369    while (reader[0] || reader[1]) {
370        c = compareTypeID();
371        if (c == 0) {
372            // Matching object type and ID, generate diff if content differs
373            if (compareOther()) {
374                displayDiff(0);
375                displayDiff(1);
376            }
377            getobject(0);
378            getobject(1);
379        } else if (c < 0) {
380            // Object in stream 0 is missing in 1, generate diff to remove old content 0
381            displayDiff(0);
382            getobject(0);
383        } else {
384            // Object in stream 0 is ahead of 1, generate diff to add content in 1
385            displayDiff(1);
386            getobject(1);
387        }
388    }
389}
390
391
392
393static int diffFiles(void)
394{
395    int i;
396
397    for(i=0; i<2; i++) {
398        reader[i] = sanitizerOpen(files[i]);
399        if (!reader[i]) {
400            fprintf(stderr, "Unable to open %s\n", files[i]);
401            return 1;
402        }
403    }
404
405    printf("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
406    printf("<planetdiff version=\"0.1\" generator=\"OpenStreetMap planetdiff\" from=\"%s\" to=\"%s\">\n", files[0], files[1]);
407    process();
408    printf("</planetdiff>\n");
409
410    return 0;
411}
412
413
414static void applyPatch(int mode)
415{
416    int c;
417    //fprintf(stdout,"%s: %d id=%d\n", (mode > 0)? "add" : "delete", current[1], osm_id[1]);
418
419    // Stream input until we get to or pass the matching type+id
420    while ((c = compareTypeID()) < 0) {
421        if (current[0] != invalid)
422            displayPatch(0);
423        getobject(0);
424    }
425    if (mode == -1) {
426        if ((c == 0) && (compareOther() == 0)) {
427            // Perfect match, remove this from input by fetching next object
428            getobject(0);
429            return;
430        }
431        fprintf(stderr, "Error remove for <%s id=%d> does not match input file. %s\n",
432                getName(1), osm_id[1], (c==0)?"Object content differs.":"Object ID missing.");
433        exit(6);
434    } else if (mode == +1) {
435        if (c > 0) {
436            // Found next input following the insert, emit the new content but not input (yet)
437            displayPatch(1);
438            return;
439        }
440        fprintf(stderr, "Error adding <%s id=%d> input file already contains this object\n", getName(1), osm_id[1]);
441        exit(6);
442    }
443}
444
445static void processPatchNode(void)
446{
447    int i = 1; // Patch file is always stream 1
448    int empty;
449    int mode = 0; // -1 = remove, +1 = add;
450    xmlChar *name = xmlTextReaderName(reader[i]);
451    if (name == NULL)
452        name = xmlStrdup(BAD_CAST "--");
453       
454    switch(xmlTextReaderNodeType(reader[i])) {
455        case XML_READER_TYPE_ELEMENT:
456            empty = xmlTextReaderIsEmptyElement(reader[i]);
457            if (xmlStrEqual(name, BAD_CAST "add"))
458                mode = +1;
459            else if (xmlStrEqual(name, BAD_CAST "delete"))
460                mode = -1;
461            else if (xmlStrEqual(name, BAD_CAST "planetdiff")) {
462                mode = 0;
463                break;
464            } else {
465                fprintf(stderr, "Unexpected node: <%s>\n", (char *)name);
466                if (xmlStrEqual(name, BAD_CAST "osm"))
467                    fprintf(stderr, "It looks like %s is an osm file not a planetdiff\n", files[i]);
468                exit(1);
469            }
470            // Retrieve the object to add/remove from the patch file and apply
471            if (!empty) {
472                getobject(1);
473                applyPatch(mode);
474                break;
475            }
476            /* Drop through for self closing tags since these generate no end_element */
477        case XML_READER_TYPE_END_ELEMENT:
478            mode = 0;
479            break;
480        case XML_READER_TYPE_SIGNIFICANT_WHITESPACE:
481            /* Ignore */
482            break;
483        default:
484            fprintf(stderr, "Unknown node type %d\n", xmlTextReaderNodeType(reader[i]));
485            break;
486    }
487    xmlFree(name);
488}
489
490
491static int patchFiles(void)
492{
493    int ret = 0;
494    int i;
495    // files[0] = planet.osm (input)
496    // files[1] = delta.xml (patch)
497    for(i=0; i<2; i++) {
498        reader[i] = sanitizerOpen(files[i]);
499        if (!reader[i]) {
500            fprintf(stderr, "Unable to open %s\n", files[i]);
501            return 1;
502        }
503    }
504
505    printf("<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
506    printf("<osm version=\"0.3\" generator=\"OpenStreetMap planet.rb\">\n");
507    // Ensure generator string length matches original planet.rb
508    // to allow 'cmp -l' to be run on output to verify correctness
509    //printf("<osm version=\"0.3\" generator=\"OSM planetpatch tool---\">\n");
510
511    ret = xmlTextReaderRead(reader[1]);
512
513    while (ret == 1) {
514        processPatchNode();
515        ret = xmlTextReaderRead(reader[1]);
516    }
517
518    if (ret != 0) {
519        fprintf(stderr, "%s : failed to parse patch\n", files[1]);
520        return ret;
521    }
522
523    // Displaying any trailer from input
524    while ((current[0] != eof) && reader[0]) {
525        displayPatch(0);
526        getobject(0);
527    }
528
529    printf("</osm>\n");
530
531    xmlFreeTextReader(reader[0]);
532    xmlFreeTextReader(reader[1]);
533    return 0;
534}
535
536
537static void usageDiff(const char *arg0)
538{
539    fprintf(stderr, "Usage:\n\t%s planet1.osm planet2.osm > planet.diff\n\nGenerates patch-compatible difference file between the two input planet.osm files\n", arg0);
540    exit(1);
541}
542
543static int mainDiff(int argc, char *argv[], const char *name)
544{
545    int i;
546
547    if (argc != 3) {
548        usageDiff(name);
549        exit(1);
550    }
551
552    for (i=0; i<2; i++) {
553        files[i] = argv[i+1];
554        initList(&tags[i]);
555        initList(&segs[i]);
556        initList(&attrs[i]);
557    }
558
559    if (diffFiles() != 0)
560        exit(2);
561
562    return 0;
563}
564
565static void usagePatch(const char *arg0)
566{
567    fprintf(stderr, "Usage:\n\t%s planet.osm delta.xml > out.osm\n\n", arg0);
568    fprintf(stderr, "Applies the differences listed in delta.xml to the input planet.osm\n");
569    exit(1);
570}
571
572static int mainPatch(int argc, char *argv[], const char *name)
573{
574    int i;
575
576    if (argc != 3) {
577        usagePatch(name);
578        exit(1);
579    }
580
581    for (i=0; i<2; i++) {
582        files[i] = argv[i+1];
583        initList(&tags[i]);
584        initList(&segs[i]);
585        initList(&attrs[i]);
586    }
587
588    if (patchFiles() != 0)
589        exit(2);
590
591    return 0;
592}
593
594int main(int argc, char *argv[])
595{
596    int r;
597    const char *name;
598    LIBXML_TEST_VERSION
599
600    name = strrchr(argv[0], '/');
601
602    if (!name)
603        name = strrchr(argv[0], '\\');
604
605    if (name)
606        name++;
607    else
608        name = argv[0];
609
610    if (!strcmp(name, "planetdiff"))
611            r = mainDiff(argc, argv, name);
612    else if (!strcmp(name, "planetpatch"))
613            r = mainPatch(argc, argv, name);
614    else {
615        fprintf(stderr, "Usage error - should be called as planetdiff or planetpatch (not '%s')\n", name);
616        exit(1);
617    }
618
619    xmlCleanupParser();
620    xmlMemoryDump();
621    fprintf(stderr, "\n");
622    return r;
623}
Note: See TracBrowser for help on using the repository browser.