{"action":"created","issue":{"url":"https://api.github.com/repos/google/xi-editor/issues/565","repository_url":"https://api.github.com/repos/google/xi-editor","labels_url":"https://api.github.com/repos/google/xi-editor/issues/565/labels{/name}","comments_url":"https://api.github.com/repos/google/xi-editor/issues/565/comments","events_url":"https://api.github.com/repos/google/xi-editor/issues/565/events","html_url":"https://github.com/google/xi-editor/issues/565","id":306668110,"number":565,"title":"Width measurement","user":{"login":"raphlinus","id":242367,"avatar_url":"https://avatars3.githubusercontent.com/u/242367?v=4","gravatar_id":"","url":"https://api.github.com/users/raphlinus","html_url":"https://github.com/raphlinus","followers_url":"https://api.github.com/users/raphlinus/followers","following_url":"https://api.github.com/users/raphlinus/following{/other_user}","gists_url":"https://api.github.com/users/raphlinus/gists{/gist_id}","starred_url":"https://api.github.com/users/raphlinus/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/raphlinus/subscriptions","organizations_url":"https://api.github.com/users/raphlinus/orgs","repos_url":"https://api.github.com/users/raphlinus/repos","events_url":"https://api.github.com/users/raphlinus/events{/privacy}","received_events_url":"https://api.github.com/users/raphlinus/received_events","type":"User","site_admin":false},"labels":[{"id":364706586,"url":"https://api.github.com/repos/google/xi-editor/labels/enhancement","name":"enhancement","color":"84b6eb","default":true}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":6,"created_at":"2018-03-19T22:56:20Z","updated_at":"2018-03-23T00:02:05Z","closed_at":null,"author_association":"COLLABORATOR","body":"This is the tracking issue for width measurement in xi-editor, and something of a design document and list of concerns.\r\n\r\n## Introduction\r\n\r\nA number of editing operations require some concept of width. Probably the most important is word wrap (see #58 for more issues regarding improving word wrapping). Currently, utf-8 code unit count is used as a stand-in for all width operations, but results are poor, as these only loosely correlate (issue #501 describes the consequences in more detail, giving examples).\r\n\r\nOther operations that require width include:\r\n\r\n* Computing a location within a line with similar horizontal positioning, for up/down 1 line and similar movements. (This is represented in `SelRegion::horiz`)\r\n\r\n* Computing the entire-document width, as one alternate for horizontal scrolling (google/xi-mac#145, #479).\r\n\r\n* Expansion of tab stops. (It's not obvious yet whether these will be expanded in the front-end or core, see #467).\r\n\r\n* Column indicator in status UI.\r\n\r\n## Statement of the problem\r\n\r\nFor the purposes of word wrapping, the fundamental problem is to compute the width of a string, with merged attributes, in the current font and font size choice selected in the front-end. The task of word wrapping is then defined as choosing, for each line, the last line break opportunity that satisfies the constraint that the width of the line (ie substring from the previous break to this break) is less than or equal to the wrap width. (As a detail, trailing space is not included in this width calculation)\r\n\r\nIn general, width measurement is not a homomorphism, ie for strings A and B, width(A + B) is not width(A) + width(B). However, for the purposes of efficiency, we will assume in some cases that it's close. In particular, if a line break opportunity exists between A and B, then we can assume the widths are independent. In some cases, this might lead to incorrect line breaks, but the amount of mismeasurement is likely to be modest.\r\n\r\nHorizontal positioning within a line is much trickier to solve exactly, as the positioning of carets within a word is subject to ligatures (fonts sometimes have a ligature caret table, but this is something of an advanced feature). In addition, it requires solving the inverse problem (resolving a width to an offset within the string). As a simplification and performance improvement, I suggest the approximation of assuming that each grapheme cluster within the word has the same width. The consequence of mismeasurement should be pretty modest; it will lead to the cursor \"wiggling\" left and right a bit more on repeated up/down arrow key requests. Note that in the general (non-monospace) case there is already nonzero wiggle as the position needs to be rounded to the nearest grapheme cluster boundary in any case.\r\n\r\nNote that the front-end needs to solve the precise version of this problem to display a caret, and to resolve a click or touch gesture to a position within the string. These cases require precision, and I do not propose using an approximation; it is strictly for computations within the core.\r\n\r\n## Performence: RPC, caching\r\n\r\nThe core needs width measurement, but the front-end is the most natural place for the calls to the underlying text engine, as the front-end needs to do text layout as part of its text rendering.\r\n\r\nEven without the core/front-end separation, text measurement tends to be a slow operation. Every word (more precisely, every substring between consecutive break opportunities) needs to be measured, so the number of measurement opporunities is potentially large. One blocking RPC per word would have unacceptable performance. We can and should employ a number of techniques to improve performance.\r\n\r\nFirst and foremost is a cache. It's likely cache effectiveness is high, and almost guaranteed in the case of re-wrapping a paragraph being edited (or when the wrap width is changed, as in the case of resizing a window). Android uses a simple heuristic for granularity of its word cache: whitespace, or a boundary between to CJK ideographs.\r\n\r\nSecond, we can use a fast-path for the simple case of a monospace font. This will be particularly effective for large files such as logs, but we should be careful not to rely on it too heavily, as it's not effective for complex scripts, emoji, or even non-monospace fonts for ASCII.\r\n\r\nThird, to reduce RPC overhead, we can apply a number of techniques. Without too much complexity we can batch requests (so each RPC is for an array of attributed words). Adding more complexity, we can pipeline, but the benefits are likely not strong.\r\n\r\nLastly, we could avoid RPC overhead by bundling the core and front-end into the same process and making width measurement a procedure call, see #439 for the prerequisite issue. I believe this should be an optional performance optimization rather than a requirement (for isolation/robustness reasons and to make it easier to stand up a new front-end), but after gaining empirical experience we can decide that RPC overhead is minimal, unacceptable, or somewhere in between.\r\n\r\n## Other details\r\n\r\nThe RPC call should be based on the style id (`set-style` in the core to front-end update protocol). If we do libxi, then we probably need to move `set-style` calls to procedure calls also, to prevent the possibility of the width measurement request being reordered before the dependent style definition by RPC transport asynchrony.\r\n\r\n## \"Columns\"\r\n\r\nIt is common UI in editors to show a \"line/column\" indication. For ASCII (or even ISO 8859-1), the units are clear, but for complex scripts and emoji, it's not clear how columns should be counted.\r\n\r\nSublime Text counts Unicode codepoints. While it's a clear metric, it's not always satisfying, as any grapheme made from multiple codepoints counts as multiple columns.\r\n\r\nWe don't currently have this feature, but it is likely to be requested. One approach is to use measured width divided by the width of a \"nominal\" character.\r\n"},"comment":{"url":"https://api.github.com/repos/google/xi-editor/issues/comments/375496526","html_url":"https://github.com/google/xi-editor/issues/565#issuecomment-375496526","issue_url":"https://api.github.com/repos/google/xi-editor/issues/565","id":375496526,"user":{"login":"vlovich","id":201287,"avatar_url":"https://avatars0.githubusercontent.com/u/201287?v=4","gravatar_id":"","url":"https://api.github.com/users/vlovich","html_url":"https://github.com/vlovich","followers_url":"https://api.github.com/users/vlovich/followers","following_url":"https://api.github.com/users/vlovich/following{/other_user}","gists_url":"https://api.github.com/users/vlovich/gists{/gist_id}","starred_url":"https://api.github.com/users/vlovich/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vlovich/subscriptions","organizations_url":"https://api.github.com/users/vlovich/orgs","repos_url":"https://api.github.com/users/vlovich/repos","events_url":"https://api.github.com/users/vlovich/events{/privacy}","received_events_url":"https://api.github.com/users/vlovich/received_events","type":"User","site_admin":false},"created_at":"2018-03-23T00:02:05Z","updated_at":"2018-03-23T00:02:05Z","author_association":"COLLABORATOR","body":"Hmm... regarding the movement, I'm still not sure I understand.  I agree that measured width is probably correct as it gives correct behaviour regardless of fonts.  I think my point is that wouldn't the FE be able to do the translation of measured width -> abstract backend cursor position -> notify BE of the desired location?  I'm not sure I get why the BE needs to support cursor movement in terms of measured width only to have to need to query the FE for the width instead of doing the measured width directly.\r\n\r\nRE line-wrapping, I understand your point now much better & I 100% agree with your decision.  That being said, I'm not 100% convinced it needs measured width.  I think it ties into how we do columns.  For programming use-cases, width is typically defined in terms of # of columns & it feels natural this is independent of font width.  For WYSIWG document editors I agree line wrapping based on measured width makes more sense since the line-wrapping is page width.  For regular text editing, it's probably also measured width based if you wrap to the window.  I think it might help to clarify Xi's priorities for code editing vs general text editing vs WYSIWG editors, but having thought about this more I understand why a measured width RPC protocol would be needed so we could support wrapping to window.\r\n\r\nFor document load I think I just didn't understand what you were saying.  Am I correct in saying that you want to compute the hscroll width based on measured width instead of glyph counts?  In that case I understand the need for the BE to request the FE to measure the width."}}
{"actor":{"display_login":"vlovich"}}