Task manager with dependencies

Question

todo(1) is a program that lists the next tasks in decreasing order of urgency (most urgent tasks first).
"Next" tasks are those which are not blocked by a task it depends that is still not set as done.

I think I'm using a convoluted solution, because I create five different data structures in the program.
First, I collect tasks in a hash table (1) and an unsorted list (2).
While I'm collecting tasks, I get its dependencies and build a graph of tasks (3).
Then, I free the hash table (I use it only to get the dependencies without having to loop over the unsorted list all the time).
Then, I iterate over the unsorted list of tasks to visit each node in the graph and create a topologically sorted list of tasks (4).
Then, I iterate over that sorted list and extract those tasks that are not blocked into an array (5) of unblocked tasks. I sort this array based on the urgency of the tasks.
Finally, I print that array.

To compute the urgency, I do the following:
I compute the difference of days between the deadline and today.
Then I compute the log2 of this difference.
Then I subtract the result by the priority (1 for A, 0 for B, -1 for C).
The result of the subtraction is the urgency. The lower the better.

Here's the manual with a example of usage:

TODO(1)                     General Commands Manual                    TODO(1)

NAME
       todo - print next tasks

SYNOPSIS
       todo [-dl] file...

DESCRIPTION
       todo reads files for tasks, one task per line; and writes to the
       standard output those tasks that should be done, and that are not
       blocked by other undone tasks.  The tasks are ordered in decrescend
       order of urgency (the most urgent task is the first listed).  If a
       hyphen (-) is provided as argument or the argument is absent, todo
       reads from the standard input.  The options are as follows:

       -d     Consider tasks whose deadline has already passed as done, even
              if they are not explicitly set as done.

       -l     Long format.  Display tasks with its internal name, priority and
              deadline.

       Each event must begin with an optional status.  Two status are
       possible: TODO (which defines a uncompleted task) or DONE (which
       defines a completed task).  If no status is supplied, it is considered
       as TODO.

       After the optional status comes the optional priority.  The priority is
       a single uppercase letter between parentheses.  The letter must be A, B
       or C.  The lower the letter, the higher the priority; so “A” is the
       higher priority.

       After the optional priority comes the obligatory task name.  The task
       name is a single alphanumeric word without spaces that names the task.
       The task name must be followed by a colon.

       After the task name comes the optional task description.  The task
       description spans from the space after the colon that ends the task
       name to the beginning of the first property.

       After the optional task description comes the properties.  Properties
       are a space-delimited list of name-value pairs separated by colon.  The
       following property names and their respective values are listed below.

       due    A property of the form due:YYYY-MM-DD specifies the deadline of
              the task.

       deps   A property of the form deps:dep1,dep2,…,depN specifies a comma-
              delimited list of tasks that this task depends on.

       If a task line ends in a backslash (\), the task continues in the next
       line.  If a line does not match the format of a task specification,
       that line is ignored and a warning is printed to stderr.

EXAMPLES
       Consider the following input.

              DONE graph:   (B) Learn graphs.
              TODO manual:  (C) Write manual for todo(1).
              TODO sort:    (B) Learn how to do topological sorting.    deps:graph
              TODO data:    (A) Implement data structures for tasks.
              TODO parser:  (B) Write code for parsing tasks.           deps:data
              TODO algor:   (A) Implement algorithm for sorting tasks.  deps:data,sort
              TODO todo:    (B) Write the todo(1) utility.              deps:parser,algor
              TODO release: (C) Release todo(1).                        deps:todo,manual

       Running todo with the option -l on this input would print the
       following:

              data:       (A) Implement data structures for tasks.
              sort:       (B) Learn how to do topological sorting.
              manual:     (C) Write manual for todo(1).

SEE ALSO
       calendar(1), schedule(1)

                                                                       TODO(1)

Here's the code:

