Support unknown formats in memoryview comparisons

[skrah]

BPO	15573
Nosy	@loewis, @birkenfeld, @mdickinson, @ncoghlan, @pitrou, @vstinner, @tiran, @skrah, @meadori
Files	format.c issue15573.diff abstractcmp.diff issue15573-struct.diff: full struct module support for comparisons issue15573-struct-2.diff memoryobject.c.gcov

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/skrah'
closed_at = <Date 2012-08-29.17:09:27.233>
created_at = <Date 2012-08-07.11:55:30.289>
labels = ['interpreter-core', 'type-bug', 'release-blocker']
title = 'Support unknown formats in memoryview comparisons'
updated_at = <Date 2012-11-02.17:07:02.101>
user = 'https://github.com/skrah'

bugs.python.org fields:

activity = <Date 2012-11-02.17:07:02.101>
actor = 'python-dev'
assignee = 'skrah'
closed = True
closed_date = <Date 2012-08-29.17:09:27.233>
closer = 'skrah'
components = ['Interpreter Core']
creation = <Date 2012-08-07.11:55:30.289>
creator = 'skrah'
dependencies = []
files = ['26720', '26725', '26766', '26800', '26831', '26992']
hgrepos = []
issue_num = 15573
keywords = ['patch']
message_count = 63.0
messages = ['167618', '167621', '167655', '167687', '167838', '167844', '167855', '167856', '167860', '167862', '167884', '167892', '167899', '167902', '167908', '167911', '167912', '167930', '167946', '167981', '167982', '167984', '167987', '167990', '167991', '167993', '167994', '168000', '168002', '168003', '168004', '168006', '168010', '168028', '168029', '168031', '168032', '168188', '168202', '168257', '168301', '168440', '168559', '168560', '168564', '169023', '169085', '169106', '169107', '169108', '169109', '169110', '169111', '169112', '169113', '169114', '169115', '169347', '169355', '169388', '169394', '169399', '174541']
nosy_count = 11.0
nosy_names = ['loewis', 'georg.brandl', 'mark.dickinson', 'ncoghlan', 'pitrou', 'vstinner', 'christian.heimes', 'Arfrever', 'skrah', 'meador.inge', 'python-dev']
pr_nums = []
priority = 'release blocker'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue15573'
versions = ['Python 3.3']

[skrah]

Continuing the discussion from bpo-13072. I hit a snag here:

Determining in full generality whether two format strings describe
identical items is pretty complicated, see also bpo-3132.

I'm attaching a best effort fmtcmp() function that should do the
following:

• recognize byte order specifiers at the start of the string.

• recognize if an explicitly specified byte order happens to
  match the native byte order.

It won't catch:

• byte order specifiers anywhere in the string.

• C types that happen to be identical ('I', 'L' on a 32-bit
  platform). I'm also not sure if that is desirable in the
  first place.

• ???

So fmtcmp() will return false negatives (not equal), but should be
correct for *most* format strings that are actually in use.

Mark, Meador: You did a lot of work on the struct module and of
course on issue bpo-3132. Does this look like a reasonable compromise?
Did I miss obvious cases (see attachment)?

[ncoghlan]

I confess I was thinking of an even simpler "format strings must be identical" fallback, but agree your way is better, since it reproduces the 3.2 behaviour in many more cases where ignoring the format string actually did the right thing.

The struct docs for the byte order specifier specifically say "the first character of the format string can be used to indicate the byte order, size and alignment of the packed data", so treating format strings that include byte order markers elsewhere in the string as differing from each other if those markers are in different locations sounds fine to me.

[meadori]

I agree that the general case is complicated. It will get even more complicated if the full of PEP-3118 gets implemented since it turns into a tree comparison. In general, I think you will probably have to compute some canonical form and then compare the canonical forms.

Here are a few more cases that don't work out in the attached algorithm:

1. Repeat characters - '2c' == 'cc'
2. Whitespace - 'h h' == 'hh'

Also, currently the byte order specifiers are always at the beginning of the string. We discussed in bpo-3132 scoping them per the nested structures, but decided to drop that unless somebody barks about it since it is fairly complicated without a clear benefit. So, I wouldn't worry about them being scattered through the string.

This seems like sort of a slippery slope. I need to think about it more, but my first impression is that coming up with some way to compare format strings is going to be nasty.

[skrah]

Right, byte order specifiers are always at the beginning of the string.
That is at least something. I wonder if we should tighten PEP-3118 to
demand a canonical form of format strings, such as (probably incomplete):

• Whitespace is disallowed.

• Except for 's', no zero count may be given.

• A count of 1 (redundant) is disallowed.

• Repeats must be specified in terms of count + single char.

That still leaves the '=I' != '=L' problem. Why are there two
specifiers describing uint32_t?

