#include "diff.h"
#include <error.h>
#include <filenamecat.h>
#include <setjmp.h>
#include <xalloc.h>
#include <dirent.h>
#include <stdlib.h>

/* Read the directory named by |dir| and store into |dirdata| a sorted
   vector of filenames for its contents.  |dir->desc == -1| means this
   directory is known to be nonexistent, so set |dirdata| to an empty
   vector.  Return -1 (setting |errno|) if error, 0 otherwise.  */

struct dirdata {
    size_t nnames;    /* Number of names.  */
    char const **names;    /* Sorted names of files in dir, followed by 0.  */
    char *data;    /* Allocated storage for file names.  */
};

static bool dir_loop(struct comparison const *, int);


/* Read a directory and get its vector of names.  */

static bool
dir_read(struct file_data const *dir, struct dirdata *dirdata) {
    register struct dirent *next;
    register size_t i;

    /* Address of block containing the files that are described.  */
    char const **names;

    /* Number of files in directory.  */
    size_t nnames;

    /* Allocated and used storage for file name data.  */
    char *data;
    size_t data_alloc, data_used;

    dirdata->names = 0;
    dirdata->data = 0;
    nnames = 0;
    data = 0;

    if (dir->desc != -1) {
        /* Open the directory and check for errors.  */
        register DIR *reading = opendir(dir->name);
        if (!reading)
            return false;

        /* Initialize the table of filenames.  */

        data_alloc = 512;
        data_used = 0;
        dirdata->data = data = xmalloc(data_alloc);

        /* Read the directory entries, and insert the subfiles
       into the |data| table.  */

        while ((errno = 0, (next = readdir(reading)) != 0)) {
            char *d_name = next->d_name;
            size_t d_size = strlen (next->d_name) + 1;

            /* Ignore "." and "..".  */
            if (d_name[0] == '.'
                && (d_name[1] == 0 || (d_name[1] == '.' && d_name[2] == 0)))
                continue;

            while (data_alloc < data_used + d_size) {
                if (PTRDIFF_MAX / 2 <= data_alloc)
                    xalloc_die();
                dirdata->data = data = xrealloc(data, data_alloc *= 2);
            }

            memcpy (data + data_used, d_name, d_size);
            data_used += d_size;
            nnames++;
        }
        if (errno) {
            int e = errno;
            closedir(reading);
            errno = e;
            return false;
        }
        if (closedir(reading) != 0)
            return false;
    }

    /* Create the |names| table from the |data| table.  */
    if (PTRDIFF_MAX / sizeof *names - 1 <= nnames)
        xalloc_die();
    dirdata->names = names = xmalloc((nnames + 1) * sizeof *names);
    dirdata->nnames = nnames;
    for (i = 0; i < nnames; i++) {
        names[i] = data;
        data += strlen(data) + 1;
    }
    names[nnames] = 0;
    return true;
}

/* Compare file names, returning a value compatible with strcmp.  */

#define compare_names strcmp

/* Compare names FILE1 and FILE2 when sorting a directory.  */

static int
compare_names_for_qsort(void const *file1, void const *file2) {
    char const *const *f1 = file1;
    char const *const *f2 = file2;
    char const *name1 = *f1;
    char const *name2 = *f2;
    return compare_names(name1, name2);
}

/* Compare the contents of two directories named in |cmp|.  This is a
   top-level routine; it does everything necessary for diff on two
   directories.

   |cmp->file[0].desc == -1| says directory |cmp->file[0]| doesn't
   exist, but pretend it is empty.  Likewise for |cmp->file[1]|.

   |handle_file| is a caller-provided subroutine called to handle each file.
   It gets three operands: |cmp|, name of file in dir 0, name of file in dir 1.
   These names are relative to the original working directory.

   For a file that appears in only one of the dirs, one of the name-args
   to |handle_file| is zero.

   Returns the maximum of all the values returned by |handle_file|,
   or |exit_trouble| if trouble is encountered in opening files.  */

int
diff_dirs(struct comparison const *cmp,
          int (*handle_file)(struct comparison const *,
                             char const *, char const *)) {
    struct dirdata dirdata[2];
    int volatile val = EXIT_SUCCESS;
    int i;

    if ((cmp->file[0].desc == -1 || dir_loop(cmp, 0))
        && (cmp->file[1].desc == -1 || dir_loop(cmp, 1))) {
        error(0, 0, "%s: recursive directory loop",
              cmp->file[cmp->file[0].desc == -1].name);
        return EXIT_TROUBLE;
    }

    /* Get contents of both dirs.  */
    for (i = 0; i < 2; i++)
        if (!dir_read(&cmp->file[i], &dirdata[i])) {
            perror_with_name(cmp->file[i].name);
            val = EXIT_TROUBLE;
        }

    if (val == EXIT_SUCCESS) {
        char const **volatile names[2];
        names[0] = dirdata[0].names;
        names[1] = dirdata[1].names;

        /* Sort the directories.  */
        for (i = 0; i < 2; i++)
            qsort(names[i], dirdata[i].nnames, sizeof *dirdata[i].names,
                  compare_names_for_qsort);

        /* If |-S name| was given, and this is the topmost level of
       comparison, ignore all file names less than the specified
       starting name.  */

        if (starting_file && !cmp->parent) {
            while (*names[0] && compare_names(*names[0], starting_file) < 0)
                names[0]++;
            while (*names[1] && compare_names(*names[1], starting_file) < 0)
                names[1]++;
        }

        /* Loop while files remain in one or both dirs.  */
        while (*names[0] || *names[1]) {
            /* Compare next name in dir 0 with next name in dir 1.  At
               the end of a dir, pretend the "next name" in that dir
               is very large.  */
            int nameorder = (!*names[0] ? 1 : !*names[1] ? -1
                                                         : compare_names(*names[0], *names[1]));
            int v1 = (*handle_file)(cmp,
                                    0 < nameorder ? 0 : *names[0]++,
                                    nameorder < 0 ? 0 : *names[1]++);
            if (val < v1)
                val = v1;
        }
    }

    for (i = 0; i < 2; i++) {
        free(dirdata[i].names);
        free(dirdata[i].data);
    }

    return val;
}

/* Return nonzero if $cmp$ is looping recursively in argument $i$.  */

static bool
dir_loop(struct comparison const *cmp, int i) {
    struct comparison const *p = cmp;
    while ((p = p->parent))
        if (0 < same_file (&p->file[i].stat, &cmp->file[i].stat))
            return true;
    return false;
}

/* Find a matching filename in a directory.  */

char *
find_dir_file_pathname(char const *dir, char const *file) {
    const char *match = file;
    return file_name_concat(dir, match, NULL);
}