Line data Source code
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/. */
5 :
6 : #include "TextUpdater.h"
7 :
8 : #include "Accessible-inl.h"
9 : #include "DocAccessible-inl.h"
10 : #include "TextLeafAccessible.h"
11 : #include <algorithm>
12 :
13 : using namespace mozilla::a11y;
14 :
15 : void
16 0 : TextUpdater::Run(DocAccessible* aDocument, TextLeafAccessible* aTextLeaf,
17 : const nsAString& aNewText)
18 : {
19 0 : NS_ASSERTION(aTextLeaf, "No text leaf accessible?");
20 :
21 0 : const nsString& oldText = aTextLeaf->Text();
22 0 : uint32_t oldLen = oldText.Length(), newLen = aNewText.Length();
23 0 : uint32_t minLen = std::min(oldLen, newLen);
24 :
25 : // Skip coinciding begin substrings.
26 0 : uint32_t skipStart = 0;
27 0 : for (; skipStart < minLen; skipStart++) {
28 0 : if (aNewText[skipStart] != oldText[skipStart])
29 0 : break;
30 : }
31 :
32 : // The text was changed. Do update.
33 0 : if (skipStart != minLen || oldLen != newLen) {
34 0 : TextUpdater updater(aDocument, aTextLeaf);
35 0 : updater.DoUpdate(aNewText, oldText, skipStart);
36 : }
37 0 : }
38 :
39 : void
40 0 : TextUpdater::DoUpdate(const nsAString& aNewText, const nsAString& aOldText,
41 : uint32_t aSkipStart)
42 : {
43 0 : Accessible* parent = mTextLeaf->Parent();
44 0 : if (!parent)
45 0 : return;
46 :
47 0 : mHyperText = parent->AsHyperText();
48 0 : if (!mHyperText) {
49 0 : NS_ERROR("Text leaf parent is not hypertext!");
50 0 : return;
51 : }
52 :
53 : // Get the text leaf accessible offset and invalidate cached offsets after it.
54 0 : mTextOffset = mHyperText->GetChildOffset(mTextLeaf, true);
55 0 : NS_ASSERTION(mTextOffset != -1,
56 : "Text leaf hasn't offset within hyper text!");
57 :
58 0 : uint32_t oldLen = aOldText.Length(), newLen = aNewText.Length();
59 0 : uint32_t minLen = std::min(oldLen, newLen);
60 :
61 : // Trim coinciding substrings from the end.
62 0 : uint32_t skipEnd = 0;
63 0 : while (minLen - skipEnd > aSkipStart &&
64 0 : aNewText[newLen - skipEnd - 1] == aOldText[oldLen - skipEnd - 1]) {
65 0 : skipEnd++;
66 : }
67 :
68 0 : uint32_t strLen1 = oldLen - aSkipStart - skipEnd;
69 0 : uint32_t strLen2 = newLen - aSkipStart - skipEnd;
70 :
71 0 : const nsAString& str1 = Substring(aOldText, aSkipStart, strLen1);
72 0 : const nsAString& str2 = Substring(aNewText, aSkipStart, strLen2);
73 :
74 : // Increase offset of the text leaf on skipped characters amount.
75 0 : mTextOffset += aSkipStart;
76 :
77 : // It could be single insertion or removal or the case of long strings. Do not
78 : // calculate the difference between long strings and prefer to fire pair of
79 : // insert/remove events as the old string was replaced on the new one.
80 0 : if (strLen1 == 0 || strLen2 == 0 ||
81 0 : strLen1 > kMaxStrLen || strLen2 > kMaxStrLen) {
82 0 : if (strLen1 > 0) {
83 : // Fire text change event for removal.
84 : RefPtr<AccEvent> textRemoveEvent =
85 0 : new AccTextChangeEvent(mHyperText, mTextOffset, str1, false);
86 0 : mDocument->FireDelayedEvent(textRemoveEvent);
87 : }
88 :
89 0 : if (strLen2 > 0) {
90 : // Fire text change event for insertion.
91 : RefPtr<AccEvent> textInsertEvent =
92 0 : new AccTextChangeEvent(mHyperText, mTextOffset, str2, true);
93 0 : mDocument->FireDelayedEvent(textInsertEvent);
94 : }
95 :
96 0 : mDocument->MaybeNotifyOfValueChange(mHyperText);
97 :
98 : // Update the text.
99 0 : mTextLeaf->SetText(aNewText);
100 0 : return;
101 : }
102 :
103 : // Otherwise find the difference between strings and fire events.
104 : // Note: we can skip initial and final coinciding characters since they don't
105 : // affect the Levenshtein distance.
106 :
107 : // Compute the flat structured matrix need to compute the difference.
108 0 : uint32_t len1 = strLen1 + 1, len2 = strLen2 + 1;
109 0 : uint32_t* entries = new uint32_t[len1 * len2];
110 :
111 0 : for (uint32_t colIdx = 0; colIdx < len1; colIdx++)
112 0 : entries[colIdx] = colIdx;
113 :
114 0 : uint32_t* row = entries;
115 0 : for (uint32_t rowIdx = 1; rowIdx < len2; rowIdx++) {
116 0 : uint32_t* prevRow = row;
117 0 : row += len1;
118 0 : row[0] = rowIdx;
119 0 : for (uint32_t colIdx = 1; colIdx < len1; colIdx++) {
120 0 : if (str1[colIdx - 1] != str2[rowIdx - 1]) {
121 0 : uint32_t left = row[colIdx - 1];
122 0 : uint32_t up = prevRow[colIdx];
123 0 : uint32_t upleft = prevRow[colIdx - 1];
124 0 : row[colIdx] = std::min(upleft, std::min(left, up)) + 1;
125 : } else {
126 0 : row[colIdx] = prevRow[colIdx - 1];
127 : }
128 : }
129 : }
130 :
131 : // Compute events based on the difference.
132 0 : nsTArray<RefPtr<AccEvent> > events;
133 0 : ComputeTextChangeEvents(str1, str2, entries, events);
134 :
135 0 : delete [] entries;
136 :
137 : // Fire events.
138 0 : for (int32_t idx = events.Length() - 1; idx >= 0; idx--)
139 0 : mDocument->FireDelayedEvent(events[idx]);
140 :
141 0 : mDocument->MaybeNotifyOfValueChange(mHyperText);
142 :
143 : // Update the text.
144 0 : mTextLeaf->SetText(aNewText);
145 : }
146 :
147 : void
148 0 : TextUpdater::ComputeTextChangeEvents(const nsAString& aStr1,
149 : const nsAString& aStr2,
150 : uint32_t* aEntries,
151 : nsTArray<RefPtr<AccEvent> >& aEvents)
152 : {
153 0 : int32_t colIdx = aStr1.Length(), rowIdx = aStr2.Length();
154 :
155 : // Point at which strings last matched.
156 0 : int32_t colEnd = colIdx;
157 0 : int32_t rowEnd = rowIdx;
158 :
159 0 : int32_t colLen = colEnd + 1;
160 0 : uint32_t* row = aEntries + rowIdx * colLen;
161 0 : uint32_t dist = row[colIdx]; // current Levenshtein distance
162 0 : while (rowIdx && colIdx) { // stop when we can't move diagonally
163 0 : if (aStr1[colIdx - 1] == aStr2[rowIdx - 1]) { // match
164 0 : if (rowIdx < rowEnd) { // deal with any pending insertion
165 0 : FireInsertEvent(Substring(aStr2, rowIdx, rowEnd - rowIdx),
166 0 : rowIdx, aEvents);
167 : }
168 0 : if (colIdx < colEnd) { // deal with any pending deletion
169 0 : FireDeleteEvent(Substring(aStr1, colIdx, colEnd - colIdx),
170 0 : rowIdx, aEvents);
171 : }
172 :
173 0 : colEnd = --colIdx; // reset the match point
174 0 : rowEnd = --rowIdx;
175 0 : row -= colLen;
176 0 : continue;
177 : }
178 0 : --dist;
179 0 : if (dist == row[colIdx - 1 - colLen]) { // substitution
180 0 : --colIdx;
181 0 : --rowIdx;
182 0 : row -= colLen;
183 0 : continue;
184 : }
185 0 : if (dist == row[colIdx - colLen]) { // insertion
186 0 : --rowIdx;
187 0 : row -= colLen;
188 0 : continue;
189 : }
190 0 : if (dist == row[colIdx - 1]) { // deletion
191 0 : --colIdx;
192 0 : continue;
193 : }
194 0 : NS_NOTREACHED("huh?");
195 0 : return;
196 : }
197 :
198 0 : if (rowEnd)
199 0 : FireInsertEvent(Substring(aStr2, 0, rowEnd), 0, aEvents);
200 0 : if (colEnd)
201 0 : FireDeleteEvent(Substring(aStr1, 0, colEnd), 0, aEvents);
202 : }
|
