Clarify status of O(1) indexing semantics of str objects

[ncoghlan]

BPO	21667
Nosy	@gvanrossum, @ncoghlan, @pitrou, @vstinner, @Rosuav, @JimJJewett, @serhiy-storchaka
Files	issue21667_clarify_str_specification.rst: Add indexing note, remove inaccurate references to "characters"

^{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 = None
closed_at = <Date 2014-06-07.13:26:31.044>
created_at = <Date 2014-06-05.11:02:22.888>
labels = ['type-feature', 'docs']
title = 'Clarify status of O(1) indexing semantics of str objects'
updated_at = <Date 2014-06-10.23:20:46.669>
user = 'https://github.com/ncoghlan'

bugs.python.org fields:

activity = <Date 2014-06-10.23:20:46.669>
actor = 'Jim.Jewett'
assignee = 'docs@python'
closed = True
closed_date = <Date 2014-06-07.13:26:31.044>
closer = 'ncoghlan'
components = ['Documentation']
creation = <Date 2014-06-05.11:02:22.888>
creator = 'ncoghlan'
dependencies = []
files = ['35489']
hgrepos = []
issue_num = 21667
keywords = []
message_count = 20.0
messages = ['219793', '219794', '219795', '219796', '219797', '219798', '219799', '219800', '219801', '219802', '219805', '219809', '219810', '219811', '219812', '219824', '219936', '219937', '220208', '220211']
nosy_count = 9.0
nosy_names = ['gvanrossum', 'ncoghlan', 'pitrou', 'vstinner', 'docs@python', 'python-dev', 'Rosuav', 'Jim.Jewett', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'later'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue21667'
versions = ['Python 3.4', 'Python 3.5']

[ncoghlan]

Based on the recent python-dev thread, I propose the following "CPython implementation detail" note in the "Strings" entry of https://docs.python.org/3/reference/datamodel.html#objects-values-and-types

"CPython currently guarantees O(1) access to arbitrary code points when indexing and slicing a string. Python implementations are required to index and slice strings as arrays of code points, but are not required to guarantee O(1) access to arbitrary locations within the string. This allows implementations to use variable width encodings for their internal string representation."

[vstinner]

str[a:b] returns a substring (characters), not an array of code points (numbers).

[ncoghlan]

Guido, I think we need your call on whether or not to add a note about string indexing algorithmic complexity to the language reference, and to approve the exact wording of such a note (my proposed wording is in my initial comment on this issue).

[ncoghlan]

No, Python doesn't expose Unicode characters in its data model at all, except in those cases where a code point happens to correspond directly with a character. A length 1 str instance represents a Unicode code point, not a Unicode character.

[ncoghlan]

Although, you're right, that section of the data model docs misuses the word "character" to mean something other than what it means in the Unicode spec :(

[vstinner]

"Python implementations are required to ..."

By the way, Python < 3.3 doesn't implement this requirement :-)

[ncoghlan]

Saying that ord() and chr() switch between characters and code points is just plain wrong, since characters may be represented as multiple code points.

We may also want to explicitly note that the Unicode normalisation is implementation dependendent, and that CPython doesn't normalise implicitly except where specifically noted (i.e. during lexical analysis).

[ncoghlan]

Right, narrow builds have long been broken - that's a large part of why this is now the requirement :)

[ncoghlan]

Patch attached that also addresses the characters vs code points confusion.

[ncoghlan]

I ducked the Unicode normalisation question for now, since that's a *different* can of worms :)

[pitrou]

Two things:

• I don't think it's very helpful to use the term "code point" without explaining or introducing it ("character" at least can be understood intuitively)
• The mention of slicing is ambiguous: is slicing suppoded to be O(1)? how is indexing related to slicing?

[ncoghlan]

If someone doesn't understand what "Unicode code point" means, that's going to be the least of their problems when it comes to implementing a conformant Python implementation. We could link to http://unicode.org/glossary/#code_point, but that doesn't really add much beyond "value from 0 to 0x10FFFF". If you try to dive into the formal Unicode spec instead, you end up in a twisty maze of definitions of things that are all closely related, but generally not the same thing (code positions, code units, code spaces, abstract characters, glyphs, graphemes, etc).

The main advantage of using the more formal "code point" over the informal "character" is that it discourages people from assuming they know what they are (with the usual mistaken assumption being that Unicode code points correspond directly to glyphs the way ASCII and Extended ASCII printable characters correspond to their glyphs). The rest of the paragraph then provides the mechanical details of the meaningful interpretations of them in Python (as length 1 strings and as numbers in a particular range) and the operations for translating between those two formats (chr and ord).

Fair point about the slicing - it may be better to just talk about indexing.

[pitrou]

Not sure what implementing a conformant Python implementation has to do with this; the language specification should be readable by any interested programmers, IMO.

If you try to dive into the formal Unicode spec instead, you end up
in a twisty maze of definitions of things that are all closely
related, but generally not the same thing (code positions, code units,
code spaces, abstract characters, glyphs, graphemes, etc).

That makes all the less useful to use the "proper term" instead of the more intuitive alternative :-)