Anyway, as Meador says, this can get tricky and I don't think this
can be resolved before beta-2. I'm attaching a patch that should
behave well for the restricted canonical form at least.

[loewis]

Can someone please explain why this is a release blocker? What is the specific regression from 3.2 that this deals with?

[vstinner]

What is the specific regression from 3.2 that this deals with?

I don't know if it must be called a regression, but at least the behaviour is different in Python 3.2 and 3.3. For example, an Unicode array is no more equal to its memoryview:

Python 3.3.0b1 (default:aaa68dce117e, Aug  9 2012, 22:45:00)                                                                                                   
[GCC 4.6.3 20120306 (Red Hat 4.6.3-2)] on linux                                                                                                                
Type "help", "copyright", "credits" or "license" for more information.                                                                                         
>>> import array                                                                                                                                               
>>> a=array.array('u', 'abc')
>>> v=memoryview(a)                                                                                                                                            
>>> a == v                                                                                                                                                     
False                                                                                                                                                          

ned$ python3
Python 3.2.3 (default, Jun  8 2012, 05:40:07)                                                                                                                  
[GCC 4.6.3 20120306 (Red Hat 4.6.3-2)] on linux2                                                                                                               
Type "help", "copyright", "credits" or "license" for more information.                                                                                         
>>> import array                                                                                                                                               
>>> a=array.array('u', 'abc')
>>> v=memoryview(a)                                                                                                                                            
>>> a == v                                                                                                                                                     
True

[loewis]

haypo: thanks for stating the issue.

ISTM that this classifies as an "obscure" bug: you have to use memoryviews, and you need to compare them for equality, and the comparison needs to be "non-trivial", where "trivial" is defined
by "both are 1D byte arrays".

While this is a bug, I think it still can be fixed in a bug fix
release of 3.3, so un-blocking.

I also think that as a first step, a specification needs to be
drafted defining when exactly a memory view should compare equal
with some other object. I can easily provide a specification that
makes the current implementation "correct".

[skrah]

I can easily provide a specification that makes the current implementation "correct"

Yes, the current specification is: memoryview only attempts to
compare arrays with known (single character native) formats and
returns "not equal" otherwise.

The problem is that for backwards compatibility memoryview accepts
arrays with arbitrary format strings. In operations like tolist()
it's possible to raise NotImplemented, but for equality comparisons
that's not possible.

Note that in 3.2 memoryview would return "equal" for arrays that
simply aren't equal, if those arrays happen to have the same bit
pattern.

One way to deal with this is to demand a strict canonical form
of format strings for PEP-3118, see msg167687.

[loewis]

Note that in 3.2 memoryview would return "equal" for arrays that
simply aren't equal, if those arrays happen to have the same bit
pattern.

This is exactly my point. If a "memoryview" has the same "memory"
as another, why are they then not rightfully considered equal?
IOW, the 3.2 behavior looks fine to me.

You apparently have a vision that equality should mean something
different for memoryviews - please explicitly state what that
view is. A mathematical definition ("two memoryviews A and B
are equal iff ...") would be appreciated.

One way to deal with this is to demand a strict canonical form
of format strings for PEP-3118, see msg167687.

You are talking about the solution already - I still don't know
what the problem is exactly (not that I *need* to understand
the problem, but at a minimum, the documentation should state
what the intended behavior is - better if people would also
agree that the proposed behavior is "reasonable").

For 3.3, I see two approaches: either move backwards to the
3.2 behavior and defer this change to 3.4 - this would make
it release-critical indeed. Or move forward to a yet-to-be
specified equality operation which as of now may not be
implemented correctly, treating any improvement to it
as a bug fix.

[skrah]

PEP-3118 specifies strongly typed multi-dimensional arrays. The existing
code in the 3.2 memoryview as well as numerous comments by Travis Oliphant
make it clear that these capabilities were intended from the start for
memoryview as well.

Perhaps the name "memoryview" is a misnomer, since the boundaries between
memoryview and NumPy's ndarray become blurry. In fact, the small
implementation of an ndarray in Modules/_testbuffer.c is *also* a memoryview
in some sense, since it can grab a buffer from an exporter and expose it in
the same manner as memoryview.

So what I implemented is certainly not only *my* vision. The PEP essentially
describes NumPy arrays with an interchange format to convert between NumPy
and PIL arrays.

It is perhaps unfortunate that the protocol was named "buffer" protocol,
since it is actually an advanced "array" protocol.

NumPy arrays don't care about the raw memory. It is always the logical array
that matters. For example, Fortran and C arrays have different bit patterns
in memory but compare equal, a fact that the 3.2 implementation completely
misses.

Arrays v and w are equal iff format and shape are equal and for all valid
indices allowed by shape

memcmp((char *)PyBuffer_GetPointer(v, indices),
(char *)PyBuffer_GetPointer(w, indices),
itemsize) == 0.

Equal formats of course imply equal itemsize.