#include <sys/time.h>
#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#define SECS_PER_DAY  ((time_t)(24 * 60 * 60))
#define DAYS_PER_WEEK 7
#define MIDDAY        12                /* 12:00 */
#define NHASH         128               /* size of hash table */
#define MULTIPLIER    31                /* multiplier for hash table */
#define NCOLS         10                /* number of collumns reserved for task name in long format */
#define TODO          "TODO"
#define DONE          "DONE"
#define PROP_DEPS     "deps"
#define PROP_DUE      "due"

/* task structure */
struct Task {
    struct Task *hnext;             /* pointer for hash table linked list */
    struct Task *unext;             /* pointer for unsorted linked list */
    struct Task *snext;             /* pointer for sorted linked list */
    struct Edge *deps;              /* linked list of dependency edges */
    time_t due;                     /* due date, at 12:00 */
    int pri;                        /* priority */
    int visited;                    /* whether node was visited while sorting */
    int done;                       /* whether task is marked as done */
    char *date;                     /* due date, in format YYYY-MM-DD*/
    char *name;                     /* task name */
    char *desc;                     /* task description */
};

/* dependency link */
struct Edge {
    struct Edge *next;              /* next edge on linked list */
    struct Task *to;                /* task the edge links to */
};

/* list and table of tasks */
struct Agenda {
    struct Task **htab;             /* hash table of tasks */
    struct Task **array;            /* array of sorted, unblocked tasks */
    struct Task *unsort;            /* head of unsorted list of tasks */
    struct Task *shead, *stail;     /* head and tail of sorted list of tasks */
    size_t nunblock;                /* number of unblocked tasks */
};

/* time for today, 12:00 */
static time_t today;

/* option flags */
static int dflag;                       /* whether to consider tasks with passed deadline as done */
static int lflag;                       /* whether to display tasks in long format */

/* show usage and exit */
static void
usage(void)
{
    (void)fprintf(stderr, "usage: todo [-ld] [file...]\n");
    exit(1);
}

/* call malloc checking for error */
static void *
emalloc(size_t size)
{
    void *p;

    if ((p = malloc(size)) == NULL)
        err(1, "malloc");
    return p;
}

/* call calloc checking for error */
static void *
ecalloc(size_t nmemb, size_t size)
{
    void *p;

    if ((p = calloc(nmemb, size)) == NULL)
        err(1, "calloc");
    return p;
}

/* call strdup checking for error */
static char *
estrdup(const char *s)
{
    char *t;

    if ((t = strdup(s)) == NULL)
        err(1, "strdup");
    return t;
}

/* get time for today, at 12:00 */
static time_t
gettoday(void)
{
    struct tm *tmorig;
    struct tm tm;
    time_t t;

    if ((t = time(NULL)) == -1)
        err(1, NULL);
    if ((tmorig = localtime(&t)) == NULL)
        err(1, NULL);
    tm = *tmorig;
    tm.tm_hour = MIDDAY;
    tm.tm_min = 0;
    tm.tm_sec = 0;
    tm.tm_isdst = -1;
    if ((t = mktime(&tm)) == -1)
        err(1, NULL);
    return t;
}

/* compute hash value of string */
static size_t
hash(const char *s)
{
    size_t h;
    unsigned char *p;

    h = 0;
    for (p = (unsigned char *)s; *p != '\0'; p++)
        h = MULTIPLIER * h + *p;
    return h % NHASH;
}

/* find name in agenda, creating if does not exist */
static struct Task *
lookup(struct Agenda *agenda, const char *name)
{
    size_t h;
    struct Task *p;

    h = hash(name);
    for (p = agenda->htab[h]; p != NULL; p = p->hnext)
        if (strcmp(name, p->name) == 0)
            return p;
    p = emalloc(sizeof(*p));
    p->name = estrdup(name);
    p->hnext = agenda->htab[h];
    p->unext = agenda->unsort;
    agenda->htab[h] = p;
    agenda->unsort = p;
    return p;
}

