Idle: make 3.x HyperParser work with non-ascii identifiers.

[terryjreedy]

BPO	21765
Nosy	@malemburg, @loewis, @terryjreedy, @taleinat, @ezio-melotti
Dependencies	bpo-21686: IDLE - Test hyperparser
Files	taleinat.20140706.IDLE_HyperParser_unicode_ids.patch taleinat.20140716.IDLE_HyperParser_unicode_ids_v2.patch: first fix + tests

^{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/terryjreedy'
closed_at = <Date 2014-07-16.17:57:41.453>
created_at = <Date 2014-06-14.23:12:54.961>
labels = ['expert-IDLE', 'type-bug']
title = 'Idle: make 3.x HyperParser work with non-ascii identifiers.'
updated_at = <Date 2019-03-23.04:14:49.716>
user = 'https://github.com/terryjreedy'

bugs.python.org fields:

activity = <Date 2019-03-23.04:14:49.716>
actor = 'terry.reedy'
assignee = 'terry.reedy'
closed = True
closed_date = <Date 2014-07-16.17:57:41.453>
closer = 'terry.reedy'
components = ['IDLE']
creation = <Date 2014-06-14.23:12:54.961>
creator = 'terry.reedy'
dependencies = ['21686']
files = ['35876', '35960']
hgrepos = []
issue_num = 21765
keywords = ['patch']
message_count = 27.0
messages = ['220593', '220594', '220613', '220614', '220621', '220626', '221066', '221158', '221161', '221165', '221172', '221184', '221236', '221238', '221267', '221279', '222418', '222454', '222457', '222726', '222739', '222767', '223150', '223191', '223199', '223202', '256487']
nosy_count = 6.0
nosy_names = ['lemburg', 'loewis', 'terry.reedy', 'taleinat', 'ezio.melotti', 'python-dev']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue21765'
versions = ['Python 3.4', 'Python 3.5']

[terryjreedy]

idlelib.HyperParser.Hyperparser has these lines
_whitespace_chars = " \t\n\\"
_id_chars = string.ascii_letters + string.digits + "_"
_id_first_chars = string.ascii_letters + "_"
used in _eat_identifier() and get_expression. At least the latter two should be turned into functions that access the unicode datebase. (Such functions, if not already present in the stdlib, should be. But adding something elsewhere would be another issue.)

[terryjreedy]

bpo-21686 adds the test file that a new test would go in.

[taleinat]

It seems that the unicodedata module already supplies relevant functions which can be used for this. For example, we can replace "char in self._id_first_chars" with something like:

from unicodedata import normalize, category
norm_char = normalize(char)[0]
is_id_first_char = norm_char_first == '_' or category(norm_char_first) in {"Lu", "Ll", "Lt", "Lm", "Lo", "Nl"}

I'm not sure what the "Other_ID_Start property" mentioned in [1] and [2] means, though. Can we get someone with more in-depth knowledge of unicode to help with this?

The real question is how to do this *fast*, since HyperParser does a *lot* of these checks. Do you think caching would be a good approach?

See:
.. [1]: https://docs.python.org/3/reference/lexical_analysis.html#identifiers
.. [2]: http://legacy.python.org/dev/peps/pep-3131/

[taleinat]

Bah, I messed up the code sample in my previous message. It was supposed to be:

from unicodedata import normalize, category
norm_char_first = normalize(char)[0]
is_id_first_char = (
    norm_char_first == '_' or
    category(norm_char_first) in {"Lu", "Ll", "Lt", "Lm", "Lo", "Nl"}
)

[terryjreedy]

I checked for usage: _id(_first)_chars is only used in _eat_identifier, which is used in one place in get_expression. That is called once each in AutoComplete and CallTips. Both are seldom visible accept as requested (by waiting, for calltips). Calltips is only called on entry of '('. Is AutoComplete doing hidden checks?

_eat_identifier currently does a linear 'c in string' scan of the 2 char strings. I believe that both are long enough that O(1) 'c in set' checks would be faster. The sets could be augmented with latin1 id chars without becoming hugh or slowing the check (see below). This is a change we could make as soon as the test file and new failing tests are ready.

I just discovered, new in 3.x, str.isidentifier.
>>> '1'.isidentifier()
False
>>> 'a'.isidentifier()
True
>>> '\ucccc'
'쳌'
>>> '\ucccc'.isidentifier()
True

This is, however, meant to be used in the forward direction. If s[pos].isidentifier(), check s[pos:end].identifier(), where end is progressively incremented until the check fails. For backwards checking, it could be used with a start char prefixed: ('a'+s[start:pos]).isidentifier(). To limit the cost, the start decrement could be 4 chars at a time, with 2 extra tests (binary search) on failure to find the actual start.

The 3.x versions of other isxyg functions could be useful: isalpha, isdecimal, isdigit, isnumeric. We just have to check their definitions against the two identifier class definitions.

What is slightly annoying is that in CPython 3.3+, all-ascii strings are marked as such but the info is not directly accessible without without ctypes. I believe all-latin-1 strings can be detected by comparing sys.getsizeof(s) to len(s), so we could augment the char sets to include the extra identifier chars in latin-1.

We could add a configuation option to assume all-ascii (or better, all-latin1 code chars or not, and note that 'all latin1' will run faster but not recognize identifiers for the two features that use this.

[taleinat]

AutoComplete isn't doing hidden checks. My concern is that auto-completion happens automatically and the parsing is done synchronously, so if the parsing takes a significant amount of time it can cause a delay long enough to be noticeable by users. We should also consider the IDLE is being used on some relatively weak computers, such as Raspberry Pi. I have one for testing if needed!

Your suggestion of jumping backwards several characters at a time and calling isidentifier() seems problematic. For example, how would it deal with something like "2fast2furious"? Recognizing "fast2furious" as the identifier candidate is incorrect, but that's what we'd get with a straightforward implementation of your suggestion. I can't think of a way to get this right without be able to check if each character is valid for identifiers.

I still think the category(normalize(char)[0]) in {...} approach could be just fine. I'd really like to get feedback from an expert on unicode. The experts index lists three people as experts on unicodedata; I've added them to the nosy for this issue.

Once we have an identifier candidate, the code currently just checks that the first char is valid and that the identifier isn't a keyword. We probably should use str.isidentifier() instead of just checking the first character.

[ezio-melotti]

I'm not sure what the "Other_ID_Start property" mentioned in [1] and
[2] means, though. Can we get someone with more in-depth knowledge of
unicode to help with this?

See http://www.unicode.org/reports/tr31/#Backward_Compatibility.
Basically they were considered valid ID_Start characters in previous versions of Unicode, but they are no longer valid. I think it's safe to leave them out (perhaps they could/should be removed from the Python parser too), but if you want to add them the list includes only 4 characters (there are 12 more for Other_ID_Continue).

The real question is how to do this *fast*, since HyperParser does a
*lot* of these checks. Do you think caching would be a good approach?

I think it would be enough to check explicitly for ASCII chars, since most of them will be ASCII anyway. If they are not ASCII you can use unicodedata.category (or .isidentifier() if it does the right thing).

[taleinat]

Alright, so I'm going to use the equivalent of the following code, unless someone can tell me that something is wrong:

from keyword import iskeyword
from unicodedata import category, normalize

_ID_FIRST_CATEGORIES = {"Lu", "Ll", "Lt", "Lm", "Lo", "Nl",
                        "Other_ID_Start"}
_ID_CATEGORIES = _ID_FIRST_CATEGORIES | {"Mn", "Mc", "Nd", "Pc",
                                         "Other_ID_Continue"}

_ASCII_ID_CHARS = set(string.ascii_letters + string.digits + "_")
_ID_KEYWORDS = {"True", "False", "None"}

def is_id_char(char):
    return char in _ASCII_ID_CHARS or (
        ord(char) >= 128 and
        category(normalize(char)[0]) in _ID_CATEGORIES
    )

def is_identifier(id_candidate):
    return id_candidate.isidentifier() and (
        (not iskeyword(id_candidate)) or
        id_candidate in _ID_KEYWORDS
    )

 def _eat_identifier(str, limit, pos):
    i = pos
    while i > limit and is_id_char(str[pos - i]):
        i -= 1
    if i < pos and not is_identifier(str[i:pos]):
        return 0
    return pos - i

[ezio-melotti]

_ID_FIRST_CATEGORIES = {"Lu", "Ll", "Lt", "Lm", "Lo", "Nl",
"Other_ID_Start"}
_ID_CATEGORIES = _ID_FIRST_CATEGORIES | {"Mn", "Mc", "Nd", "Pc",
"Other_ID_Continue"}

Note that "Other_ID_Start" and "Other_ID_Continue" are not categories -- they are properties -- and that unicodedata.category() won't return them, so adding them to these set won't have any effect. I don't think there's a way to check if chars have that property, but as I said in my previous message it's probably safe to ignore them (nothing will explode even in the unlikely case that those chars are used, right?).

def is_id_char(char):
return char in _ASCII_ID_CHARS or (
ord(char) >= 128 and

What's the reason for checking if the ord is >= 128?

   category(normalize(char)[0]) in \_ID_CATEGORIES

)

[loewis]

The Other_ID_Start property is defined in

http://www.unicode.org/Public/UCD/latest/ucd/PropList.txt

It currently includes 4 characters.

However, I would propose that methods .isidstart and .isidcontinue get added to the str type if there is a need for them.

[taleinat]

What's the reason for checking if the ord is >= 128?

It's an optimization. Assuming the majority of characters will be ASCII, most non-identifier characters will fail this test, thus avoiding the more involved generic Unicode check.

However, I would propose that methods .isidstart and
.isidcontinue get added to the str type if there is a
need for them.

I was surprised to find .isidentifier() is a method of the str type. Even if that is considered useful enough to be a method of str, I don't think the functions you suggest are generally useful enough to warrant being added as methods.

Then again, I'm no authority on decided what gets included as methods of base types. Regardless, I'd rather this patch go in without affecting str; adding these methods to str is a separate issue. If someone decides to pursue that, feel free to use this code and/or +nosy me.

[ezio-melotti]

It's an optimization. Assuming the majority of characters will be
ASCII, most non-identifier characters will fail this test, thus
avoiding the more involved generic Unicode check.

I don't know what kind of characters are usually received as input. If things like (ASCII) spaces, parentheses, commas are common, then the optimization is probably OK.

@martin
Do you know the reason why characters with the Other_ID_Start have been included in the first place, given that they are no longer considered valid identifiers and I can hardly think any situation where someone would need it? Could they be removed from 3.5 if that makes the code simpler?

[loewis]

The reason the Unicode consortium made this list (Other_ID_Start) is that they want to promise 100% backwards compatibility: if some programming language had been using UAX#31, changes to the Unicode database might break existing code. To avoid this, UAX#31 guarantees 100% stability.

The reason Python uses it is because it uses UAX#31, with the minimum number of modifications. We really shouldn't be making arbitrary changes to it. If we would e.g. say that we drop these four characters now, the next Unicode version might add more characters to Other_ID_Start, and then we would have to say that we include some, but not all, characters from Other_ID_Start.

So if IDLE wants to reimplement the XID_Start and XID_Continue properties, it should do it correctly. Note that the proposed patch only manages to replicate the ID_Start and ID_Continue properties. For the XID versions, see

http://www.unicode.org/reports/tr31/#NFKC_Modifications

Unfortunately, the specification doesn't explain exactly how these modifications are performed. For item 1, I think it is:

Characters which are in ID_Start (because they count as letters) but their NFKC decomposition does not start with an ID_Start character (because it starts with a modifier instead) are removed in XID_Start

For item 2, they unfortunately don't list all characters that get excluded. For the one example that they do give, the reason is clear: U+037A (GREEK YPOGEGRAMMENI, category Lm) decomposes to U+0020 (SPACE) U+0345 (COMBINING GREEK YPOGEGRAMMENI). Having a space in an identifier is clearly out of the question. I assume similar problems occur with "certain Arabic presentation forms". I wish the consortium was more explicit as to what precise algorithms they use to derive their derived properties.

[loewis]

Tal: If you want to verify your is_id_char function, you could use the code

for i in range(65536):
    c = chr(i)
    c2 = 'a'+c
    if is_id_char(c) != c2.isidentifier():
        print('\\u%.4x'%i,is_id_char(c),c2.isidentifier())

Alternatively, you could use the strategy taken in that code for is_id_char itself:

def is_id_char(c):
  return ('a'+c).isidentifier()