1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 #include "TextUpdater.h"
8 #include "LocalAccessible-inl.h"
9 #include "DocAccessible-inl.h"
10 #include "TextLeafAccessible.h"
13 using namespace mozilla::a11y
;
15 void TextUpdater::Run(DocAccessible
* aDocument
, TextLeafAccessible
* aTextLeaf
,
16 const nsAString
& aNewText
) {
17 NS_ASSERTION(aTextLeaf
, "No text leaf accessible?");
19 const nsString
& oldText
= aTextLeaf
->Text();
20 uint32_t oldLen
= oldText
.Length(), newLen
= aNewText
.Length();
21 uint32_t minLen
= std::min(oldLen
, newLen
);
23 // Skip coinciding begin substrings.
24 uint32_t skipStart
= 0;
25 for (; skipStart
< minLen
; skipStart
++) {
26 if (aNewText
[skipStart
] != oldText
[skipStart
]) break;
29 // The text was changed. Do update.
30 if (skipStart
!= minLen
|| oldLen
!= newLen
) {
31 TextUpdater
updater(aDocument
, aTextLeaf
);
32 updater
.DoUpdate(aNewText
, oldText
, skipStart
);
36 void TextUpdater::DoUpdate(const nsAString
& aNewText
, const nsAString
& aOldText
,
37 uint32_t aSkipStart
) {
38 LocalAccessible
* parent
= mTextLeaf
->LocalParent();
41 mHyperText
= parent
->AsHyperText();
43 MOZ_ASSERT_UNREACHABLE("Text leaf parent is not hypertext!");
47 mTextOffset
= mHyperText
->GetChildOffset(mTextLeaf
);
48 NS_ASSERTION(mTextOffset
!= -1, "Text leaf hasn't offset within hyper text!");
50 uint32_t oldLen
= aOldText
.Length(), newLen
= aNewText
.Length();
51 uint32_t minLen
= std::min(oldLen
, newLen
);
53 // Trim coinciding substrings from the end.
55 while (minLen
- skipEnd
> aSkipStart
&&
56 aNewText
[newLen
- skipEnd
- 1] == aOldText
[oldLen
- skipEnd
- 1]) {
60 uint32_t strLen1
= oldLen
- aSkipStart
- skipEnd
;
61 uint32_t strLen2
= newLen
- aSkipStart
- skipEnd
;
63 const nsAString
& str1
= Substring(aOldText
, aSkipStart
, strLen1
);
64 const nsAString
& str2
= Substring(aNewText
, aSkipStart
, strLen2
);
66 // Increase offset of the text leaf on skipped characters amount.
67 mTextOffset
+= aSkipStart
;
69 // It could be single insertion or removal or the case of long strings. Do not
70 // calculate the difference between long strings and prefer to fire pair of
71 // insert/remove events as the old string was replaced on the new one.
72 if (strLen1
== 0 || strLen2
== 0 || strLen1
> kMaxStrLen
||
73 strLen2
> kMaxStrLen
) {
75 // Fire text change event for removal.
76 RefPtr
<AccEvent
> textRemoveEvent
=
77 new AccTextChangeEvent(mHyperText
, mTextOffset
, str1
, false);
78 mDocument
->FireDelayedEvent(textRemoveEvent
);
82 // Fire text change event for insertion.
83 RefPtr
<AccEvent
> textInsertEvent
=
84 new AccTextChangeEvent(mHyperText
, mTextOffset
, str2
, true);
85 mDocument
->FireDelayedEvent(textInsertEvent
);
88 mDocument
->MaybeNotifyOfValueChange(mHyperText
);
91 mTextLeaf
->SetText(aNewText
);
92 mHyperText
->InvalidateCachedHyperTextOffsets();
96 // Otherwise find the difference between strings and fire events.
97 // Note: we can skip initial and final coinciding characters since they don't
98 // affect the Levenshtein distance.
100 // Compute the flat structured matrix need to compute the difference.
101 uint32_t len1
= strLen1
+ 1, len2
= strLen2
+ 1;
102 uint32_t* entries
= new uint32_t[len1
* len2
];
104 for (uint32_t colIdx
= 0; colIdx
< len1
; colIdx
++) entries
[colIdx
] = colIdx
;
106 uint32_t* row
= entries
;
107 for (uint32_t rowIdx
= 1; rowIdx
< len2
; rowIdx
++) {
108 uint32_t* prevRow
= row
;
111 for (uint32_t colIdx
= 1; colIdx
< len1
; colIdx
++) {
112 if (str1
[colIdx
- 1] != str2
[rowIdx
- 1]) {
113 uint32_t left
= row
[colIdx
- 1];
114 uint32_t up
= prevRow
[colIdx
];
115 uint32_t upleft
= prevRow
[colIdx
- 1];
116 row
[colIdx
] = std::min(upleft
, std::min(left
, up
)) + 1;
118 row
[colIdx
] = prevRow
[colIdx
- 1];
123 // Compute events based on the difference.
124 nsTArray
<RefPtr
<AccEvent
> > events
;
125 ComputeTextChangeEvents(str1
, str2
, entries
, events
);
130 for (int32_t idx
= events
.Length() - 1; idx
>= 0; idx
--) {
131 mDocument
->FireDelayedEvent(events
[idx
]);
134 mDocument
->MaybeNotifyOfValueChange(mHyperText
);
137 mTextLeaf
->SetText(aNewText
);
138 mHyperText
->InvalidateCachedHyperTextOffsets();
141 void TextUpdater::ComputeTextChangeEvents(
142 const nsAString
& aStr1
, const nsAString
& aStr2
, uint32_t* aEntries
,
143 nsTArray
<RefPtr
<AccEvent
> >& aEvents
) {
144 int32_t colIdx
= aStr1
.Length(), rowIdx
= aStr2
.Length();
146 // Point at which strings last matched.
147 int32_t colEnd
= colIdx
;
148 int32_t rowEnd
= rowIdx
;
150 int32_t colLen
= colEnd
+ 1;
151 uint32_t* row
= aEntries
+ rowIdx
* colLen
;
152 uint32_t dist
= row
[colIdx
]; // current Levenshtein distance
153 while (rowIdx
&& colIdx
) { // stop when we can't move diagonally
154 if (aStr1
[colIdx
- 1] == aStr2
[rowIdx
- 1]) { // match
155 if (rowIdx
< rowEnd
) { // deal with any pending insertion
156 FireInsertEvent(Substring(aStr2
, rowIdx
, rowEnd
- rowIdx
), rowIdx
,
159 if (colIdx
< colEnd
) { // deal with any pending deletion
160 FireDeleteEvent(Substring(aStr1
, colIdx
, colEnd
- colIdx
), rowIdx
,
164 colEnd
= --colIdx
; // reset the match point
170 if (dist
== row
[colIdx
- 1 - colLen
]) { // substitution
176 if (dist
== row
[colIdx
- colLen
]) { // insertion
181 if (dist
== row
[colIdx
- 1]) { // deletion
185 MOZ_ASSERT_UNREACHABLE("huh?");
189 if (rowEnd
) FireInsertEvent(Substring(aStr2
, 0, rowEnd
), 0, aEvents
);
190 if (colEnd
) FireDeleteEvent(Substring(aStr1
, 0, colEnd
), 0, aEvents
);