#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <fcntl.h>
#include <dirent.h>
#include <errno.h>
#include <unistd.h>
#include <assert.h>
#include <sys/stat.h>
#include <sys/types.h>
#include "options.h"
#include "string.h"
#include "tree.h"


static const char* describe_stat(mode_t mode) {
  if (S_ISREG(mode)) return "file";
  if (S_ISDIR(mode)) return "directory";
  if (S_ISCHR(mode)) return "character device";
  if (S_ISBLK(mode)) return "block device";
  if (S_ISFIFO(mode)) return "FIFO";
  if (S_ISLNK(mode)) return "symbolic link";
  if (S_ISSOCK(mode)) return "socket";
  return "?unknown";
}

static const char* describe_dirent(unsigned char type) {
  switch (type) {
    case DT_BLK: return "block device";
    case DT_CHR: return "character device";
    case DT_DIR: return "directory";
    case DT_FIFO: return "FIFO";
    case DT_LNK: return "symbolic link";
    case DT_REG: return "file";
    case DT_SOCK: return "socket";
    case DT_UNKNOWN: return "unknown directory entry";
    default: return "?unknown";
  }
}

static int sort_pairs__compar(const void *p1_, const void *p2_) {
  const struct tree_pair *p1 = p1_, *p2 = p2_;

  // directories go first
  if ((p1->sub != NULL) != (p2->sub != NULL))
    return p1->sub != NULL ? -1 : 1;

  // directories with more things in it go first
  if (p1->sub != NULL) {
    const size_t tot1 = p1->sub->total_files + p1->sub->total_dirs;
    const size_t tot2 = p2->sub->total_files + p2->sub->total_dirs;
    if (tot1 != tot2) return tot2 - tot1;
  }

  return strcmp(p1->name, p2->name);
}

static void sort_pairs(struct tree_pair *pairs, size_t num) {
  qsort(pairs, num, sizeof(struct tree_pair), sort_pairs__compar);
}

struct linked_dir_node {
  char *name;
  struct tree_node *sub;
  struct linked_dir_node *next;
};

// If this directory contained a cachetag, this_was_cache_dir is set to true
// and NULL is returned.
static struct tree_node* make_dir_tree(const struct options *opts, struct string *relpath, int dirfd, bool *this_was_cache_dir) {
  // fprintf(stderr, "make_dir_tree(%s)\n", string_read(*relpath));

  DIR *dir = fdopendir(dirfd);
  if (dir == NULL) {
    if (errno == EACCES) {
      fprintf(stderr, "Warning: permission denied (fdopendir): %s\n", string_read(*relpath));
      return tree_make(NULL, 0, 0);
    }
    perror("fdopendir");
    exit(1);
  }

  struct linked_dir_node *first = NULL;
  struct linked_dir_node *last = NULL;
  size_t num_dir_nodes = 0;

  size_t disk_size = 0;

  const size_t dirpathlen = relpath->len;

  while (true) {
    errno = 0;
    struct dirent *ent = readdir(dir);
    if (ent == NULL) {
      if (errno == 0) break;  // end of directory listing
      perror("readdir");
      exit(1);
    }

    if (strcmp(ent->d_name, ".") == 0 || strcmp(ent->d_name, "..") == 0) {
      continue;
    }

    for (size_t i = 0; i < opts->ncachetags; i++) {
      if (strcmp(ent->d_name, opts->cachetags[i]) == 0) {
        *this_was_cache_dir = true;
        while (first != NULL) {
          free(first->name);
          if (first->sub != NULL) tree_free(first->sub);
          struct linked_dir_node *next = first->next;
          free(first);
          first = next;
        }
        closedir(dir);
        return NULL;
      }
    }

    // Do the truncate here, not on loop continue, because there's many
    // continue points and I'd forget.
    string_truncate(relpath, dirpathlen);
    if (dirpathlen > 0) string_append(relpath, "/");
    string_append(relpath, ent->d_name);

    for (size_t i = 0; i < opts->nfilters; i++) {
      if (!filter_rule_allows(opts->filters[i], string_read(*relpath))) {
        if (opts->debug)
          fprintf(stderr, "Excluded: <%s>\n", string_read(*relpath));
        goto skip_this_dirent;
      }
    }

    struct stat st;
    bool have_st = false;
    bool is_dir;

    if (ent->d_type == DT_UNKNOWN) {
      int ret = fstatat(dirfd, ent->d_name, &st, 0);
      if (ret < 0) {
        if (errno == EACCES) {
          fprintf(stderr, "Warning: permission denied (fstatat): %s\n", string_read(*relpath));
          continue;
        }
        perror("fstatat");
        exit(1);
      }

      have_st = true;
      if (S_ISDIR(st.st_mode)) is_dir = true;
      else if (S_ISREG(st.st_mode)) is_dir = false;
      else {
        if (!S_ISLNK(st.st_mode))
          fprintf(stderr, "Warning: skipping %s: %s\n", describe_stat(st.st_mode), string_read(*relpath));
        continue;
      }
    } else if (ent->d_type == DT_REG) {
      is_dir = false;
    } else if (ent->d_type == DT_DIR) {
      is_dir = true;
    } else {
      if (ent->d_type != DT_LNK)
        fprintf(stderr, "Warning: skipping %s: %s\n", describe_dirent(ent->d_type), string_read(*relpath));
      continue;
    }

    struct tree_node *sub = NULL;

    if (is_dir) {
      int fd = openat(dirfd, ent->d_name, O_DIRECTORY);
      if (fd < 0) {
        if (errno == EACCES) {
          fprintf(stderr, "Warning: permission denied (openat): %s\n", string_read(*relpath));
          continue;
        }
        perror("openat");
        exit(1);
      }

      bool was_cache_dir = false;
      sub = make_dir_tree(opts, relpath, fd, &was_cache_dir);
      close(fd);

      if (was_cache_dir) { assert(sub == NULL); goto skip_this_dirent; }  // no need to free 'sub'
    } else {
      if (!have_st) {
        int ret = fstatat(dirfd, ent->d_name, &st, 0);
        if (ret < 0) {
          if (errno == EACCES) {
            fprintf(stderr, "Warning: permission denied (fstatat): %s\n", string_read(*relpath));
            continue;
          }
          perror("fstatat");
          exit(1);
        }
        have_st = true;
      }
      disk_size += (st.st_size + st.st_blksize - 1) / st.st_blksize * st.st_blksize;
    }

    struct linked_dir_node *lnode = malloc(sizeof(struct linked_dir_node));
    lnode->name = strdup(ent->d_name);
    lnode->sub = sub;
    lnode->next = NULL;

    if (last == NULL) first = last = lnode;
    else { last->next = lnode; last = lnode; }
    num_dir_nodes++;

  skip_this_dirent:
    ;
  }

