Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

"probably an cyclic dep or infinite loop" on huge graphs #820

Open
alex65536 opened this issue Jul 24, 2022 · 6 comments
Open

"probably an cyclic dep or infinite loop" on huge graphs #820

alex65536 opened this issue Jul 24, 2022 · 6 comments

Comments

@alex65536
Copy link

alex65536 commented Jul 24, 2022

If the graph is large, you may get the following error:

task: maximum task call exceeded (100) for task: probably an cyclic dep or infinite loop

The reasons are as follows:

task/task.go

Lines 110 to 112 in bf9cd76

if !e.Watch && atomic.AddInt32(e.taskCallCount[call.Task], 1) >= MaximumTaskCall {
return &MaximumTaskCallExceededError{task: call.Task}
}

So, if we try to execute the task >= 100 times, then we crash.

The issue is that RunTask is executed once from each of the dependencies:

task/task.go

Lines 200 to 206 in bf9cd76

g.Go(func() error {
err := e.RunTask(ctx, taskfile.Call{Task: d.Task, Vars: d.Vars})
if err != nil {
return err
}
return nil
})

but we increment the counter before checking if the task is already running or finished. Such check is done below, in startExecution:

task/task.go

Lines 300 to 327 in bf9cd76

func (e *Executor) startExecution(ctx context.Context, t *taskfile.Task, execute func(ctx context.Context) error) error {
h, err := e.GetHash(t)
if err != nil {
return err
}
if h == "" {
return execute(ctx)
}
e.executionHashesMutex.Lock()
otherExecutionCtx, ok := e.executionHashes[h]
if ok {
e.executionHashesMutex.Unlock()
e.Logger.VerboseErrf(logger.Magenta, "task: skipping execution of task: %s", h)
<-otherExecutionCtx.Done()
return nil
}
ctx, cancel := context.WithCancel(ctx)
defer cancel()
e.executionHashes[h] = ctx
e.executionHashesMutex.Unlock()
return execute(ctx)
}

So, if there is a task on which 100 other tasks depend, then the graph will fail with an error.

Moreover, if you read startExecution carefully, then it would appear that the error has nothing to do with cyclic deps. The simplified algorithm is as follows:

RunTask(task) {
  if (hashes.contains(task)) {
    // wait for task
    return;
  }
  hashes.insert(task);
  // iterate over deps
  // run commands
}

So, even for cyclic dependency, the task will be executed once (though, it will eventually stuck waiting for itself).

@q0rban
Copy link
Contributor

q0rban commented Aug 3, 2023

Running into this when running a task on ~150 files using the new for command option.

@q0rban
Copy link
Contributor

q0rban commented Aug 4, 2023

Here's an example Taskfile.yml to replicate this:

version: 3

tasks:
  default:
    vars:
      ITEMS:
        sh: echo {1..101}
    cmds:
      - for: { var: ITEMS }
        task: process-item
        vars:
          ITEM: '{{.ITEM}}'

  process-item:
    cmds:
      - echo {{.ITEM}}

What would be ideal in my mind is for Task to count the number of items that is in the for loop and only throw an error if it is called more than that number.

In addition, a parameter on the task to configure this limit would be desirable:

version: 3

tasks:
  default:
    vars:
      ITEMS:
        sh: echo {1..101}
    cmds:
      - for: { var: ITEMS }
        task: process-item
        vars:
          ITEM: '{{.ITEM}}'

  process-item:
    max-call-count: 101
    cmds:
      - echo {{.ITEM}}

@alex65536
Copy link
Author

What would be ideal in my mind is for Task to count the number of items that is in the for loop and only throw an error if it is called more than that number.

In addition, a parameter on the task to configure this limit would be desirable:

I think it's a very hacky workaround which doesn't solve the issue fully. My comment above states that it's good either:

  • to move this check below, so it will actually check for cyclic deps
  • to get rid of this check at all, because actually it doesn't check for cyclic dependencies at all, but prevents valid configurations from running

@q0rban
Copy link
Contributor

q0rban commented Aug 12, 2023

to get rid of this check at all, because actually it doesn't check for cyclic dependencies at all, but prevents valid configurations from running

That would be fine by me!

I did try to verify that adding a circular dependency triggers the error, which it does, though interestingly it catches it right away, before reaching 100 calls. I think this confirms what you're saying? That the "max call of 100" isn't actually a useful limit since the circular dependency is caught before ever reaching it?

task: Failed to run task "default": task: Maximum task call exceeded (0) for task "one": probably an cyclic dep or infinite loop

The salient bit: "Maximum task call exceeded (0)" instead of "Maximum task call exceeded (100)".

@pd93
Copy link
Member

pd93 commented Nov 29, 2024

Just doing some spring cleaning and a quick update on this issue:

Related issues/PRs

Update

As discussed in #1332 and committed in a70f5aa, we increased the limit from 100 to 1000 to try and mitigate this issue. Obviously, this is not a proper solution to the problem though and this number is still arbitrary and does not actually "detect" cycles.

In #1332 (comment) I mentioned that we were moving to DAG for Taskfiles. This was merged in #1563. However, this did not add DAG to tasks themselves. DAGs (as per their name) do not allow cycles and so would give us proper cycle detection. This is still something that we would like to do in the future and so the fundamental issue remains for now.

I would be open to a change that implemented proper cycle detection as a temporary solutions. This is almost certainly quicker and easier to do than implementing a task DAG right now. However, increasing the limit above 1000 just feels like chasing our tail a bit (where do we stop - people will probably always hit the limit unless we raise it to something unacceptable).

@alex65536
Copy link
Author

This is almost certainly quicker and easier to do than implementing a task DAG right now. However, increasing the limit above 1000 just feels like chasing our tail a bit (where do we stop - people will probably always hit the limit unless we raise it to something unacceptable).

I think a better solution would be to remove this check at all rather than increasing the limit, because, as I have shown above, it doesn't do anything with cycles at all. It only prevents one task from having more than 1000 reverse dependencies.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants