cache rendered text on a11y side

RESOLVED FIXED in mozilla2.0b12

Status

()

Core
Disability Access APIs
RESOLVED FIXED
7 years ago
7 years ago

People

(Reporter: surkov, Assigned: surkov)

Tracking

({access})

unspecified
mozilla2.0b12
access
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(blocking2.0 betaN+)

Details

(Whiteboard: [hardblocker] for remaining work [has patch])

Attachments

(2 attachments, 2 obsolete attachments)

(Assignee)

Description

7 years ago
if AT gets text from accessible at unsafe time then we may crash similar to bug 615475. On the another hand this approach allows us to fire text change events based on rendered text.
Blocks: 615475
(Assignee)

Comment 1

7 years ago
try server build will be available here - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/surkov.alexander@gmail.com-43f3ab139915

It fixes bug 613058, bug 627647, bug 452599 and bug 567203. I suspect it fixes bug 452584 as well but haven't time to fix mochitests.

Note, it doesn't fix bug 612098 and bug 615475. I'll do this in follow ups.
(Assignee)

Comment 2

7 years ago
Created attachment 508096 [details] [diff] [review]
patch

I think to do some optimization before request a review
Assignee: nobody → surkov.alexander
Status: NEW → ASSIGNED
(Assignee)

Comment 3

7 years ago
Created attachment 508190 [details] [diff] [review]
patch2
Attachment #508096 - Attachment is obsolete: true
Attachment #508190 - Flags: superreview?(neil)
Attachment #508190 - Flags: review?(bolterbugz)
(Assignee)

Comment 4