/* create agenda and hash table */
static struct Agenda *
newagenda(void)
{
    struct Agenda *agenda;

    agenda = ecalloc(1, sizeof(*agenda));
    agenda->htab = ecalloc(NHASH, sizeof(*(agenda->htab)));
    return agenda;
}

/* add dependencies to task; we change s */
static void
adddeps(struct Agenda *agenda, struct Task *task, char *s)
{
    struct Task *tmp;
    struct Edge *edge;
    char *t;

    for (t = strtok(s, ","); t != NULL; t = strtok(NULL, ",")) {
        tmp = lookup(agenda, t);
        edge = emalloc(sizeof(*edge));
        edge->next = task->deps;
        edge->to = tmp;
        task->deps = edge;
    }
}

/* add deadline to task */
static void
adddue(struct Task *task, char *s)
{
    struct tm *tmorig;
    struct tm tm;
    time_t t;
    char *ep;

    if ((tmorig = localtime(&today)) == NULL) {
        warn(NULL);
        return;
    }
    tm = *tmorig;
    ep = strptime(s, "%Y-%m-%d", &tm);
    if (ep == NULL || *ep != '\0') {
        errno = EINVAL;
        warn("%s", s);
        return;
    }
    tm.tm_hour = MIDDAY;
    tm.tm_min = 0;
    tm.tm_sec = 0;
    tm.tm_isdst = -1;
    if ((t = mktime(&tm)) == -1) {
        warn(NULL);
        return;
    }
    task->date = estrdup(s);
    task->due = t;
    if (dflag && task->due < today) {
        task->done = 1;
    }
}

/* parse s for a new task and add it into agenda; we change s */
static void
addtask(struct Agenda *agenda, char *s)
{
    struct Task *task;
    size_t len;
    int done;
    char *name, *prop, *val;
    char *t, *end, *colon;
    int pri;

    while (isspace(*(unsigned char *)s))
        s++;
    done = 0;
    if (strncmp(s, TODO, sizeof(TODO) - 1) == 0) {
        s += sizeof(TODO) - 1;
    } else if (strncmp(s, DONE, sizeof(DONE) - 1) == 0) {
        done = 1;
        s += sizeof(DONE) - 1;
    }
    while (isspace(*(unsigned char *)s))
        s++;
    name = NULL;
    for (t = s; *t != '\0' && !isspace(*(unsigned char *)t); t++) {
        if (*t == ':') {
            name = s;
            *t = '\0';
            s = t + 1;
            break;
        }
    }
    if (name == NULL)
        return;
    while (isspace(*(unsigned char *)s))
        s++;
    pri = 0;
    if (s[0] == '(' && s[1] >= 'A' && s[1] <= 'C' && s[2] == ')') {
        switch (s[1]) {
        case 'A':
            pri = +1;
            break;
        default:
            pri = 0;
            break;
        case 'C':
            pri = -1;
            break;
        }
        s += 3;
    }
    task = lookup(agenda, name);
    task->pri = pri;
    task->done = done;
    while (isspace(*(unsigned char *)s))
        s++;
    len = strlen(s);
    for (t = &s[len - 1]; t >= s; t--) {
        colon = NULL;
        while (t >= s && isspace(*(unsigned char *)t))
            t--;
        end = t + 1;
        while (t >= s && !isspace(*(unsigned char *)t)) {
            if (*t == ':') {
                colon = t;
                *colon = '\0';
            }
            t--;
        }
        if (colon) {
            *t = '\0';
            *end = '\0';
            prop = t + 1;
            val = colon + 1;
            if (strcmp(prop, PROP_DUE) == 0) {
                adddue(task, val);
            } else if (strcmp(prop, PROP_DEPS) == 0) {
                adddeps(agenda, task, val);
            } else {
                warnx("unknown property \"%s\"", prop);
            }
        } else {
            break;
        }
    }
    len = strlen(s);
    for (t = &s[len - 1]; isspace(*(unsigned char *)t) && t >= s; t--)
        *t = '\0';
    free(task->desc);
    task->desc = estrdup(s);
}

