This should ideally succeed:

>>> b''.join([memoryview(b'foo'), b'bar'])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: sequence item 0: expected bytes, memoryview found

(ditto for bytearray.join)

Attached patch adds support for memoryviews to bytes.join:

>>> b''.join([memoryview(b'foo'), b'bar'])
b'foobar'

The implementation currently has some duplication, because it does a first pass to calculate the total size to allocate, and another pass to create the result that calculates the individual sizes again.  Py_SIZE(item) can't be used here for memoryviews, so during the first pass it's now necessary to check for memoryviews and extract the len from the memoryview buffer, and then do it again during the second pass.
If necessary this could be optimized/improved.

I also tried to check for multi-dimensional and non-contiguous buffers, but I didn't manage to obtain a failure so I removed the check for now.
More tests should probably be added to cover these cases, and possibly the patch should be adjusted accordingly.

If/when the patch is OK I'll do the same for bytearrays.

I think memoryview here is example only, and Antoine had in mind arbitrary buffer objects.

Indeed.  Attached new patch.
Tests still need to be improved; bytearrays are still not changed.

We would need to release the buffers and also check for format 'B'.
With issue15958-2.diff this is possible:

>>> import array
>>> a = array.array('d', [1.2345])
>>> b''.join([b'ABC', a])
b'ABC\x8d\x97n\x12\x83\xc0\xf3?'


It is unfortunate that a PyBUF_SIMPLE request does not guarantee 'B'.
I think that's probably a mistake, but it's certainly existing practice.

Also, perhaps we can keep a fast path for bytes and bytearray, but I
didn't time the difference.

Well, given the following works:

>>> import array
>>> a = array.array('d', [1.2345])
>>> b'' + a
b'\x8d\x97n\x12\x83\xc0\xf3?'

It should also work for bytes.join().
I guess that means I'm against the strict-typedness of memoryviews. As the name suggests, it provides access to some memory area, not some structured array of data.

Attached new refleakless patch.

> Attached new refleakless patch.

Your approach is dangerous, because the buffers may change size between
two calls to PyObject_GetBuffer(). I think you should keep the
Py_buffers alive in an array, and only release them at the end (it may
also be slightly faster to do so).

A nit: you are adding a lot of newlines in test_bytes.py.

> I think you should keep the
> Py_buffers alive in an array, and only release them at the end (it may
> also be slightly faster to do so).

However allocation of this array may considerably slow down the function. We 
may need the special-case for bytes and bytearray. Stop, and the bytearray (or 
bytearray subclass) can change size between two calls to Py_SIZE()?

Here is a patch with tests.

Patch LGTM, however...

$ ./python -m timeit -s "a=[b'a']*100000"  "b','.join(a)"

Vanilla: 3.69 msec per loop
Patched: 11.6 msec per loop

> Patch LGTM, however...
> 
> $ ./python -m timeit -s "a=[b'a']*100000"  "b','.join(a)"
> 
> Vanilla: 3.69 msec per loop
> Patched: 11.6 msec per loop

True. It is a bit of a pathological case, though.

Here is a patch with restored performance. Is not it too complicated?

The problem with your approach is that the sequence could be mutated while another thread is running (_getbuffer() may release the GIL). Then the pre-computed size gets wrong.

> The problem with your approach is that the sequence could be mutated while
> another thread is running (_getbuffer() may release the GIL). Then the
> pre-computed size gets wrong.

Well, then I withdraw my patch.

But what if the sequence will be mutated and PySequence_Size(seq) will become 
less seqlen? Then using PySequence_Fast_GET_ITEM() will be incorrect.

> But what if the sequence will be mutated and PySequence_Size(seq) will become 
> less seqlen? Then using PySequence_Fast_GET_ITEM() will be incorrect.

Perhaps we should detect that case and raise, then.

Here is an updated patch using PySequence_Fast_GET_SIZE to avoid problems when the sequence is resized during iteration.

Here is a new patch checking that the sequence size didn't change. I also refactored the join() implementation into a shared function in stringlib.

I added new comments. :-(

> I added new comments. :-(

Thanks. I think I will commit after adding the missing #undef :-)

New changeset 16285c1b4dda by Antoine Pitrou in branch 'default':
Issue #15958: bytes.join and bytearray.join now accept arbitrary buffer objects.
http://hg.python.org/cpython/rev/16285c1b4dda

Done now.

Well done.

However check at top of Objects/stringlib/join.h does not protect from using 
the file with asciilib or ucs1lib.

> However check at top of Objects/stringlib/join.h does not protect from using 
> the file with asciilib or ucs1lib.

I'm not sure that's a problem. Someone would have to go out of their way
to use join.h with only UCS1 unicode strings. Also tests would probably
start failing, since str.join doesn't have the right signature :-)

Yet one issue. You forgot to add join.h to BYTESTR_DEPS in Makefile.pre.in.

New changeset 388e43bb519d by Antoine Pitrou in branch 'default':
Followup to issue #15958: add join.h to Makefile dependencies for byte strings
http://hg.python.org/cpython/rev/388e43bb519d