  string_truncate(relpath, dirpathlen);

  if (last != NULL) disk_size += 4096;  // add 4K for a non-empty directory node

  closedir(dir);

  struct tree_pair *pairs = malloc(num_dir_nodes * sizeof(struct tree_pair));
  {
    struct linked_dir_node *lnode = first;
    for (size_t i = 0; i < num_dir_nodes; i++) {
      pairs[i].name = lnode->name;
      pairs[i].sub = lnode->sub;
      lnode = lnode->next;
    }
  }

  sort_pairs(pairs, num_dir_nodes);

  struct tree_node *result = tree_make(pairs, num_dir_nodes, disk_size);

  while (first != NULL) {
    free(first->name);
    struct linked_dir_node *next = first->next;
    free(first);
    first = next;
  }
  free(pairs);

  return result;
}

static struct tree_node* make_dir_tree_root(const struct options *opts, const char *rootpath, const char *treeroot) {
  // If the first character is a /, keep it
  size_t rootpath_len = strlen(rootpath);
  while (rootpath_len > 1 && rootpath[rootpath_len - 1] == '/') rootpath_len--;

  // But not in the tree root
  size_t treeroot_len = treeroot != NULL ? strlen(treeroot) : 0;
  while (treeroot_len > 0 && treeroot[treeroot_len - 1] == '/') treeroot_len--;

  if (treeroot_len > 0 && treeroot[0] == '/') {
    fprintf(stderr, "Tree root is not a relative path\n");
    exit(1);
  }

  char *pathbuf = malloc(rootpath_len + 1 + treeroot_len + 1);
  size_t pathbuf_len = rootpath_len;
  strcpy(pathbuf, rootpath);
  if (treeroot) {
    pathbuf[pathbuf_len++] = '/';
    strcpy(pathbuf + pathbuf_len, treeroot);
    pathbuf_len += treeroot_len;
  }

  if (opts->debug) {
    fprintf(stderr, "Expanding from path <%s>\n", pathbuf);
  }

  int fd = open(pathbuf, O_DIRECTORY);
  if (fd < 0) {
    perror("open");
    exit(1);
  }

  struct string s = string_make(treeroot_len > 0 ? pathbuf + rootpath_len+1 : "");

  if (opts->debug) {
    fprintf(stderr, "Virtual start path <%s>\n", string_read(s));
  }

  free(pathbuf);

  bool was_cache_dir = false;
  struct tree_node *tree = make_dir_tree(opts, &s, fd, &was_cache_dir);
  close(fd);

  string_free(s);

  if (was_cache_dir) {
    fprintf(stderr, "Error: Root is a cache directory (contains a cache tag)\n");
    exit(1);
  }

  return tree;
}

static void print_tree(struct tree_node *node, struct string *prefix, int maxdepth) {
  if (maxdepth <= 0) return;

  struct tree_iter iter = tree_iter_start(node);
  struct tree_pair pair;
  while (tree_iter_next(&iter, &pair)) {
    if (pair.sub == NULL) {
      // printf("%s- %s\n", string_read(*prefix), pair.name);
    } else {
      printf("%s- %s/: files=%zu dirs=%zu size=%zu\n",
          string_read(*prefix), pair.name,
          pair.sub->total_files, pair.sub->total_dirs, pair.sub->total_size);

      const size_t origlen = string_append(prefix, "  ");
      print_tree(pair.sub, prefix, maxdepth - 1);
      string_truncate(prefix, origlen);
    }
  }
}

int main(int argc, char **argv) {
  if (argc <= 1) {
    fprintf(stderr, "Usage: %s [options...] <root>\n", argv[0]);
    return 1;
  }

  struct options opts = parse_options(argc, argv);

  if (opts.debug) {
    for (size_t i = 0; i < opts.nfilters; i++) {
      fprintf(stderr, "FR: ");
      filter_rule_debugdump(stderr, opts.filters[i]);
    }
  }

  struct tree_node *root = make_dir_tree_root(&opts, opts.rootpath, opts.treeroot);

  printf("files=%zu dirs=%zu size=%zu\n",
      root->total_files, root->total_dirs, root->total_size);

  struct string prefix = string_make("");
  print_tree(root, &prefix, opts.print_depth);
  string_free(prefix);

  tree_free(root);
}