/* read tasks from fp into agenda */
static void
readtasks(FILE *fp, struct Agenda *agenda)
{
    char buf[BUFSIZ];

    while (fgets(buf, sizeof(buf), fp) != NULL) {
        addtask(agenda, buf);
    }
}

/* visit task and their dependencies */
static void
visittask(struct Agenda *agenda, struct Task *task)
{
    struct Edge *edge;

    if (task->visited > 1)
        return;
    if (task->visited == 1)
        errx(1, "cyclic dependency between tasks");
    task->visited = 1;
    for (edge = task->deps; edge != NULL; edge = edge->next)
        visittask(agenda, edge->to);
    task->visited = 2;
    if (agenda->shead == NULL)
        agenda->shead = task;
    if (agenda->stail != NULL)
        agenda->stail->snext = task;
    agenda->stail = task;
}

/* compare tasks */
static int
comparetask(const void *a, const void *b)
{
    struct Task *taska, *taskb;
    time_t timea, timeb;
    time_t tmpa, tmpb;

    taska = *(struct Task **)a;
    taskb = *(struct Task **)b;
    tmpa = (taska->due != 0) ? (taska->due - today) / SECS_PER_DAY : DAYS_PER_WEEK;
    tmpb = (taskb->due != 0) ? (taskb->due - today) / SECS_PER_DAY : DAYS_PER_WEEK;
    timea = timeb = 0;
    if (tmpa < 0) {
        tmpa = -tmpa;
        while (tmpa >>= 1) {
            --timea;
        }
    } else {
        while (tmpa >>= 1) {
            ++timea;
        }
    }
    if (tmpb < 0) {
        tmpb = -tmpb;
        while (tmpb >>= 1) {
            --timeb;
        }
    } else {
        while (tmpb >>= 1) {
            ++timeb;
        }
    }
    timea -= taska->pri;
    timeb -= taskb->pri;
    if (timea < timeb)
        return -1;
    if (timea > timeb)
        return +1;
    return 0;
}

/* perform topological sort on agenda */
static void
sorttasks(struct Agenda *agenda)
{
    struct Task *task;
    struct Edge *edge;
    size_t ntasks;
    int cont;

    free(agenda->htab);
    ntasks = 0;
    for (task = agenda->unsort; task != NULL; task = task->unext) {
        if (!task->visited)
            visittask(agenda, task);
        ntasks++;
    }
    agenda->array = ecalloc(ntasks, sizeof(*agenda->array));
    for (task = agenda->shead; task != NULL; task = task->snext) {
        if (task->done)
            continue;
        if (task->deps != NULL) {
            cont = 0;
            for (edge = task->deps; edge != NULL; edge = edge->next) {
                if (!edge->to->done) {
                    cont = 1;
                    break;
                }
            }
            if (cont) {
                continue;
            }
        }
        agenda->array[agenda->nunblock++] = task;
    }
    qsort(agenda->array, agenda->nunblock, sizeof(*agenda->array), comparetask);
}

/* print sorted tasks */
static void
printtasks(struct Agenda *agenda)
{
    struct Task *task;
    size_t i;
    int n;

    for (i = 0; i < agenda->nunblock; i++) {
        task = agenda->array[i];
        if (lflag) {
            n = printf("%s", task->name);
            n = (n > 0 && n < NCOLS) ? NCOLS - n : 0;
            (void)printf(":%*c (%c) %s", n, ' ', (task->pri < 0 ? 'C' : (task->pri > 0 ? 'A' : 'B')), task->desc);
            if (task->date != NULL) {
                (void)printf(" due:%s", task->date);
            }
        } else {
            (void)printf("%s", task->desc);
        }
        printf("\n");
    }
}

