Re: Fwd: Unicode offset calculations

Hello Frederik,

This is an old, well-known issue. As a starter, please have a look at 
what the Character Model has to say about this:

http://www.w3.org/TR/charmod/#sec-stringIndexing

Please feel free to come back again here or contact the I18N WG.

Regards,   Martin.

On 2015/04/29 21:45, Frederick Hirsch wrote:
> TAG members - has the issue of dealing with symbols vs characters/codepoints come up in TAG discussion?
>
> Any comment/suggestion welcome  (I've cross-posted intentionally, please remove recipients if not appropriate.)
>
> Thanks
>
> regards, Frederick
>
> Frederick Hirsch
> Co-Chair, W3C Web Annotation WG
>
> www.fjhirsch.com <http://www.fjhirsch.com/>
> @fjhirsch
>
>> Begin forwarded message:
>>
>> From: "Nick Stenning" <nick@whiteink.com>
>> Subject: Unicode offset calculations
>> Date: April 29, 2015 at 4:38:34 AM EDT
>> To: public-annotation@w3.org
>> Resent-From: public-annotation@w3.org
>>
>> One of the most useful discussions at our working group F2F last week was the result of a question from Takeshi Kanai about how we calculate character offsets such as those used by Text Position Selector <http://www.w3.org/TR/annotation-model/#text-position-selector> in the draft model. Specifically, if I have a selector such as
>>
>> {
>>    "@id": "urn:uuid:...",
>>    "@type": "oa:TextPositionSelector",
>>    "start": 478,
>>    "end": 512
>> }
>> to what do the numbers 478 and 512 refer? These numbers will likely be interpreted by other components specified by this WG (such as the RangeFinder API), not to mention external systems, and we need to make sure we are consistent in our definitions across these specifications.
>>
>> I've reviewed what the model spec currently says and I'm not sure it's particularly precise on this point. Even if I'm misreading it and it is clear, I'm not sure it makes a recommendation that is practical. In order to review this, I'm going to first lay out the possible points of ambiguity, and then review what the spec seems to say on these issues.
>>
>> 1. A symbol is not (necessarily) a codepoint
>>
>> The atom of selection in the browser is the symbol, or grapheme. For example, "ą́" is composed of three codepoints, but is rendered as a single selectable symbol. It can only be unselected or selected: there is no way to only select some of the codepoints that comprise the symbol.
>>
>> Because user selections start and end at symbols, it would be reasonable for TextPositionSelector offsets to be defined as symbol counts. Unfortunately, most extant DOM APIs don't deal in symbols:
>>
>>> var p = document.createElement('p')
>>> p.innerText = 'ą́'
>>> p.innerText.length
>> 3
>>> p.firstChild.splitText(1)
>>> p.firstChild.nodeValue
>> '\u0061'
>>> p.firstChild.nextSibling.nodeValue
>> '\u0328\u0301'
>> Calculating how a sequence of codepoints maps to rendered symbols is in principle complicated <http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries> and in practice not completely standardised across rendering engines. It's also (as demonstrated with splitText above) possible for the DOM to end up in a state in which the mapping between textual content and rendered symbols has become decoupled.
>>
>> 2. Combining characters
>>
>> Some sequences of codepoints can render identically to other sequences of codepoints. For example:
>>
>> ñ (U+00F1 LATIN SMALL LETTER N WITH TILDE)
>> renders identically to
>>
>> ñ (U+006E LATIN SMALL LETTER N + U+0303 COMBINING TILDE)
>> This is the "combining characters" problem. Some codepoints are used to modify the appearance of preceding codepoints. Selections made on a document containing one of these would behave identically to selections made on a document containing the other, but:
>>
>>> 'ñ'.length
>> 1
>>> 'ñ'.length
>> 2
>> This is not an insoluble problem, as the Unicode specification itself defines a process by which sequences of codepoints can be canonicalised into fully decomposed (aka "NFD") or fully composed (aka "NFC") form. But it's not that simple, because if we specify a canonicalisation requirement for annotation selector offsets, then there may be undesirable performance implications (consider making an annotation at the end of a 100KB web page of unknown canonicalisation status).
>>
>> 3. Astral codepoints and JavaScript
>>
>> JavaScript's internal encoding of Unicode strings is based on UCS-2 <https://en.wikipedia.org/wiki/UTF-16#History>, which means that it represents codepoints from the so-called "astral planes" (i.e. codepoints above 0xFFFF) as two surrogate pairs. This leads to the principal problem that Takeshi identified, which is that different environments will calculate offsets differently. For example, in Python 3:
>>
>>>>> len('😀') # U+1F600 GRINNING FACE
>> 1
>> Whereas in JavaScript:
>>
>>> '😀'.length
>> 2
>> There are ways of addressing this problem in JavaScript, but to my knowledge none of them are particularly elegant, and none of them will allow us to calculate offsets at the bottom of a long document without scanning the entire preceding text for astral codepoints.
>>
>> So what does our spec currently say?
>>
>> The text must be normalized before counting characters. HTML/XML tags should be removed, character entities should be replaced with the character that they encode, unnecessary whitespace should be normalized, and so forth. The normalization routine may be performed automatically by a browser, and other clients should implement the DOM String Comparisons [DOM-Level-3-Core] method.
>>
>> It's not immediately clear what this means in terms of Unicode normalisation. Following the chain of specifications leads to §1.3.1 of the DOM Level 3 Core specification <http://www.w3.org/TR/DOM-Level-3-Core/core.html#DOMString>. The only thing this says about Unicode normalisation is:
>>
>> The character normalization, i.e. transforming into their fully normalized form as as defined in [XML 1.1], is assumed to happen at serialization time.
>>
>> This doesn't appear to be relevant, as the meaning of "serialization" in this context appears to refer to the mechanisms described in the DOM Load and Save <http://www.w3.org/TR/2004/REC-DOM-Level-3-LS-20040407/> spec, and does not refer to the process of parsing an HTML document and presenting its content through the DOM APIs. (I'd be very happy if someone more familiar with the DOM Level 3 Spec could confirm this interpretation.)
>>
>> For completeness, "fully normalized form" in the XML 1.1 sense <http://www.w3.org/TR/2004/REC-xml11-20040204/#dt-fullnorm> would appear to imply full "NFC" normalisation of the document. It is apparent even from the simple examples above that browsers do not apply NFC normalisation to documents they receive from the server.
>>
>> What should we do about all this?
>>
>> I've listed above three sources of confusion in talking about offsets. In each case there is tension between what would make the most sense to a user and a pragmatic engineering recommendation that takes into account contingent factors.
>>
>> Symbols: users can only select symbols in browsers, but as far as I'm aware all current internal DOM APIs ignore this fact. Further, given that determining the symbol sequence for a given codepoint sequence is non-trivial, we probably should not attempt to define offsets in terms of symbols.
>>
>> Combining characters: user selections make no distinction between combinatoric variants such as "ñ" and "n + ˜", so it would seem logical to define offsets in terms of the "NFC" canonicalised form. In practice, such a recommendation would likely be ignored by implementers (for reasons of complexity or performance impact), and so for the same reasons as in 1) I'd be inclined to suggest we define offsets in terms of the delivered document codepoint sequence rather than any canonical form.
>>
>> Astral codepoints + surrogate pairs: this is the tricky one. As demonstrated by this page <http://bl.ocks.org/nickstenning/bf09f4538878b97ebe6f>, this poses serious problems for interoperability, as JavaScript counts a single unicode astral codepoint as having length 2, due to the internal representation of the codepoint as a surrogate pair. As far as I'm concerned we're stuck between a rock and a hard place:
>>
>> a. calculating offsets in terms of codepoints (i.e. accounting for surrogate pairs in JavaScript) makes interoperability more likely, but could impose a substantial cost on client-side algorithms, both in terms of implementation complexity and performance impact.
>>
>> b. calculating offsets using native calculations on JavaScript strings is preferable from an implementation complexity standpoint, but as far as I'm aware no other mainstream programming environment has the same idiosyncrasy, thus almost guaranteeing problems of interoperability when offsets are used in both the DOM environment and outside.
>>
>> In summary, Takeshi raised an important question at the F2F. What do we do about JavaScript's rather unfortunate implementation of unicode strings? I'd be interested to hear from anyone with thoughts on this subject. I imagine there are people in the I18N activity at W3C who would be able to weigh in here too.
>>
>> -N
>>
>
>

Received on Thursday, 30 April 2015 00:58:58 UTC