/*-
 * Copyright (c) 2002 Poul-Henning Kamp
 * Copyright (c) 2002 Networks Associates Technology, Inc.
 * All rights reserved.
 *
 * This software was developed for the FreeBSD Project by Poul-Henning Kamp
 * and NAI Labs, the Security Research Division of Network Associates, Inc.
 * under DARPA/SPAWAR contract N66001-01-C-8035 ("CBOSS"), as part of the
 * DARPA CHATS research program.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The names of the authors may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <ctype.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <sys/queue.h>
#include <sys/sbuf.h>
#include <err.h>
#include <bsdxml.h>

FILE *fsubs;

struct node {
        LIST_HEAD(, node)       children;
        LIST_ENTRY(node)        siblings;
        struct node             *parent;
        const char              *name;
        struct sbuf             *cont;
        struct sbuf             *key;
        char                    *id;
        char                    *ref;
};

struct mytree {
        struct node             *top;
        struct node             *cur;
        int                     indent;
        int                     ignore;
};

struct ref {
        LIST_ENTRY(ref)         next;
        char                    *k1;
        char                    *k2;
};

LIST_HEAD(, ref)                refs = LIST_HEAD_INITIALIZER(refs);

static struct node *
new_node(void)
{
        struct node *np;

        np = calloc(1, sizeof *np);
        np->cont = sbuf_new_auto();
        sbuf_clear(np->cont);
        np->key = sbuf_new_auto();
        sbuf_clear(np->key);
        LIST_INIT(&np->children);
        return (np);
}

static void
indent(int n)
{

        printf("%*.*s", n, n, "");
}

static void
StartElement(void *userData, const char *name, const char **attr)
{
        struct mytree *mt;
        struct node *np;
        int i;

        mt = userData;
        if (!strcmp(name, "FreeBSD")) {
                mt->ignore = 1;
                return;
        }
        mt->ignore = 0;
        mt->indent += 2;
        np = new_node();
        for (i = 0; attr[i]; i += 2) {
                if (!strcmp(attr[i], "id"))
                        np->id = strdup(attr[i+1]);
                else if (!strcmp(attr[i], "ref"))
                        np->ref = strdup(attr[i+1]);
        }
        np->name = strdup(name);
        sbuf_cat(np->key, name);
        sbuf_cat(np->key, "::");
        np->parent = mt->cur;
        LIST_INSERT_HEAD(&mt->cur->children, np, siblings);
        mt->cur = np;
}

static void
EndElement(void *userData, const char *name __unused)
{
        struct mytree *mt;
        struct node *np;

        mt = userData;
        if (mt->ignore)
                return;

        mt->indent -= 2;
        sbuf_finish(mt->cur->cont);
        LIST_FOREACH(np, &mt->cur->children, siblings) {
                if (strcmp(np->name, "name"))
                        continue;
                sbuf_cat(mt->cur->key, sbuf_data(np->cont));
                break;
        }
        sbuf_finish(mt->cur->key);
        mt->cur = mt->cur->parent;
}

static void
CharData(void *userData , const XML_Char *s , int len)
{
        struct mytree *mt;
        const char *b, *e;

        mt = userData;
        if (mt->ignore)
                return;
        b = s;
        e = s + len - 1;
        while (isspace(*b) && b < e)
                b++;
        while (isspace(*e) && e > b)
                e--;
        if (e != b || *b)
                sbuf_bcat(mt->cur->cont, b, e - b + 1);
}

static struct mytree *
dofile(char *filename)
{
        XML_Parser parser;
        struct mytree *mt;
        struct stat st;
        int fd;
        char *p;
        int i;

        parser = XML_ParserCreate(NULL);
        mt = calloc(1, sizeof *mt);
        mt->top = new_node();
        mt->top->name = "(top)";
        mt->top->parent = mt->top;
        mt->cur = mt->top;
        sbuf_finish(mt->top->key);
        sbuf_finish(mt->top->cont);
        XML_SetUserData(parser, mt);
        XML_SetElementHandler(parser, StartElement, EndElement);
        XML_SetCharacterDataHandler(parser, CharData);
        fd = open(filename, O_RDONLY);
        if (fd < 0)
                err(1, filename);
        fstat(fd, &st);
        p = mmap(NULL, st.st_size, PROT_READ, MAP_NOCORE|MAP_PRIVATE, fd, 0);
        i = XML_Parse(parser, p, st.st_size, 1);
        if (i != 1)
                errx(1, "XML_Parse complained -> %d", i);
        munmap(p, st.st_size);
        close(fd);
        XML_ParserFree(parser);
        sbuf_finish(mt->top->cont);
        if (i)
                return (mt);
        else
                return (NULL);
}

static void
print_node(struct node *np)
{
        printf("\"%s\" -- \"%s\" -- \"%s\"", np->name, sbuf_data(np->cont), sbuf_data(np->key));
        if (np->id)
                printf(" id=\"%s\"", np->id);
        if (np->ref)
                printf(" ref=\"%s\"", np->ref);
        printf("\n");
}

static void
print_tree(struct node *np, int n)
{
        struct node *np1;

        indent(n); printf("%s id=%s ref=%s\n", np->name, np->id, np->ref);
        LIST_FOREACH(np1, &np->children, siblings)
                print_tree(np1, n + 2);
}

static void
sort_node(struct node *np)
{
        struct node *np1, *np2;
        int n;

        LIST_FOREACH(np1, &np->children, siblings)
                sort_node(np1);
        do {
                np1 = LIST_FIRST(&np->children);
                n = 0;
                for (;;) {
                        if (np1 == NULL)
                                return;
                        np2 = LIST_NEXT(np1, siblings);
                        if (np2 == NULL)
                                return;
                        if (strcmp(sbuf_data(np1->key), sbuf_data(np2->key)) > 0) {
                                LIST_REMOVE(np2, siblings);
                                LIST_INSERT_BEFORE(np1, np2, siblings);
                                n++;
                                break;
                        }
                        np1 = np2;
                }
        } while (n);
}

static int
refcmp(char *r1, char *r2)
{
        struct ref *r;

        LIST_FOREACH(r, &refs, next) {
                if (!strcmp(r1, r->k1))
                        return (strcmp(r2, r->k2));
        }
        r = calloc(1, sizeof(*r));
        r->k1 = strdup(r1);
        r->k2 = strdup(r2);
        LIST_INSERT_HEAD(&refs, r, next);
        if (fsubs != NULL) {
                fprintf(fsubs, "s/%s/%s/g\n", r1, r2);
                fflush(fsubs);
        }
        return (0);
}

static int compare_node2(struct node *n1, struct node *n2, int in);

static int
compare_node(struct node *n1, struct node *n2, int in)
{
        int i;
        struct node *n1a, *n2a;

        i = strcmp(n1->name, n2->name);
        if (i)
                return (i);
        if (n1->id && n2->id)
                i = refcmp(n1->id, n2->id);
        else if (n1->id || n2->id)
                i = -1;
        if (i)
                return (i);
        if (n1->ref && n2->ref)
                i = refcmp(n1->ref, n2->ref);
        else if (n1->ref || n2->ref)
                i = -1;
        if (i)
                return (i);
        if (!strcmp(n1->name, "ref"))
                i = refcmp(sbuf_data(n1->cont), sbuf_data(n2->cont));
        else
                i = strcmp(sbuf_data(n1->cont), sbuf_data(n2->cont));
        if (i)
                return (1);
        n1a = LIST_FIRST(&n1->children);
        n2a = LIST_FIRST(&n2->children);
        for (;;) {
                if (n1a == NULL && n2a == NULL)
                        return (0);
                if (n1a != NULL && n2a == NULL) {
                        printf("1>");
                        indent(in);
                        print_node(n1a);
                        printf("2>\n");
                        return (1);
                }
                if (n1a == NULL && n2a != NULL) {
                        printf("1>\n");
                        printf("2>");
                        indent(in);
                        print_node(n2a);
                        return (1);
                }
                i = compare_node2(n1a, n2a, in + 2);
                if (i)
                        return (1);
                n1a = LIST_NEXT(n1a, siblings);
                n2a = LIST_NEXT(n2a, siblings);
        }
        return (0);
}

static int
compare_node2(struct node *n1, struct node *n2, int in)
{
        int i;

        i = compare_node(n1, n2, in);
        if (i) {
                printf("1>");
                indent(in);
                print_node(n1);
                printf("2>");
                indent(in);
                print_node(n2);
        }
        return (i);
}



int
main(int argc, char **argv)
{
        struct mytree *t1, *t2;
        int i;

        fsubs = fopen("_.subs", "w");
        setbuf(stdout, NULL);
        setbuf(stderr, NULL);
        if (argc != 3)
                errx(1, "usage: %s file1 file2", argv[0]);

        t1 = dofile(argv[1]);
        if (t1 == NULL)
                errx(2, "XML parser error on file %s", argv[1]);
        sort_node(t1->top);
        t2 = dofile(argv[2]);
        if (t2 == NULL)
                errx(2, "XML parser error on file %s", argv[2]);
        sort_node(t2->top);
        i = compare_node(t1->top, t2->top, 0);
        return (i);
}