dev-job-in-job branch: False positives on cycle detection

[gsksivesh]

Issue by rclough
Thursday Jan 07, 2016 at 20:40 GMT
Originally opened as thieman#172

---

Want to note this here cause I might not be able to immediately address it.

To replicate:

1. Create "Job A" with trivial task "ls"
2. Create "Job B" and
3. Add "Job A" as a jobtask to "Job B"
4. Add it again, with a new name
5. Add a dependency betweenthe tasks
6. Attempt to run
7. Receive "Unable to start job"

In laymans terms, if you want to make a job that executes another job, twice in a row, which is entirely valid, it will assume it has a cycle.

For whatever reason, the job is not removed from the "context", which denotes which job expansions you are currently running in. I suspect this is due to a poor pass by reference/value assumption

[gsksivesh]

Comment by rclough
Thursday Jan 07, 2016 at 21:47 GMT

---

I've looked at this again, and some discussion here: thieman#60 (comment)

I think the issue is that the context needs to be treated as "immutable". Right now the code looks like (highly simplified):

    def verify(self, context=none):
        if context is none:
            logger.debug("no context set, using empty set")
            context = set()
        if self.name in context:
            return false
        context.add(self.name)

        # Topological sort verifies DAG is acyclic before digging deeper
        ...

        # Traverse nodes and verify any JobTasks
        for task in topo_sorted:
            if not self.implements_expandable(task):
                continue
            cur_job = self.parent._resolve_job(task.target_job_name)
            if cur_job.name in context:
                return False

            # Verify this job has no internal cycles, or references to jobs
            # in the current context
            verified = cur_job.verify(context)
            if not verified:
                return False

        return True

I did some additional debug logging, and what happens is the verify() returns from the first instance of "Job A", but is never removed from the context before attempting to verify the next.

The initial discussion (linked above) seems to assume pass-by-value in passing the context, which is not the case (unless I'm missing some nuance)

I see two main options, but am open to other ideas:

1. only pass a copy of the context (ie force pass-by-value)
2. manually remove yourself from the context before returning True at the end of verify. This should work because all other returns would be False or an Error.

Thoughts?

[gsksivesh]

Comment by rclough
Thursday Jan 07, 2016 at 22:41 GMT

---

I personally think the best way is #2, which just results in the following line, before the final return True above:

context.discard(self.name)

Should be "guaranteed" (:wink:) to work because discard() does not fail on missing key, and self.name is exactly what's added right at the beginning.

Tested it by hand and seems to work, passes existing tests as well.