7 years ago
(In reply to comment #3)
> Created attachment 508190 [details] [diff] [review]
> patch2

try server build will be here - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/surkov.alexander@gmail.com-3f097023ed64

Marco, I need your testing. Especially you should give an attention to editing.
(Assignee)

Comment 5

7 years ago
should be betaN blocking since we need beta triage for this bug
blocking2.0: --- → ?
(Assignee)

Updated

7 years ago
Depends on: 630001
(Assignee)

Updated

7 years ago
blocking2.0: ? → ---
(Assignee)

Updated

7 years ago
Blocks: 630001
No longer depends on: 630001
(Assignee)

Updated

7 years ago
Blocks: 630013
No longer blocks: 625653
(Assignee)

Comment 6

7 years ago
(In reply to comment #5)
> should be betaN blocking since we need beta triage for this bug

it blocks bug 613058 which is betaN+
Attachment #508190 - Flags: review?(bolterbugz) → review+
Comment on attachment 508190 [details] [diff] [review]
patch2

Woah, undoing accidental r+ (wrong window). I'll review this next.
Attachment #508190 - Flags: review+ → review?
Attachment #508190 - Flags: review? → review?(bolterbugz)
Comment on attachment 508190 [details] [diff] [review]
patch2

>+++ b/accessible/tests/mochitest/editabletext/editabletext.js

>-  this.insertText = function insertText(aStr, aPos, aResStr)
>+  this.insertText = function insertText(aStr, aPos, aResStr, aResPos)

What are aResStartPos, and aResEndPos? (Same with cutText)

>-    this.scheduleTest(aID, null, [aPos, aPos + aStr.length, aStr],
>+    var resPos = aResPos != undefined ? aResPos : aPos;

I'd prefer a change for readability like this:
var resEndPos = (aResEndPos != undefined) ? aResPos : aPos;

(in a few places).
Comment on attachment 508190 [details] [diff] [review]
patch2

>+++ b/accessible/src/base/nsAccessibilityService.cpp
>@@ -910,35 +910,32 @@ nsAccessibilityService::GetOrCreateAcces

>-    if (f && f->IsEmpty()) {

This worries me a little. How do we know we don't need to check the frame IsAlive?

>+    weakFrame->GetRenderedText(&text, nsnull, nsnull, 0, PR_UINT32_MAX);

>-    if (weakFrame.IsAlive()) {

This worries me a little.

>+    newAcc = weakFrame->CreateAccessible();
Reading up on Levenshtein :)
Did you get any talos/perf numbers back? The TextUpdater stuff looks O(n^2) of course, and hurts my brain.
(Assignee)

Comment 12

7 years ago
(In reply to comment #8)

> >-  this.insertText = function insertText(aStr, aPos, aResStr)
> >+  this.insertText = function insertText(aStr, aPos, aResStr, aResPos)
> 
> What are aResStartPos, and aResEndPos? (Same with cutText)

start and end offsets of text change event

(In reply to comment #9)
> Comment on attachment 508190 [details] [diff] [review]
> patch2
> 
> >+++ b/accessible/src/base/nsAccessibilityService.cpp
> >@@ -910,35 +910,32 @@ nsAccessibilityService::GetOrCreateAcces
> 
> >-    if (f && f->IsEmpty()) {
> 
> This worries me a little. How do we know we don't need to check the frame
> IsAlive?
> 
> >+    weakFrame->GetRenderedText(&text, nsnull, nsnull, 0, PR_UINT32_MAX);
> 
> >-    if (weakFrame.IsAlive()) {
> 
> This worries me a little.

we just got non-empty frame from weakFrame, that's the same with isAlive.
(Assignee)

Comment 13

7 years ago
(In reply to comment #11)
> Did you get any talos/perf numbers back? The TextUpdater stuff looks O(n^2) of
> course, and hurts my brain.

I run talos table test locally, TextEnumarate takes 0.91% weight vs 82.00% of Firefox. I wouldn't expect regressions on talos.
Comment on attachment 508190 [details] [diff] [review]
patch2

The second try build breaks caret navigation in GMail's WYSIWYG editor (embedded frame).
STR:
1. Log into GMail with nVDA running.
2. Hit the "Compose Mail" button.
3. Fill in an address, tab to subject and fill in, too. These two textfields work fine.
4. Tab into the mail body and start typing.
5. Try to review with arrow keys.

Result: Silence. No caret tracking.

6. Press tab once, then shift+tab.
7. In thi s instance, all text you type will be visible on the braille display, and a SayLine command (hit 8 on the number pad) will read it, but caret navigation will still not work.

Will now try the first try-server build as well and give feedback.

The nightly build of January 30 works fine.
Attachment #508190 - Flags: feedback-
The first of the try-server builds in this bug doesn't allow me to perform the above steps. It crashes consistently when loading the initial GMail interface after login. I have no chance to get to the composition window at all.
(Assignee)

Comment 16

7 years ago
The patch works fine with me. Pushing new try server build just in the case - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/surkov.alexander@gmail.com-923a2dc506e0
(Assignee)

Comment 17

7 years ago
Note, the patch doesn't change caret navigation events behavior, all it does is change the behavior text change events.
I imagine cutting or pasting large amounts of text is O(n)?
(Assignee)

Comment 19

7 years ago
(In reply to comment #18)
> I imagine cutting or pasting large amounts of text is O(n)?

yep, it should be 3n, where n is length of removed substring if I get right
Comment on attachment 508190 [details] [diff] [review]
patch2

This latest try-server build also works in gmail. Changing my Feedback to +. Also, I notice in other textareas and text fields greater responsiveness when typing. Recent builds were a bit sluggish at times, but this build is very fast indeed.
Attachment #508190 - Flags: feedback- → feedback+
(Assignee)

Comment 21

7 years ago
(In reply to comment #20)
> Comment on attachment 508190 [details] [diff] [review]
> patch2
> 
> This latest try-server build also works in gmail. Changing my Feedback to +.
> Also, I notice in other textareas and text fields greater responsiveness when
> typing. Recent builds were a bit sluggish at times, but this build is very fast
> indeed.

it's because of async processing one time instead of sync processing for each pressed key.
Comment on attachment 508190 [details] [diff] [review]
patch2

Let's get this landed.
Attachment #508190 - Flags: review?(bolterbugz) → review+
BTW:
You intended to hide these right? You could make explicit via naming:
TextUpdater(const NoCopying&);
TextUpdater& operator = (const NoCopying&);
(Assignee)

Comment 24

7 years ago
(In reply to comment #23)
> BTW:
> You intended to hide these right? You could make explicit via naming:
> TextUpdater(const NoCopying&);
> TextUpdater& operator = (const NoCopying&);

It's just protection at compiling level. I don't think anybody will need to copy it.
Fair enough.
(Assignee)

Comment 26

7 years ago
Neil, I need to land this patch today to get a beta triage. So it may be not enough time for you to do a review. But it's very important to get it. If I go ahead to land it and you finish review after landing then would it work for you? I will fix all your comments as following up bug.
(Assignee)

Comment 27

7 years ago
landed on 2.0 beta11 - http://hg.mozilla.org/mozilla-central/rev/7a5f8241cfa4

keeping open, looking forward for post Neil review.
(Assignee)

Updated

7 years ago
Target Milestone: --- → mozilla2.0b11
Comment on attachment 508190 [details] [diff] [review]
patch2

Since all of my nits are code style/efficiency nits, I'll grant sr+, but you might want to follow up on some of them anyway.

>+private:
>+  TextUpdater();
Nit: There is no compiler-generated null constructor, so you don't have to make it priviate.

>+  void FindDiffNFireEvents(const nsDependentSubstring& aStr1,
>+                           const nsDependentSubstring& aStr2,
Nit: prefer to use const nsAString& if possible.

>+  PRUint32 minLen = oldLen < newLen ? oldLen : newLen;
NS_MIN would make the code clearer in several places!

>+  // Trim coinciding substrings from the end.
It might be easier to write
PRUint32 skipEnd = 0;
while (aNewText[newLen - skipEnd - 1] == oldText[oldLen - skipEnd - 1])
  skipEnd++;

const nsDependentSubstring& str1 =
  Substring(oldText, skipStart, oldLen - skipStart - skipEnd);
const nsDependentSubstring& str2 =
  Substring(aNewText, skipStart, newLen - skipStart - skipEnd);

>+  PRUint32** matrix = new PRUint32*[len1];
>+  for (PRUint32 i = 0; i < len1; i++)
>+    matrix[i] = new PRUint32[len2];
It's slightly more efficient to allocate all the entries in one go i.e.
PRUint32* entries = new PRUint32*[len1 * len2];
And then you can slice this up into rows.
Physically:
for (PRUint32 i = 0; i < len1; i++) {
  matrix[i] = entries + i * len2;
  matrix[i][0] = i;
}
Or logically, by using the formula matrix[i][j] = entries[i * len2 + j]
Or via strength reduction, because you consider each cell in turn, so that matrix[i][j] = *cell, matrix[i][j - 1] = *(cell - 1), matrix[i - 1][j] = *(cell - len2) etc. Or maybe two pointers, one pointing to [i][j] and one to [i - 1][j - 1], because you use those two the most. Although on the x86 it's actually probably slightly more efficient to keep pointers to the current and the previous row, since it has these clever opcodes that allow you to do row[j - 1] in a single instruction.

>+  for (PRUint32 i = 1; i < len1; i++) {
Rather than have two separate "i" loops, you can put both sets of code in one loop, as you don't need to know matrix[i][0] = i before the "i"th loop.

>+  while (i >= 0 && j >= 0) {
>+    if (aMatrix[i][j] == 0) {
Because you trimmed the common prefix, only aMatrix[0][0] will be zero.

>+      // substitution
>+    // move up, insertion
>+    // move left, removal
The Levenshtein Distance does not provide a unique least cost solution if there is a mixture of orthogonal and diagonal edits. So after finding a substitution, you should ideally move as much as you can until you run out of edits, and then notify on the insertion and deletion. Example: for the edit from "meilenstein" to "levenshtein" there is a substitution from "m" to "l", a substitution from "il" to "v", and an insertion of "h". However this code appears to fire a substitution from "m" to "l", a deletion of "i", a substitution from "l" to "v" and an insertion of "h". You get the bonus of not having to build up the text strings as you can just keep the positions of the last match. And you even get to stop as soon as either i or j hits zero since that just means that the rest of the old/new string is part of the last substitution/insertion/deletion.

>+  NS_ASSERTION(hyperText, "Text leaf parnet is not hyper text!");
parent
Attachment #508190 - Flags: superreview?(neil) → superreview+

Comment 29

7 years ago
Is this supposed to be nominated for 2.0? Can we get the blocking flag set if it's indeed a blocker.
(In reply to comment #29)
> Is this supposed to be nominated for 2.0? Can we get the blocking flag set if
> it's indeed a blocker.

Sure. We need beta coverage so blockingN+. It blocks 11 open bugs including blockers. We're full steam ahead and have made a landing that we hope sticks; with some perf followup possible.
blocking2.0: --- → betaN+
(Assignee)

Comment 31

7 years ago
(In reply to comment #28)

> >+private:
> >+  TextUpdater();
> Nit: There is no compiler-generated null constructor, so you don't have to make
> it priviate.

There is no it while there's non null constructor? That doesn't harm if I keep it private, right? I would have it just to keep things explicitly.

> >+  for (PRUint32 i = 1; i < len1; i++) {
> Rather than have two separate "i" loops, you can put both sets of code in one
> loop, as you don't need to know matrix[i][0] = i before the "i"th loop.

Is row and cell index calculation on each loop preferable than two loops like:
PRUint32 size = len1 * len2;
for (PRUint32 i = 1; i < size; i++) {
  PRUint32 rowIdx = i % len1;
  PRUint32 colIdx = i - rowIdx * len1;
  if (str1[rowIdx - 1] == str2[colIdx - 1])
}

or should I have something like 

for (PRUint32 i = 1, colIdx = 0, rowIdx = 0; i < size; i++) {
  if (str1[rowIdx - 1] == str2[colIdx - 1])
  if (++colIdx == len2) {
    colIdx = 0;
    rowIdx++;
  }
}
(In reply to comment #31)
> (In reply to comment #28)
> > (From update of attachment 508190 [details] [diff] [review])
> > >+private:
> > >+  TextUpdater();
> > Nit: There is no compiler-generated null constructor, so you don't have to make
> > it private.
> There is no it while there's non null constructor? That doesn't harm if I keep
> it private, right? I would have it just to keep things explicitly.
Well, it's your choice of error message: "TextUpdater::TextUpdater() is private" or "no function matching TextUpdater::TextUpdater()".

> > >+  for (PRUint32 i = 1; i < len1; i++) {
> > Rather than have two separate "i" loops, you can put both sets of code in one
> > loop, as you don't need to know matrix[i][0] = i before the "i"th loop.
> Is row and cell index calculation on each loop preferable than two loops like:
I think you misunderstood; I said two "i" loops, meaning that you have two
for (PRUint32 i = 1; i < len1; i++) loops. The "j" loops are fine.

>   PRUint32 rowIdx = i % len1;
[This is horrible.]
Whiteboard: [softblocker] for remaining work
(Assignee)

Comment 33

7 years ago
Created attachment 509112 [details] [diff] [review]
patch [further work]

sorry for moving code into separate files, while it makes the code look nicer it appears the changes were so big so that keeping a diff wouldn't help for review.
Attachment #509112 - Flags: superreview?(neil)
Attachment #509112 - Flags: review?(bolterbugz)
(In reply to comment #33)
> sorry for moving code into separate files, while it makes the code look nicer
> it appears the changes were so big so that keeping a diff wouldn't help for
> review.
You only seem to have done some of my suggestions :-(
(Assignee)

Comment 35

7 years ago
(In reply to comment #34)
> (In reply to comment #33)

> You only seem to have done some of my suggestions :-(

Sorry. Could you point please what I missed?
(In reply to comment #28)
> NS_MIN would make the code clearer in several places!
> 
> The Levenshtein Distance does not provide a unique least cost solution
> 
> >+  NS_ASSERTION(hyperText, "Text leaf parnet is not hyper text!");
> parent
(Assignee)

Comment 37

7 years ago
(In reply to comment #36)
> (In reply to comment #28)
> > NS_MIN would make the code clearer in several places!

Is the point in "several places" or I started to use PR_MIN (btw, I did by mistake). If "several" then I must miss where it's appropriate place for it. Since I replaced calls like a < b ? a : b to PR_MIIN(a, b).

> > The Levenshtein Distance does not provide a unique least cost solution

I started coalescence of substitution with insertion and deletion. I think I miss your point again, is a key word "unique" here? If so then what can I do with that?

> > >+  NS_ASSERTION(hyperText, "Text leaf parnet is not hyper text!");
> > parent

my bad, I'll fix it.
Comment on attachment 509112 [details] [diff] [review]
patch [further work]

>+            (left < up ? (upleft < left ? upleft : left) :
>+                (upleft < up ? upleft : up)) + 1;
This is where I was looking for NS_MIN. (PR_MIN isn't so good because it's a macro rather than an inline function.)
(Assignee)

Comment 39

7 years ago
(In reply to comment #38)
> Comment on attachment 509112 [details] [diff] [review]
> patch
> 
> >+            (left < up ? (upleft < left ? upleft : left) :
> >+                (upleft < up ? upleft : up)) + 1;
> This is where I was looking for NS_MIN. (PR_MIN isn't so good because it's a
> macro rather than an inline function.)

Right, I got tired today. Sorry for that. Thank you.
(In reply to comment #37)
> I started coalescence of substitution with insertion and deletion. I think I
> miss your point again, is a key word "unique" here? If so then what can I do
> with that?
Ah, the difference there was too subtle for me to spot without a proper diff ;-)
(Assignee)

Comment 41

7 years ago
changing to a hardblocker since the current code fires wrong events in some cases what's a regression.
Whiteboard: [softblocker] for remaining work → [hardblocker] for remaining work
(Assignee)

Updated

7 years ago
Whiteboard: [hardblocker] for remaining work → [hardblocker] for remaining work [haspatch]

Updated

7 years ago
Whiteboard: [hardblocker] for remaining work [haspatch] → [hardblocker] for remaining work [has patch]
Comment on attachment 509112 [details] [diff] [review]
patch [further work]

>+  // affect on the Levenshtein distance.
Nit: "affect the" (no on)

>+  PRUint32* row = entries;
>+  for (PRUint32 rowIdx = 0; rowIdx < len2; rowIdx++, row += len1)
>+    row[0] = rowIdx;
>+
>+  for (PRUint32 colIdx = 1; colIdx < len1; colIdx++) {
>+    entries[colIdx] = colIdx;
>+    PRUint32* prevRow = entries, row = nsnull;
>+    for (PRUint32 rowIdx = 1; rowIdx < len2; rowIdx++) {
>+      PRUint32* row = prevRow + len1;
I would suggest you nest the loops the other way around, like this:

for (PRUint32 colIdx = 0; colIdx < len1; colIdx++)
  entries[colIdx] = colIdx;

PRUint32* row = entries;
for (PRUint32 rowIdx = 1; rowIdx < len2; rowIdx++) {
  PRUint32* prevRow = row;
  row += len1;
  row[0] = rowIdx;
  for (PRUint32 colIdx = 1; colIdx < len1; colIDx++) {

>+  ComputeTextChangeEvents(str1, str2, entries, &events);
Nit: prefer to pass nsTArray by reference.

>+  while (colIdx >= 0 && rowIdx >= 0) {
As far as I can tell, this is always true, since you only decrement col/rowIdx after first testing that they're >= 1.

>+    if (colIdx == 0 && rowIdx == 0) {
>+      MayFireEvent(insertedText, removedText, offset, &change, aEvents);
>+      return;
>+    }
>+
>+    // move up left
>+    if (colIdx >= 1 && rowIdx >= 1) {
>+      // no change
>+      if (aStr1[colIdx - 1] == aStr2[rowIdx - 1]) {
>+        MayFireEvent(insertedText, removedText, offset, &change, aEvents);
[If you try this out in a debugger, you'll see that these two calls to MayFireEvent are the only two that actually fire with change != eNoChange.]
[I can't decide whether comparing the strings or comparing (row[colIdx] == prevRow[colIdx - 1]) is better.]

>+        offset = rowIdx - 1;
>+        removedText.Insert(aStr1[colIdx - 1], 0);
>+        insertedText.Insert(aStr2[offset], 0);
Not sure what the point of the "offset" variable is.
(In reply to comment #42)
>(From update of attachment 509112 [details] [diff] [review])
>>+        offset = rowIdx - 1;
>>+        removedText.Insert(aStr1[colIdx - 1], 0);
>>+        insertedText.Insert(aStr2[offset], 0);
>Not sure what the point of the "offset" variable is.
Ah, I see it's used by MayFireEvent. But by then rowIdx has the same value...
(Assignee)

Comment 44

7 years ago
(In reply to comment #42)
> Comment on attachment 509112 [details] [diff] [review]
> patch

> >+    if (colIdx == 0 && rowIdx == 0) {
> >+      MayFireEvent(insertedText, removedText, offset, &change, aEvents);
> >+      return;
> >+    }
> >+
> >+    // move up left
> >+    if (colIdx >= 1 && rowIdx >= 1) {
> >+      // no change
> >+      if (aStr1[colIdx - 1] == aStr2[rowIdx - 1]) {
> >+        MayFireEvent(insertedText, removedText, offset, &change, aEvents);
> [If you try this out in a debugger, you'll see that these two calls to
> MayFireEvent are the only two that actually fire with change != eNoChange.]

If I have insertion and deletion (no substitution) then MayFireEvent of insertion or deletion should trigger once. I didn't debugged that though.

> [I can't decide whether comparing the strings or comparing (row[colIdx] ==
> prevRow[colIdx - 1]) is better.]

perhaps I would save string comparison.

(In reply to comment #43)
> (In reply to comment #42)
> >(From update of attachment 509112 [details] [diff] [review])
> >>+        offset = rowIdx - 1;
> >>+        removedText.Insert(aStr1[colIdx - 1], 0);
> >>+        insertedText.Insert(aStr2[offset], 0);
> >Not sure what the point of the "offset" variable is.
> Ah, I see it's used by MayFireEvent. But by then rowIdx has the same value...

it sounds like I could use rowIdx or rowIdx + 1 (the last one in the case of removal). Do you think it's worth to change?
Comment on attachment 509112 [details] [diff] [review]
patch [further work]

By the way, I think it's possible to compute the change events without copying the strings character by character, something like this:
colEnd = colIdx = astr1.Length(); // point at which strings last matched
rowEnd = rowIdx = astr2.Length();
colLen = colEnd + 1;
row = entries + rowIdx * colLen;
dist = row[colIdx]; // current Levenshtein distance
while (rowIdx && colIdx) { // stop when we can't move diagonally
  if (dist == row[colIdx - 1 - colLen]) { // match
    if (colIdx < colEnd) // deal with any pending deletion
      FireDeleteEvent(Substring(aStr1, colIdx, colEnd), rowIdx + mOffset);
    if (rowIdx < rowEnd) // deal with any pending insertion
      FireInsertEvent(Substring(aStr2, rowIdx, rowEnd), rowIdx + mOffset);
    colEnd == --colIdx; // reset the match point
    rowEnd == --rowIdx;
  } else if (--dist == row[colIdx - 1 - colLen]) { // substitution
    --colIdx;
    --rowIdx;
  } else if (dist == row[colIdx - colLen]) { // insertion
    --rowIdx;
  } else if (dist == row[colIdx - 1]) { // deletion
    --colIdx;
    continue; // silly trick to avoid typing row -= colLen; 3 times
  } else {
    NS_NOTREACHED("huh?");
    return;
  }
  row -= colLen;
}
if (colEnd)
  FireDeleteEvent(Substring(aStr1, 0, colEnd), mOffset);
if (rowEnd)
  FireInsertEvent(Substring(aStr2, 0, rowEnd), mOffset);
(In reply to comment #44)
>(In reply to comment #42)
>>(From update of attachment 509112 [details] [diff] [review])
>>>+    if (colIdx == 0 && rowIdx == 0) {
>>>+      MayFireEvent(insertedText, removedText, offset, &change, aEvents);
>>>+      return;
>>>+    }
>>>+
>>>+    // move up left
>>>+    if (colIdx >= 1 && rowIdx >= 1) {
>>>+      // no change
>>>+      if (aStr1[colIdx - 1] == aStr2[rowIdx - 1]) {
>>>+        MayFireEvent(insertedText, removedText, offset, &change, aEvents);
>>[If you try this out in a debugger, you'll see that these two calls to
>>MayFireEvent are the only two that actually fire with change != eNoChange.]
>If I have insertion and deletion (no substitution) then MayFireEvent of
>insertion or deletion should trigger once. I didn't debugged that though.
That's not actually possible, because substitution has less distance than insertion plus deletion, so you would always trigger that by preference!

>>[I can't decide whether comparing the strings or comparing (row[colIdx] ==
>>prevRow[colIdx - 1]) is better.]
>perhaps I would save string comparison.
I was thinking the optimiser might want to cache the value of row[colIdx].

>(In reply to comment #43)
>>(In reply to comment #42)
>>>(From update of attachment 509112 [details] [diff] [review])
>>>>+        offset = rowIdx - 1;
>>>>+        removedText.Insert(aStr1[colIdx - 1], 0);
>>>>+        insertedText.Insert(aStr2[offset], 0);
>>>Not sure what the point of the "offset" variable is.
>>Ah, I see it's used by MayFireEvent. But by then rowIdx has the same value...
>it sounds like I could use rowIdx or rowIdx + 1 (the last one in the case of
>removal).
Actually in the case of removal you don't change rowIdx so that offset is still equal to rowIdx.
(Assignee)

Comment 47

7 years ago
(In reply to comment #45)

> By the way, I think it's possible to compute the change events without copying
> the strings character by character, something like this:

This is excellent idea. Thank you!

> row = entries + rowIdx * colLen;
> dist = row[colIdx]; // current Levenshtein distance
> while (rowIdx && colIdx) { // stop when we can't move diagonally
>   if (dist == row[colIdx - 1 - colLen]) { // match

This doesn't always mean a match because it's necessary that up and left cells has dist - 1 additionally. I'll use string comparison I think for the next patch.
(Assignee)

Comment 48

7 years ago
Created attachment 509701 [details] [diff] [review]
patch2 [further work]

fixed Neil's comments and Neil's code snippets are used.
Attachment #509112 - Attachment is obsolete: true
Attachment #509701 - Flags: superreview?(neil)
Attachment #509701 - Flags: review?(bolterbugz)
Attachment #509112 - Flags: superreview?(neil)
Attachment #509112 - Flags: review?(bolterbugz)
(Assignee)

Updated

7 years ago
Attachment #509112 - Attachment description: patch → patch [further work]
(Assignee)

Comment 49

7 years ago
Comment on attachment 509701 [details] [diff] [review]
patch2 [further work]


>+  // Increase offset of the text leaf on skipped characters amount.
>+  mTextOffset = mHyperText->GetChildOffset(mTextLeaf, PR_TRUE) + aSkipStart;

this is done by mistake, I fixed locally:
mTextOffset += aSkipStart;
(In reply to comment #47)
> > row = entries + rowIdx * colLen;
> > dist = row[colIdx]; // current Levenshtein distance
> > while (rowIdx && colIdx) { // stop when we can't move diagonally
> >   if (dist == row[colIdx - 1 - colLen]) { // match
> 
> This doesn't always mean a match because it's necessary that up and left cells
> has dist - 1 additionally. I'll use string comparison I think for the next
> patch.

I'm not sure what you mean there. When you compute the matrix, if the characters match then you copy the diagonal cell without adding 1. Otherwise you choose the minimum of the three touching cells, plus 1. So the diagonal cells can only be equal if the characters match.
Comment on attachment 509701 [details] [diff] [review]
patch2 [further work]

>+  if (rowEnd)
>+    FireInsertEvent(Substring(aStr2, 0, rowEnd), 0, aEvents);
>+  if (colEnd)
>+    FireDeleteEvent(Substring(aStr1, 0, colEnd), 0, aEvents);
[Note to self: the events are stacked as they need to fire in reverse order;
 the insert event is stacked first so that the delete fires first.]
(Assignee)

Comment 52

7 years ago
(In reply to comment #50)
> (In reply to comment #47)
> > > row = entries + rowIdx * colLen;
> > > dist = row[colIdx]; // current Levenshtein distance
> > > while (rowIdx && colIdx) { // stop when we can't move diagonally
> > >   if (dist == row[colIdx - 1 - colLen]) { // match
> > 
> > This doesn't always mean a match because it's necessary that up and left cells
> > has dist - 1 additionally. I'll use string comparison I think for the next
> > patch.
> 
> I'm not sure what you mean there. When you compute the matrix, if the
> characters match then you copy the diagonal cell without adding 1. Otherwise
> you choose the minimum of the three touching cells, plus 1. So the diagonal
> cells can only be equal if the characters match.

Right, but you can move out from diagonal because of insertion or deletion.
(In reply to comment #52)
> (In reply to comment #50)
> > (In reply to comment #47)
> > > > row = entries + rowIdx * colLen;
> > > > dist = row[colIdx]; // current Levenshtein distance
> > > > while (rowIdx && colIdx) { // stop when we can't move diagonally
> > > >   if (dist == row[colIdx - 1 - colLen]) { // match
> > > 
> > > This doesn't always mean a match because it's necessary that up and left cells
> > > has dist - 1 additionally. I'll use string comparison I think for the next
> > > patch.
> > 
> > I'm not sure what you mean there. When you compute the matrix, if the
> > characters match then you copy the diagonal cell without adding 1. Otherwise
> > you choose the minimum of the three touching cells, plus 1. So the diagonal
> > cells can only be equal if the characters match.
> 
> Right, but you can move out from diagonal because of insertion or deletion.

Ah, I see what you mean now.
To go from steams to seatme is a distance of 3 (-t, +t, -s+e)
To go from steams to dreamt is also a distance of 3 (-s+d, -t+r, -s+t)
But you can't tell the difference from the array, because entries[3][3] is the same in both cases.
Comment on attachment 509701 [details] [diff] [review]
patch2 [further work]

>+  // Text was appended or removed to/from the end.
>+  if (aSkipStart == minLen) {
>+    // If text has been appended to the end, fire text inserted event.
>+    if (oldLen < newLen) {
>+      UpdateTextNFireEvent(aNewText, Substring(aNewText, oldLen),
>+                           oldLen, PR_TRUE);
>+      return;
>+    }
>+
>+    // Text has been removed from the end, fire text removed event.
>+    UpdateTextNFireEvent(aNewText, Substring(aOldText, newLen),
>+                         newLen, PR_FALSE);
>+    return;
>+  }
>+
>+  // Trim coinciding substrings from the end.
>+  PRUint32 skipEnd = 0;
>+  while (minLen - skipEnd > aSkipStart &&
>+         aNewText[newLen - skipEnd - 1] == aOldText[oldLen - skipEnd - 1]) {
>+    skipEnd++;
>+  }
[It occurs to me that you could check for skipEnd == minLen and optimise for the text inserted/deleted from the start.]

>+        row[colIdx] =
>+          (left < up ? NS_MIN(upleft, left) : NS_MIN(upleft, up)) + 1;
= NS_MIN(upleft, NS_MIN(left, up)) + 1;

>+  TextUpdater();
[I take it you prefer the "function is private" error to the "no matching function" error when trying to default-construct a TextUpdater.]

>+  TextUpdater& operator = (const TextUpdater&);
This must be one of the rare cases where you don't need spaces around = !

>+  enum ChangeType {
Unused!

>+    nsRefPtr<AccEvent> event =
[AccEvent* would probably work, because aEvents will addref it.]
Attachment #509701 - Flags: superreview?(neil) → superreview+
I was trying to think how you could fire the value change for ROLE_ENTRY in one place but ended up liking your implementation :)
Comment on attachment 509701 [details] [diff] [review]
patch2 [further work]

>+  /**
>+   * Start text of the text leaf update.
>+   */
>+  static void Run(nsDocAccessible* aDocument, nsTextAccessible* aTextLeaf,
>+                  const nsAString& aNewText);

Nit: is the comment supposed to be "Start the text leaf update"?
Comment on attachment 509701 [details] [diff] [review]
patch2 [further work]

r=me for the logic, quick while I still understand it :)

With Neil's nits of course.

Regarding the tests:

>+  this.isAlreadyCaught = function eventQueue_isAlreadyCaught(aIdx, aEvent)
>+  {
>+    // We don't have stored info about handled event other than its type and
>+    // target, thus we should filter text change events since they may occur
>+    // on the same element because of complex changes.
>+    return this.compareEvents(aIdx, aEvent) &&
>+      !(aEvent instanceof nsIAccessibleTextChangeEvent);
>+  }
>+

I don't yet understand the need for this yet
Attachment #509701 - Flags: review?(bolterbugz) → review+
(In reply to comment #57)
 
> I don't yet understand the need for this yet

Got it.

BTW I asked Ehsan's opinion on a few things, and he's going to provide feedback.
Even though there are tests, at this point in the release cycle Marco wants to try builds before landing non trivial changes.
(Assignee)

Comment 60

7 years ago
(In reply to comment #59)
> Even though there are tests, at this point in the release cycle Marco wants to
> try builds before landing non trivial changes.

while these changes may be considered as non trivial for algorithm, but they can't be considered the same way for a11y.

I don't mind if Marco wants to try it - http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/surkov.alexander@gmail.com-8e76b5435206

Comment 61

7 years ago
(In reply to comment #58)
> (In reply to comment #57)
> 
> > I don't yet understand the need for this yet
> 
> Got it.
> 
> BTW I asked Ehsan's opinion on a few things, and he's going to provide
> feedback.

So Firefox crashed for me when I was writing those comments, and then I got distracted.  I didn't get to look into it closely after that, but here's what I can rmember from what I was writing:

+    } else if (--dist == row[colIdx - 1 - colLen]) { // substitution

I think decrementing dist as a side effect of this branch condition is a very bad idea.  If I were to write this code, I'd decrement dist in an else block, which would have the rest of the conditions inside if after the decrement.
(Assignee)

Comment 62

7 years ago
(In reply to comment #61)

> +    } else if (--dist == row[colIdx - 1 - colLen]) { // substitution
> 
> I think decrementing dist as a side effect of this branch condition is a very
> bad idea.  If I were to write this code, I'd decrement dist in an else block,
> which would have the rest of the conditions inside if after the decrement.

I don't use this code style when I write a code. Here's an exception I'd said. It's Neil's code snippet and looks compact and clear (what's quite important for algorithm understanding). I used it even if it looks like a stranger with rest of code.
(Assignee)

Comment 63

7 years ago
(In reply to comment #54)

> >+  TextUpdater();
> [I take it you prefer the "function is private" error to the "no matching
> function" error when trying to default-construct a TextUpdater.]

I don't have preferences in errors but perhaps I have preference to keep things explicit.

> >+    nsRefPtr<AccEvent> event =
> [AccEvent* would probably work, because aEvents will addref it.]

It looks like if AppendElement runs out of memory then it should mean a leak.
(In reply to comment #63)
> (In reply to comment #54)
> > >+    nsRefPtr<AccEvent> event =
> > [AccEvent* would probably work, because aEvents will addref it.]
> It looks like if AppendElement runs out of memory then it should mean a leak.
Thanks for reminding me.

Feel free to rewrite the branching code. Maybe something like this:
  if (dist == row[colIdx - 1 - colLen]) { // match
    /* etc */
    rowEnd == --rowIdx;
    row -= colLen;
    continue;
  }
  dist--;
  if (dist == row[colIdx - 1 - colLen]) { // substitution
    --colIdx;
    --rowIdx;
    row -= colLen;
    continue;
  }
  if (dist == row[colIdx - colLen]) { // insertion
    --rowIdx;
    row -= colLen;
    continue;
  }
  if (dist == row[colIdx - 1]) { // deletion
    --colIdx;
    continue;
  }
  NS_NOTREACHED("huh?");
  return;
(In reply to comment #64)
> Feel free to rewrite the branching code. Maybe something like this:
>   if (dist == row[colIdx - 1 - colLen]) { // match
Well, not that, but you get the idea of the rest of it ;-)
(Assignee)

Comment 66

7 years ago
(In reply to comment #64)
 
> Feel free to rewrite the branching code. Maybe something like this:

Ok, I think I follow this way.
(Assignee)

Comment 67

7 years ago
(In reply to comment #61)

> So Firefox crashed for me when I was writing those comments, and then I got
> distracted.  I didn't get to look into it closely after that, but here's what I
> can rmember from what I was writing:

Ehsan, thanks for looking at this. If you spotted anything important then please find a time to find it again.
(In reply to comment #62)
> (In reply to comment #61)
> 
> > +    } else if (--dist == row[colIdx - 1 - colLen]) { // substitution
> > 
> > I think decrementing dist as a side effect of this branch condition is a very
> > bad idea.  If I were to write this code, I'd decrement dist in an else block,
> > which would have the rest of the conditions inside if after the decrement.
> 
> I don't use this code style when I write a code. Here's an exception I'd said.
> It's Neil's code snippet and looks compact and clear (what's quite important
> for algorithm understanding). I used it even if it looks like a stranger with
> rest of code.

Note: this part threw me during my review, which was why I pointed it out Ehsan for his opinion.
I ran with this try-server build for a while, and everything's OK from this end.
Blocks: 631213

Comment 70

7 years ago
(In reply to comment #67)
> (In reply to comment #61)
> 
> > So Firefox crashed for me when I was writing those comments, and then I got
> > distracted.  I didn't get to look into it closely after that, but here's what I
> > can rmember from what I was writing:
> 
> Ehsan, thanks for looking at this. If you spotted anything important then
> please find a time to find it again.

Nah, I was mostly nit-picking, don't worry!  The code looks sane to me more or less.
(Assignee)

Comment 71

7 years ago
(In reply to comment #68)
> (In reply to comment #62)
> > (In reply to comment #61)
> > 
> > > +    } else if (--dist == row[colIdx - 1 - colLen]) { // substitution
> > > 
> > > I think decrementing dist as a side effect of this branch condition is a very
> > > bad idea.  If I were to write this code, I'd decrement dist in an else block,
> > > which would have the rest of the conditions inside if after the decrement.
> > 
> > I don't use this code style when I write a code. Here's an exception I'd said.
> > It's Neil's code snippet and looks compact and clear (what's quite important
> > for algorithm understanding). I used it even if it looks like a stranger with
> > rest of code.
> 
> Note: this part threw me during my review, which was why I pointed it out Ehsan
> for his opinion.

Perhaps this code can be compared to regular expression: while it is compact and look pretty good, it takes a time to understand why it work :)
(Assignee)

Comment 72

7 years ago
(In reply to comment #70)

> > Ehsan, thanks for looking at this. If you spotted anything important then
> > please find a time to find it again.
> 
> Nah, I was mostly nit-picking, don't worry!  The code looks sane to me more or
> less.

Ok, thank you.
(Assignee)

Comment 73

7 years ago
landed on 2.0 (fx4beta12) - http://hg.mozilla.org/mozilla-central/rev/622553a5c89d
Status: ASSIGNED → RESOLVED
Last Resolved: 7 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: mozilla2.0b11 → mozilla2.0b12
(Assignee)

Updated

7 years ago
Blocks: 631499
You need to log in before you can comment on or make changes to this bug.