#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>

#include <sys/resource.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/wait.h>

#include <readline/history.h>
#include <readline/readline.h>

#define LIST_BLOCK_SZ 4
#define MAX_ARGS 31
#define MAX_USER_COMMANDS 32
#define MAX_BG_CMDS 128

typedef char **Command;

struct backgroundCommand {
  pid_t pid;
  Command cmd;

  struct backgroundCommand *last;
  struct backgroundCommand *next;
};

struct backgroundCommand *createBgCommand(pid_t pid, Command cmd) {
  struct backgroundCommand *newCmd = (struct backgroundCommand *)malloc(sizeof(struct backgroundCommand));

  if (newCmd == NULL) {
    perror("Error allocating background command.");
    exit(1);
  }

  newCmd->pid = pid;
  newCmd->cmd = cmd;

  newCmd->next = NULL;
  newCmd->last = NULL;

  return newCmd;
}

void appendBgCommand(pid_t pid, Command cmd, struct backgroundCommand *root) {
  // Find tail of linked list
  while (root->next != NULL) {
    root = root->next;
  }

  struct backgroundCommand *newCmd = createBgCommand(pid, cmd);

  root->next = newCmd;
  newCmd->last = root;
}

struct backgroundCommand *removeBgCommand(struct backgroundCommand *cmd) {
  struct backgroundCommand *last = cmd->last;
  struct backgroundCommand *next = cmd->next;

  if (last != NULL) cmd->last->next = next;
  if (next != NULL) cmd->next->last = last;

  free(cmd);

  if (last == NULL) {
    return next;
  } else {
    while (1) {
      if (last->last == NULL) {
        return last;
      } else {
        last = last->last;
      }
    }
  }
}

void freeBackgroundCommands(struct backgroundCommand *root) {
  do {
    struct backgroundCommand *next = root->next;

    free(root);

    root = next;
  } while (root != NULL);
}

Command parseCommand(char *str) {
  Command cmd = (Command)calloc(LIST_BLOCK_SZ, sizeof(char *));

  if (cmd == NULL) {
    perror("Error allocating command while parsing.");
    exit(1);
  }

  char *tok = strtok(str, " ");
  size_t i = 0;
  while (tok != NULL) {
    // Append token to command
    cmd[i++] = tok;
    tok = strtok(NULL, " ");

    if (i % LIST_BLOCK_SZ == 0) {
      cmd = (Command)realloc(cmd, (i + LIST_BLOCK_SZ) * sizeof(char *));

      if (cmd == NULL) {
        perror("Error re-allocating background command.");
        exit(1);
      }
    }
  }

  // Terminate sequence with NULL
  cmd[i] = NULL;
  return cmd;
}

Command *newCommandList() {
  Command *list = (Command *)calloc(LIST_BLOCK_SZ, sizeof(Command));
  if (list == NULL) {
    perror("Error allocating command list.");
    exit(1);
  }
  return list;
}

Command *appendCommand(Command cmd, Command *cmdList, size_t cmdListLen) {
  cmdList[cmdListLen] = cmd;

  // Re-allocate list if needed (cmdListLen not updated from append)
  if (cmdListLen % LIST_BLOCK_SZ == (LIST_BLOCK_SZ - 1)) {
    Command *newCmd = realloc(cmdList, (cmdListLen + LIST_BLOCK_SZ) * sizeof(Command));

    if (newCmd == NULL) {
      perror("Error re-allocating command list while appending.");
      exit(1);
    }

    return newCmd;
  }

  return cmdList;
}

char *printCommand(Command cmd) {
  Command iCmd = cmd;
  do {
    printf("%s ", (*iCmd));
  } while (*(++iCmd) != NULL);
}

void freeCommand(Command cmd) {
  char *str = cmd[0];
  size_t i = 1;
  while (str != NULL) {
    free(str);
    str = cmd[i++];
  }

  free(cmd);
}

