Correct order of overflowing_tokens for slow tokenizer
Author: Apoorvgarg-creator
Pull request: yes

# What does this PR do?
 When using a slow tokenizer (LayoutLM, Bert, Alberta, etc.), the `overflowing_tokens` were obtained in the wrong order. I have made the necessary changes that will produce the `overflowing_tokens` in the correct order.
## Tasks summary - 
- [x] making sure overflowing tokens are returned in the correct order for all `truncation_strategy` for a sequences of input ids.
- [x] if a pair of sequences of input ids (or batch of pairs) is provided, an error should be raised for the `truncation_strategy=True` or `longest_first` stating _"Not possible to return overflowing tokens for pair of sequences with the `longest_first`.Please select another truncation strategy than `longest_first`, for instance `only_second` or `only_first`."_
- [x] Replaced the deprecated method `encode_plus` to regular `__call__` method in `test\test_tokenization_common.py`.

<!--
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 -->

This PR fixes the issue [ huggingface/transformers#13148 ](https://github.com/huggingface/transformers/issues/13148 ) 
Fixes huggingface#13148



## Before submitting
- [x] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/master/CONTRIBUTING.md#start-contributing-pull-requests),Pull Request section? Yes 👍🏻
- [x] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? Yes, [ huggingface/transformers#13148 ](https://github.com/huggingface/transformers/issues/13148 ) 
- [x] Did you write any new necessary tests?Yes 👍🏻  , Required tests are added in `tests/test_tokenization_common.py`
- [x] Did you make sure to update the documentation with your changes? 


Anyone in the community is free to review the PR once the tests have passed.

<!-- 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

 -->
@patrickvonplaten  @NielsRogge @LysandreJik @n1t0 @SaulLu 

Comments:
Thank you very much for working on this PR.

Did you check the test `test_maximum_encoding_length_single_input` and `test_maximum_encoding_length_pair_input`  passed locally? :slightly_smiling_face:  

I think it would be good to have some tests to check that the tokens are in the right order now. What do you think? The first thing I see would be to complete the tests performed in methods [`test_maximum_encoding_length_single_input`](https://github.com/huggingface/transformers/blob/master/tests/test_tokenization_common.py#L846) and [`test_maximum_encoding_length_pair_input` ](https://github.com/huggingface/transformers/blob/master/tests/test_tokenization_common.py#L938) in file `test_tokenization_common.py`. 

For example, currently, sometimes we check that the content of the overflowing tokens corresponds to what we expect for the [fast tokenizers](https://github.com/huggingface/transformers/blob/master/tests/test_tokenization_common.py#L928) but not for the [slow ones](https://github.com/huggingface/transformers/blob/master/tests/test_tokenization_common.py#L937) (and [here](https://github.com/huggingface/transformers/blob/master/tests/test_tokenization_common.py#L1079) and [here](https://github.com/huggingface/transformers/blob/master/tests/test_tokenization_common.py#L1111)). 

Our goal is really to check in the tests the resulting overflowing tokens for all cases , i.e. all `TruncationStrategy` and with 1 sequence or a pair of sequences. 

Don't hesitate to tell me if you need more help to complete these tests. :slightly_smiling_face: 





> Did you check the test `test_maximum_encoding_length_single_input` and `test_maximum_encoding_length_pair_input` passed locally?
 No. These two tests weren't passed locally either.


> I think it would be good to have some tests to check that the tokens are in the right order now.
I ran the updated code on several tokenizers to verify the result. They all passed. I will try making better test cases.

As mentioned, Firstly I will try to resolve the ` test_maximum_encoding_length_single_input` and `test_maximum_encoding_length_pair_input`.

Thank you @SaulLu.

@SaulLu I would like to make a request.
I want to know the correct order of overflowing tokens  for the test case : 

```
from transformers import BertTokenizer

tokenizer = BertTokenizer.from_pretrained("bert-base-uncased")

seq = ["hello my name is Ted Mosby ", "I am an Architect in Boston "]

encoding = tokenizer(seq[0],seq[1], padding=True, max_length=6, truncation=True, return_overflowing_tokens=True)

print(tokenizer.decode(encoding.input_ids))

print(tokenizer.decode(encoding.overflowing_tokens))
```

You make a very good point! Indeed, we have an API choice to make here. 

I'm going to list the possibilities I see here because I don't see an "ideal" solution that would fit into the current framework (i.e. a single list). I take the example you gave:
```python
from transformers import BertTokenizer

tokenizer = BertTokenizer.from_pretrained("bert-base-uncased")
seq = ["hello my name is Ted Mosby ", "I am an Architect in Boston "]
encoding = tokenizer(seq[0],seq[1], padding=True, max_length=6, truncation=True, return_overflowing_tokens=True)

print(tokenizer.decode(encoding.input_ids))
```
Output
```
[CLS] hello my [SEP] i [SEP]
```
the possibilities I see for the output of `encoding.overflowing_tokens`:
1. Concatenate in the same list the overflowing tokens of the sequence 1 and the sequence 2. As a result ``print(tokenizer.decode(encoding.overflowing_tokens))`` will return:
```
'name is Ted Mo ##sby am an Architect in Boston'
```
Advantage: the output format is the same; Disadvantage: we can't distinguish between the first and the second sequence
2. Create a tuple of 2 lists for the overflowing tokens of the sequence 1 and the sequence 2. As a result ``print(tokenizer.decode(encoding.overflowing_tokens[0]), tokenizer.decode(encoding.overflowing_tokens[1]))`` will return:
```
'name is Ted Mo ##sby' 'am an Architect in Boston'
```
Advantage: we can distinguish between the first and the second sequence; Disadvantage: the output format is not the same. This can be seen as a temporary micro-change if we ever want to standardize the API of fast and slow tokenizers in a second PR.
3. Raise an error because as many comments in the tests show, before it was not possible to return overflowing tokens for slow tokenizers with the longest_first strategy

@LysandreJik , @sgugger, @patil-suraj or @patrickvonplaten I think your point of view can be useful here. Should we change the output format ? Should we also aim to have the same behavior for the slow and fast tokenizers ? :slightly_smiling_face: 

> Disadvantage: we can't distinguish between the first and the second sequence

For the above Disadvantage, The following method might resolve it -
The use of special tokens might help in this problem 
For instance: On the same test case mentioned above -
` [CLS] name is Ted Mo ##sby  [SEP] am an Architect in Boston [SEP]  `
 
@SaulLu Thank you for helping me out with the test case.

For `test_maximum_encoding_length_single_input` earlier the order was not correct for the slow tokenizer (i.e. reverse order if stride = 0 ) but now I guess we can add this line of code 

https://github.com/huggingface/transformers/blob/143738214cb83e471f3a43652617c8881370342c/tests/test_tokenization_common.py#L928 

for Slow tokenizer as well.

@SaulLu 

@SaulLu @LysandreJik @NielsRogge @patrickvonplaten, could you please review the changes I have done in the code.

Hello, thank you for your PR! Could you please add some tests to ensure correct behavior? You can add them in `tests/tests_tokenization_common.py` so that all tokenizers get tested. Thank you!

> Hello, thank you for your PR! Could you please add some tests to ensure correct behavior? You can add them in `tests/tests_tokenization_common.py` so that all tokenizers get tested. Thank you!

@LysandreJik Thank you for reviewing the PR. Sure, I will add the necessary test to ensure the correct behavior.

@LysandreJik All the necessary tests have been added.

@LysandreJik, could you please review the tests I have added to the code. 
Thank you

Thanks for the ping @Apoorvgarg-creator, @SaulLu will take over and review :)

@Apoorvgarg-creator , thanks again for your work, I am trying to look at your PR quickly.

> @SaulLu I would like to make a request.
I want to know the correct order of overflowing tokens for the test case :

In the meantime, sorry for the delay, but after discussing it, for this case (pair of sequences and `longest_first` strategy) we think it would be better to return an error.

> @Apoorvgarg-creator , thanks again for your work, I am trying to look at your PR quickly.
> 
> > @SaulLu I would like to make a request.
> > I want to know the correct order of overflowing tokens for the test case :
> 
> In the meantime, sorry for the delay, but after discussing it, for this case (pair of sequences and `longest_first` strategy) we think it would be better to return an error.

So the code should raise an error message whenever we try to return overflowing tokens for a pair of sequences with the `longest_first` strategy.

And For single_input, I have corrected the order and also added the necessary tests in `test_tokenization_common.py`. Do these require any changes?

@SaulLu , Thank you for the review.

<img width="1076" alt="Screenshot 2021-08-27 at 9 04 24 AM" src="https://user-images.githubusercontent.com/57873504/131067867-0f681b61-a82c-44ec-97f1-fa40b44fd3f3.png">

[Documentation/Preprocessing data]( https://huggingface.co/transformers/preprocessing.html ),Here they have mentioned when truncation_strategy  is set to 'True' it means `only_first` instead of `longest_first`.
@sgugger 

> <img alt="Screenshot 2021-08-27 at 9 04 24 AM" width="1076" src="https://user-images.githubusercontent.com/57873504/131067867-0f681b61-a82c-44ec-97f1-fa40b44fd3f3.png">
> 
> [Documentation/Preprocessing data](https://huggingface.co/transformers/preprocessing.html),Here they have mentioned when truncation_strategy is set to 'True' it means `only_first` instead of `longest_first`.


Great catch. Indeed, the documentation seems to differ between the section ["Everything you always wanted to know about padding and truncation"](https://huggingface.co/transformers/preprocessing.html?highlight=truncation#everything-you-always-wanted-to-know-about-padding-and-truncation) and [the docstring of the _call__ methode of `PreTrainedTokenizerBase`](https://huggingface.co/transformers/internal/tokenization_utils.html?highlight=truncation#transformers.tokenization_utils_base.PreTrainedTokenizerBase.__call__). It would be best if you opened a dedicated issue so that we can deal with the problems separately?

> It would be best if you opened a dedicated issue so that we can deal with the problems separately?

Sure. I will make a separate issue for this.
Thank you for the reviews, @SaulLu. I will do the dedicated changes at the earliest.

> I didn't check if that the case or, did you check it?

No, I haven't. But I will go through the things you have mentioned above. 

@SaulLu, All the changes that I could find in the docstring have been done.

@sgugger Thank you for reviewing the PR. I have made the changes mentioned above. Do I need to change every use case of `tokenizer.encode_plus` or only in the `test_maximum_encoding_length_pair_input`.

@LysandreJik @SaulLu, all the dedicated changes have been resolved. Could you please review the PR?
Thank you 

Thanks for fixing this, great work!

@SaulLu @LysandreJik @sgugger @NielsRogge, Thank you for the guidance. It was an insightful experience and I hope to contribute more.