Why is python decode replacing more than the invalid bytes from an encoded string?

Question

You know that your S is valid, with the benefit of both look-ahead and hindsight :-) Suppose there was originally a legal 3-byte UTF-8 sequence there, and the 3rd byte was corrupted in transmission ... with the change that you mention, you'd be complaining that a spurious S had not been replaced. There is no "right" way of doing it, without the benefit of error-correcting codes, or a crystal ball, or a tamborine.

Update

As @mjv remarked, the UTC issue is all about how many U+FFFD should be included.

In fact, Python is not using ANY of the UTC's 3 options.

Here is the UTC's sole example:

      61      F1      80      80      E1      80      C2      62
1   U+0061  U+FFFD                                          U+0062
2   U+0061  U+FFFD                  U+FFFD          U+FFFD  U+0062
3   U+0061  U+FFFD  U+FFFD  U+FFFD  U+FFFD  U+FFFD  U+FFFD  U+0062

Here is what Python does:

>>> bad = '\x61\xf1\x80\x80\xe1\x80\xc2\x62cdef'
>>> bad.decode('utf8', 'replace')
u'a\ufffd\ufffd\ufffdcdef'
>>>

Why?

F1 should start a 4-byte sequence, but the E1 is not valid. One bad sequence, one replacement.
Start again at the next byte, the 3rd 80. Bang, another FFFD.
Start again at the C2, which introduces a 2-byte sequence, but C2 62 is invalid, so bang again.

It's interesting that the UTC didn't mention what Python is doing (restarting after the number of bytes indicated by the lead character). Perhaps this is actually forbidden or deprecated somewhere in the Unicode standard. More reading required. Watch this space.

Update 2 Houston, we have a problem.

=== Quoted from Chapter 3 of Unicode 5.2 ===

Constraints on Conversion Processes

The requirement not to interpret any ill-formed code unit subsequences in a string as characters (see conformance clause C10) has important consequences for conversion processes.

Such processes may, for example, interpret UTF-8 code unit sequences as Unicode character sequences. If the converter encounters an ill-formed UTF-8 code unit sequence which starts with a valid first byte, but which does not continue with valid successor bytes (see Table 3-7), it must not consume the successor bytes as part of the ill-formed subsequence whenever those successor bytes themselves constitute part of a well-formed UTF-8 code unit subsequence.

If an implementation of a UTF-8 conversion process stops at the first error encountered, without reporting the end of any ill-formed UTF-8 code unit subsequence, then the requirement makes little practical difference. However, the requirement does introduce a significant constraint if the UTF-8 converter continues past the point of a detected error, perhaps by substituting one or more U+FFFD replacement characters for the uninterpretable, ill-formed UTF-8 code unit subsequence. For example, with the input UTF-8 code unit sequence <C2 41 42>, such a UTF-8 conversion process must not return <U+FFFD> or <U+FFFD, U+0042>, because either of those outputs would be the result of misinterpreting a well-formed subsequence as being part of the ill-formed subsequence. The expected return value for such a process would instead be <U+FFFD, U+0041, U+0042>.

For a UTF-8 conversion process to consume valid successor bytes is not only non-conformant, but also leaves the converter open to security exploits. See Unicode Technical Report #36, “Unicode Security Considerations.”

=== End of quote ===

It then goes on to discuss at length, with examples, the "how many FFFD to emit" issue.

Using their example in the 2nd last quoted paragraph:

>>> bad2 = "\xc2\x41\x42"
>>> bad2.decode('utf8', 'replace')
u'\ufffdB'
# FAIL

Note that this is a problem with both the 'replace' and 'ignore' options of str.decode('utf_8') -- it's all about omitting data, not about how many U+FFFD are emitted; get the data-emitting part right and the U+FFFD issue falls out naturally, as explained in the part that I didn't quote.

Update 3 Current versions of Python (including 2.7) have unicodedata.unidata_version as '5.1.0' which may or may not indicate that the Unicode-related code is intended to conform to Unicode 5.1.0. In any case, the wordy prohibition of what Python is doing didn't appear in the Unicode standard until 5.2.0. I'll raise an issue on the Python tracker without mentioning the word 'oht'.encode('rot13').

Reported here

the 0xE3 byte is one (of the possible) first bytes indicative of a 3-bytes character.

Apparently Python's decode logic takes these three bytes and tries to decode them. They turn out to not match an actual code point ("character") and that is why Python produces a UnicodeDecodeError and emits a substitution character
It appears, however that in doing so, Python's decode logic doesn't adhere to the recommendation of the Unicode Consortium with regards to substitution characters for "ill-formed" UTF-8 sequences.

See UTF-8 article on Wikipedia for background info about UTF-8 encoding.

New (final?) Edit: re the UniCode Consortium's recommended practice for replacement characters (PR121)
(BTW, congrats to dangra to keep digging and digging and hence making the question better)
Both dangra and I were partially incorrect, in our own way, regarding the interpretation of this recommendation; my latest insight is that indeed the recommendation also speaks to trying and "re-synchronize".
The key concept is that of the maximal subpart [of an ill-formed sequence].
In view of the (lone) example supplied in the PR121 document, the "maximal subpart" implies not reading-in the bytes which could not possibly be part of a sequence. For example, the 5th byte in the sequence, 0xE1 could NOT possibly be a "second, third or fourth byte of a sequence" since it isn't in the x80-xBF range, and hence this terminates the ill-formed sequence which started with xF1. Then one must try and start a new sequence with the xE1 etc. Similarly, upon hitting the x62 which too cannot be interpreted as a second/third/fourth byte, the bad sequence is ended, and the "b" (x62) is "saved"...

In this light (and until corrected ;-) ) the Python decoding logic appears to be faulty.

Also see John Machin's answer in this post for more specific quotes of the underlying Unicode standard/recommendations.

In 'PREFIX\xe3\xabSUFFIX', the \xe3 indicates that it and the next two bites form one unicode code point. (\xEy does for all y.) However, \xe3\xabS obviously does not refer to a valid code point. Since Python knows it's supposed to take three bytes, it sucks up all three anyhow since it doesn't know your S is an S and not just some byte representing 0x53 for some other reason.