mozilla/crontabber — pull request #58 by rsmenon (2014-12-16 00:09:53+00:00)
Title: Fix incorrect CircularDAGError when sorting dependencies

The implementation of `reorder_dag` gives incorrect `CircularDAGError` when dependent jobs themselves have other dependencies. For example:

```
job | dependencies
----+-------------
A | None
B | A
C | B
D | None
E | A, B
F | C, D, E

```

This is due to [line 76 in `base.py`](https://github.com/mozilla/crontabber/blob/master/crontabber/base.py#L76) which effectively says "if the dependencies are not in the set of ordered jobs, then skip". Instead, the dependencies should be further sorted (to make sure their dependencies are also satisfied) and added to the jobs list. Such sortings are called ["toplogical sorts"](http://en.wikipedia.org/wiki/Topological_sorting) and there are efficient algorithms and packages for this.

In this pull request, I've used the [toposort](https://pypi.python.org/pypi/toposort/1.0) package to handle the dependency ordering. Note that:

- I've modified the code minimally, changing only what's absolutely necessary.
- The `impatience_max` parameter is left as is so that code elsewhere doesn't break.
- I still raise a `CircularDAGError` after capturing toposort's `ValueError` so that try/except blocks that catch the first one don't break.

Another point is that [line 86](https://github.com/mozilla/crontabber/blob/master/crontabber/base.py#L84) in the original `base.py` also assumes that all the jobs are listed in a single `crontabber.ini` file, but this doesn't have to be the case. Suppose in the above example, job `D` was in the `crontabber.ini` file for a different machine, then this line would throw a `KeyError` because the parent job is not in the list passed to `reorder_dag`. This has now been changed to ignore missing keys. I believe this is OK, because in [line 1083 of `app.py`](https://github.com/mozilla/crontabber/blob/master/crontabber/app.py#L1083), the postgres database is used to verify that the parent job has run.

I have been using this version in our environment and it works fine (while the version from `pip` didn't). Let me know if you're interested in merging this pull request and if so, I'll tidy up a few things:

- [ ] Add toposort to requirements.txt
- [ ] Add tests
- [ ] Remove usages of `impatience_max`