void freeCommandList(Command *cmdList, size_t len) {
  size_t i = len;
  while ((i--) != 0) {
    freeCommand(cmdList[i]);
  }
  free(cmdList);
}

int main(int argc, char **argv) {
  Command *userCommands = newCommandList();
  size_t userCommandsLen = 0;

  struct backgroundCommand *backgroundCmd = NULL;

  char basedir[256];
  getcwd(basedir, sizeof(basedir));

  while (1) {
    printf("== Midday Commander, v1 ===\n");
    printf("Enter a command:\n");
    printf("\t0. whoami\tPrints out the result of the whoami command.\n");
    printf("\t1. last\t\tPrints out the result of the last command.\n");
    printf("\t2. ls\t\tPrints out the result of a listing of a user-specified "
           "path.\n");

    size_t i = 0;
    for (; i < userCommandsLen; i++) {
      printf("\t%zu. ", i + 3);
      printCommand(userCommands[i]);
      printf("\t\tUser-provided command.\n");
    }

    printf("\ta. add command\tAdds a new command to the menu.\n");
    printf("\tc. change directory\tChanges process working directory.\n");
    printf("\te. exit\t\tLeave mid-day commander.\n");
    printf("\tp. pwd\tPrints\t the working directory.\n");

    // Get command via input
    char *input = readline("> ");
    printf("\n");

    // `readline` returns NULL if EOF is read on an empty line
    char firstChar;
    if (input == NULL) {
      firstChar = 'e';
    } else {
      firstChar = input[0];
    }

    // Check if any background process have finished
    pid_t lastPid;
    do {
      struct rusage usage;
      lastPid = wait3(NULL, WNOHANG, &usage);

      int i = 0;
      struct backgroundCommand *cmd = backgroundCmd;
      while (cmd != NULL) {
        i++;
        struct backgroundCommand *next = cmd->next;

        if (cmd->pid == lastPid) {
          printf("== Job Complete [%d] ==\n", i);
          printf("Process ID: %d\n", cmd->pid);
          printf("[ Output ]\n");

          // Get output file and print to stdout
          char filename[16];
          sprintf(filename, "%s/.%d_output", basedir, lastPid);
          FILE *chOutput = fopen(filename, "r");
          if (chOutput) {
            char c;
            while ((c = getc(chOutput)) != EOF)
              putchar(c);
            fclose(chOutput);

            // Remove file now that we've seen it
            remove(filename);
          }

          // Re-set root in case it changed
          backgroundCmd = removeBgCommand(cmd);
        }

        cmd = next;
      }
    } while (lastPid > 0);

    // Parse the input command
    Command cmd;
    switch (firstChar) {
    case 'a': // Add a user-defined command
      cmd = parseCommand(readline("Command to add: "));
      if (cmd[0] == NULL) {
        printf("Invalid command entered\n\n");
        continue;
      }

      appendCommand(cmd, userCommands, userCommandsLen++);
      printf("Okay, added with ID %zu\n\n", userCommandsLen + 2);
      continue;

    case 'c': { // Change Directory
      printf("== Change Directory ==\n");
      const char *dir = readline("Directory: ");
      chdir(dir);
      printf("\n");
      continue;
    }

    case 'e': // Exit program
      printf("Logging you out, commander.\n");
      return 0;

    case 'p': { // Print working directory
      printf("== Current Directory ==\n");
      char dir[256];
      getcwd(dir, sizeof(dir));
      printf("Directory: %s\n\n", dir);
      continue;
    }

    case 'r': { // Print all running processes
      printf("== Running Processes ==\n");
      struct backgroundCommand *cmd = backgroundCmd;
      while (cmd != NULL) {
        printf("[%d]  ", cmd->pid);
        printCommand(cmd->cmd);
        printf("\n");

        cmd = cmd->next;
      }

      printf("\n");

      continue;
    }

    // Input must be a number, and will execute a command
    default: {
      int selection = atoi(input);

      switch (selection) {
      case 0: // whoami command
        printf("== Who am I? ==\n");
        cmd = parseCommand(strdup("whoami"));
        break;

      case 1: // last command
        printf("== Last Logins ==\n");
        cmd = parseCommand(strdup("last"));
        break;

      case 2: { // ls command
        printf("== Directory Listing ==\n");
        char *tStr = strcat(strdup("ls "), readline("Arguments: "));
        tStr = strcat(tStr, " ");
        tStr = strcat(tStr, readline("Path: "));
        cmd = parseCommand(tStr);
        break;
      }

      default: { // User-defined command
        // Offset selection by 3 to take pre-defined commands into account
        size_t adjSelection = selection - 3;
        if (adjSelection >= userCommandsLen || adjSelection < 0) {
          printf("Not a valid command.\n");
          continue;
        }

        cmd = userCommands[adjSelection];
      }
      }
    }
    }

    // Find last element in command
    Command iCmd = cmd;
    while (*(++iCmd) != NULL);
    iCmd--;

    // Check if selected process is a background process
    int background = (**iCmd == '&');

    struct timeval beforeTime;
    gettimeofday(&beforeTime, NULL);

    // Print custom command's name
    if (!background && atoi(input) > 2) {
      printf("== ");
      printCommand(cmd);
      printf("==\n");
    }

    pid_t pid = fork();
    struct rusage usage;
    if (pid < 0) {
      perror("Error during fork()\n");
      exit(1);
    } else if (pid != 0) {
      if (background) {
        // Check if we've created a background cmd already
        // if not, then create a new background cmd.
        // Otherwise place a new background cmd in the linked list
        if (backgroundCmd == NULL) {
          backgroundCmd = createBgCommand(pid, cmd);
        } else {
          appendBgCommand(pid, cmd, backgroundCmd);
        }

        printf("[%d] Running ", pid);
        printCommand(cmd);
        printf("in background...\n\n");
      } else {
        wait3(NULL, 0, &usage);
      }
    } else if (pid == 0) {
      // If command is a background cmd...
      if (background) {
        // remove the & at the end
        *iCmd = NULL;

        // close stdout and output to a file
        close(STDOUT_FILENO);
        char filepath[16];
        sprintf(filepath, "%s/.%d_output", basedir, getpid());
        int redirect = open(filepath, O_CREAT|O_WRONLY|O_TRUNC, S_IRWXU);

        if (redirect == -1) {
          perror("Could not open output redirect file.");
          exit(1);
        }

        // Create grand-child process in order for us to time execution
        pid_t gcPID = fork();
        if (gcPID < 0) {
          perror("Error during gc fork().");
          exit(1);
        } else if (gcPID != 0) {
          wait(NULL);
        } else {
          // Run command
          int res = execvp(cmd[0], cmd);
          if (res == -1) {
            printf("Error: invalid command %s.\n", cmd[0]);
            exit(1);
          }
        }
      } else {
        // Run command
        int res = execvp(cmd[0], cmd);
        if (res == -1) {
          printf("Error: invalid command %s.\n", cmd[0]);
          exit(1);
        }
      }
    }

    // If running cmd is a background command, don't print stats
    if (background && pid != 0) continue;

    struct timeval afterTime;
    gettimeofday(&afterTime, NULL);

    int elapsedTime = (afterTime.tv_sec - beforeTime.tv_sec) * 1000 +
                      (afterTime.tv_usec - beforeTime.tv_usec) / 1000;

    printf("\n-- Statistics --\n");
    printf("Elapsed Time: %d ms\n", elapsedTime);
    printf("Page Faults: %ld\n", usage.ru_majflt);
    printf("Page Faults (reclaimed): %ld\n\n", usage.ru_minflt);

    // If we're a child process, we've done our job.
    if (pid == 0) return 0;
  }

  // Free allocated memory
  freeBackgroundCommands(backgroundCmd);
  freeCommandList(userCommands, userCommandsLen);


  return 0;
}