Fix DisjunctiveConstraint edge case and add ConjunctiveDisjunctiveConstraint
Author: boy2000-007man
Pull request: yes

# What does this PR do?
- implement [`AC automaton`](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm) 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
<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

<!-- Remove if not applicable -->

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](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [x] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? 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](https://github.com/huggingface/transformers/tree/main/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/main/docs#writing-source-documentation).
- [x] Did you write any new necessary tests?


## Who can review?

@patrickvonplaten, @cwkeam 

<!-- Your PR will be replied to more quickly if you can figure out the right person to tag with @

 If you know how to use git blame, that is the easiest way, otherwise, here is a rough guide of **who to tag**.
 Please tag fewer than 3 people.

Models:

- albert, bert, xlm: @LysandreJik
- blenderbot, bart, marian, pegasus, encoderdecoder,  t5: @patrickvonplaten, @patil-suraj
- longformer, reformer, transfoxl, xlnet: @patrickvonplaten
- fsmt: @stas00
- funnel: @sgugger
- gpt2: @patrickvonplaten, @LysandreJik
- rag: @patrickvonplaten, @lhoestq
- tensorflow: @LysandreJik

Library:

- benchmarks: @patrickvonplaten
- deepspeed: @stas00
- ray/raytune: @richardliaw, @amogkam
- text generation: @patrickvonplaten
- tokenizers: @n1t0, @LysandreJik
- trainer: @sgugger
- pipelines: @LysandreJik

Documentation: @sgugger

HF projects:

- datasets: [different repo](https://github.com/huggingface/datasets)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Examples:

- maintained examples (not research project or legacy): @sgugger, @patil-suraj
- research_projects/bert-loses-patience: @JetRunner
- research_projects/distillation: @VictorSanh

 -->


Comments:
The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_17920). 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](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md) are likely to be ignored.