/* free agenda and its tasks */
static void
freeagenda(struct Agenda *agenda)
{
    struct Task *task, *ttmp;
    struct Edge *edge, *etmp;

    for (task = agenda->unsort; task != NULL; ) {
        for (edge = task->deps; edge != NULL; ) {
            etmp = edge;
            edge = edge->next;
            free(etmp);
        }
        ttmp = task;
        task = task->unext;
        free(ttmp->name);
        free(ttmp->desc);
        free(ttmp->date);
        free(ttmp);
    }
    free(agenda->array);
    free(agenda);
}

/* todo: print next tasks */
int
main(int argc, char *argv[])
{
    static struct Agenda *agenda;
    FILE *fp;
    int exitval, ch;

    today = gettoday();
    while ((ch = getopt(argc, argv, "dl")) != -1) {
        switch (ch) {
        case 'd':
            dflag = 1;
            break;
        case 'l':
            lflag = 1;
            break;
        default:
            usage();
            break;
        }
    }
    argc -= optind;
    argv += optind;
    exitval = 0;
    agenda = newagenda();
    if (argc == 0) {
        readtasks(stdin, agenda);
    } else {
        for (; *argv != NULL; argv++) {
            if (strcmp(*argv, "-") == 0) {
                readtasks(stdin, agenda);
                continue;
            }
            if ((fp = fopen(*argv, "r")) == NULL) {
                warn("%s", *argv);
                exitval = 1;
                continue;
            }
            readtasks(fp, agenda);
            fclose(fp);
        }
    }
    sorttasks(agenda);
    printtasks(agenda);
    freeagenda(agenda);
    return exitval;
}

EDIT: I removed the topological sort and released todo(1) on github with another utility of mine.

Answer 1

About the manpage

The manpage looks very nice! There's a few small improvements that could be made:

• Spelling: "decrescend" should be "decreasing".
• Some conflicting statements are made, like "Each event must begin with an optional status." Consider rewriting this to avoid any confusion. Perhaps also start with a single line showing the syntax of each line, like so:

  [status] [priority] task-name: [description] [name:value]...
  

• Also, the description says the priority comes after status and before the task name, but the example shows the priority coming after the task name.
• Put the description of the file format in its own section.
• Show off all features in the examples section, in particular I am not seeing the "due" option being used, nor line continuation using backslashes.

Avoid using #define if a static const variable will do

Instead of defining constants using #define, prefer declaring them as static const variables instead. This avoids having to deal with macro issues like needing lots of parentheses, and ensures those constants also have a type associated with them. For example:

static const time_t SECS_PER_DAY = 24 * 60 * 60;
static const int DAYS_PER_WEEK = 7;
...
static const char PROP_DUE[] = "due";

Reduce the number of data structures

I think I'm using a convoluted solution, because I create five different data structures in the program.

Indeed, it's a bit much, and you could get rid of some. Instead of having hash maps and linked lists, you could store everything in arrays: one array of struct Tasks, and perhaps some others with pointers to Tasks if necessary. This whole array can then be sorted using qsort(), and then you can do \$\mathcal{O}(\log N)\$ lookups using bsearch().

While hash maps are the fastest for sufficiently large numbers of tasks, a sorted array will probably outperform it for a small number of tasks.

Another option is to not use your own hash map implementation, but use the POSIX hcreate() and related functions.

Unnecessary topological sort

You mention you do a topological sort of the tasks, then iterate over that sorted list and print out all the unblocked tasks. However, just determining whether tasks are blocked or not does not require a topological sort at all. Instead, just add a flag bool blocked to struct Task, make sure it is false when a new Task is created. Then after reading in all the tasks, just iterate over all of them, and for each task check its dependencies. If it depends on a task that is not yet DONE, then just set blocked = true. Then do another pass to print out only the tasks that have blocked == false. If you only allow dependencies on tasks that have already been read in, then you can even do the check of being blocked inside addtask().

Rename lookup() to lookup_or_create()

The lookup function also is used to create new tasks, so I would rename it lookup_or_create(). Alternatively, have separate lookup() and newtask() functions.

Initialize all elements when creating a new Task

