What does this PR do?

• implement AC automaton to supersede Trie to fix DisjunctiveConstraint edge case
• add ConjunctiveDisjunctiveConstraint to handle the complex combinations between multiple conjunctive and disjunctive constraints
• update stronger unit tests

Fixes # (issue)

#17831

Before submitting

• [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
• [x] Did you read the contributor guideline, Pull Request section?
• [x] Was this discussed/approved via a Github issue or the forum? Please add a link to it if that's the case.
• [x] Did you make sure to update the documentation with your changes? Here are the documentation guidelines, and here are tips on formatting docstrings.
• [x] Did you write any new necessary tests?

Who can review?

@patrickvonplaten, @cwkeam

The docs for this PR live here. All of your documentation changes will be reflected on that endpoint.

Hey @boy2000-007man,

Thanks for the fix proposal! @cwkeam could you take a look here as well? :-)

@boy2000-007man - it'd be really nice if you could add a test that would have failed without your fix, but will now pass.

Thanks a lot for working on this!

Hey @boy2000-007man,

Thanks a lot for the PR - I'm a bit worried about adding so much new code to main transformers to catch an edge case and wonder if it's really worth it. The problem is that this function will quickly become unmaintainable (it already sadly is to some extent) - in your opinion is it absolutely necessary to add this edge case? Also could you maybe provide a "real" generation example that shows how the current implementation fails?

Hi, @patrickvonplaten, the current code implementation is complex to support both the existing DisjunctiveConstraint and newly added ConjunctiveDisjunctiveConstraint at the same time. I can add a much-simplified version dedicated to back DisjunctiveConstraint only, and the new ConjunctiveDisjunctiveConstraint is not used by the library default but requires manual import, so won't break any existing works by chance. Finding a failure case is not that straightforward especially without deep understanding of specific model preference, but I can image some constraints like the small cat/small cats, the united states/united kingdom may be influenced.

Hey @boy2000-007man,

Sorry to reply so late here. Will gently ask @cwkeam in private if he could take a quick look because he's the most familiar with the current code. if there is no answer, I'll come back to it and dive deeper into the code to be able to better answer here.

Also cc @gante if you're feeling curios on complex code ;-)

Hi @boy2000-007man 👋 I was having a look into this PR, and one thing I noticed was that the objective of the PR was not immediately clear -- it says at the top that it fixes an edge case but... what edge case? We can find the answer to that in the code, especially in the docstring of ConjunctiveDisjunctiveConstraint.

I do think we should fix the edge case, as the documented behavior does not match the actual behavior. However, adding clear examples (as in #15761) will be extremely useful for our future selves 🙏 It will also helps the reviewers seeing the value of the PR :D

Hi, @gante , Sorry for the late reply. The edge case is mentioned in the associated bug report, https://github.com/huggingface/transformers/issues/17831. Do you mean to mention it again in the docstring?

Do you mean to mention it again in the docstring

Yes please, but with input strings (as opposed to tokens).

It's hard to justify adding so many new lines of code without a clear example of why it matters :) We have very limited maintenance capacity, so sometimes it's preferable to have an incomplete short solution that we can maintain than a complete long solution that will accumulate bugs as we introduce new features.

This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the contributing guidelines are likely to be ignored.