In lookup(), when you create a new Task, you only initialize some of the elements of this struct. I recommend you ensure all of them are properly initialized, by just using ecalloc() instead of emalloc(). This will avoid surprises.

Add comments to or split up long functions

The function addtask() is quite long. Try to separate it into several sections and add a comment to each section describing what is done. It should look something like this:

// Strip leading spaces
while (isspace((unsigned char)*s))
    s++;

// Check for the optional state
done = 0;
if (strncmp(s, TODO, sizeof(TODO) - 1) == 0) {
    ...
}
...

// Read the task name
...

// And so on...

Even better would be to create separate functions for each section, so that addtask() would look like this instead:

done = readstatus(&s);

name = readname(&s);
if (name == NULL)
    return;
...

Where for example readstatus() would look like:

static void skipspaces(char **s) {
    while (isspace((unsigned char)**s))
        ++*s;
}

static bool readstatus(char **s) {
    skipspace(s);

    if (strncmp(*s, ...)) {
        *s += ...;
    } else if (...) {
        ...
        return true;
    }

    return false;
}

Missing error checking

You check whether files are opened correctly, but you don't check if the files were read correctly. After reading in all the lines, use feof() to check whether you actually reached the end of the file. If not, something has gone wrong.

Also consider exitting the program immediately upon any read error, instead of just setting exitval = 1. The user might not notice the non-zero exit code, and you are printing potentially incorrect data.

Furthermore, also consider exitting with an error message and non-zero exit code if parsing the lines failed, and if other errors are detected such as cyclical dependencies.

You might also want to check that printing the tasks was done succesfully. Consider someone redirecting standard output to a file on a file system that is nearly full. In case writing fails, you again want to print an error message to standard error, and exit with a non-zero exit code. To do this correctly, I recommend you do this right at the end of main() by first calling fflush(), then using ferror() to check if any error was encountered while writing to stdout.

I also recommend you use EXIT_SUCCESS and EXIT_FAILURE as the exit codes.

Answer 2

   agenda->htab = ecalloc(NHASH, sizeof(*(agenda->htab)));

GCC's static analyzer can't find a corresponding call to free() for this allocation. It gets through Valgrind at runtime, but that's only because sorttasks() has been called, which is fragile. And if sorttasks() gets called more than once, we'll be accessing freed memory, which is UB.

I would modify sorttasks to set agenda->htab = NULL after freeing the memory, and add free(agenda->htab) to freeagenda(). That will make the code much more robust (and keep the static analysis on our side).

Also, it's a poor assumption that calloc() produces null pointers - that's not universally true for all architectures.

---

The order of functions in the file makes it harder to find things. In particular, I would expect newagenda() and freeagenda() to be adjacent.

In freeagenda(), there's no need for the variables to be at function scope. They can be reduced to where they are used (and given better names):

static void
freeagenda(struct Agenda *agenda)
{
    for (struct Task *task = agenda->unsort;  task;  ) {
        struct Task *next_task = task->unext;
        for (struct Edge *edge = task->deps;  edge;  ) {
            struct Edge *next_edge = edge->next;
            free(edge);
            edge = next_edge;
        }
        free(task->name);
        free(task->desc);
        free(task->date);
        free(task);
        task = next_task;
    }
    free(agenda->array);
    free(agenda);
}

---

static void
usage(void)
{
    (void)fprintf(stderr, "usage: todo [-ld] [file...]\n");
    exit(1);
}

This usage message is useful only as an error. We could adapt it to provide --help:

static void __attribute__((noreturn))
usage(int is_err)
{
    fputs("usage: todo [-ld] [file...]\n", is_err ? stderr : stdout);
    exit(is_err);
}

---

It's a shame not to see the unit tests for the parsing. There's a lot of problem cases to consider, and I would expect the tests to be present, to give confidence in future changes. I wouldn't accept this without the accompanying test suite.

---

(This is a partial review - I got a higher-priority interrupt and not sure whether I'll return to this.)