1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/accessible/src/base/TextUpdater.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,202 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "TextUpdater.h"
1.10 +
1.11 +#include "Accessible-inl.h"
1.12 +#include "DocAccessible-inl.h"
1.13 +#include "TextLeafAccessible.h"
1.14 +#include <algorithm>
1.15 +
1.16 +using namespace mozilla::a11y;
1.17 +
1.18 +void
1.19 +TextUpdater::Run(DocAccessible* aDocument, TextLeafAccessible* aTextLeaf,
1.20 + const nsAString& aNewText)
1.21 +{
1.22 + NS_ASSERTION(aTextLeaf, "No text leaf accessible?");
1.23 +
1.24 + const nsString& oldText = aTextLeaf->Text();
1.25 + uint32_t oldLen = oldText.Length(), newLen = aNewText.Length();
1.26 + uint32_t minLen = std::min(oldLen, newLen);
1.27 +
1.28 + // Skip coinciding begin substrings.
1.29 + uint32_t skipStart = 0;
1.30 + for (; skipStart < minLen; skipStart++) {
1.31 + if (aNewText[skipStart] != oldText[skipStart])
1.32 + break;
1.33 + }
1.34 +
1.35 + // The text was changed. Do update.
1.36 + if (skipStart != minLen || oldLen != newLen) {
1.37 + TextUpdater updater(aDocument, aTextLeaf);
1.38 + updater.DoUpdate(aNewText, oldText, skipStart);
1.39 + }
1.40 +}
1.41 +
1.42 +void
1.43 +TextUpdater::DoUpdate(const nsAString& aNewText, const nsAString& aOldText,
1.44 + uint32_t aSkipStart)
1.45 +{
1.46 + Accessible* parent = mTextLeaf->Parent();
1.47 + if (!parent)
1.48 + return;
1.49 +
1.50 + mHyperText = parent->AsHyperText();
1.51 + if (!mHyperText) {
1.52 + NS_ERROR("Text leaf parent is not hypertext!");
1.53 + return;
1.54 + }
1.55 +
1.56 + // Get the text leaf accessible offset and invalidate cached offsets after it.
1.57 + mTextOffset = mHyperText->GetChildOffset(mTextLeaf, true);
1.58 + NS_ASSERTION(mTextOffset != -1,
1.59 + "Text leaf hasn't offset within hyper text!");
1.60 +
1.61 + uint32_t oldLen = aOldText.Length(), newLen = aNewText.Length();
1.62 + uint32_t minLen = std::min(oldLen, newLen);
1.63 +
1.64 + // Trim coinciding substrings from the end.
1.65 + uint32_t skipEnd = 0;
1.66 + while (minLen - skipEnd > aSkipStart &&
1.67 + aNewText[newLen - skipEnd - 1] == aOldText[oldLen - skipEnd - 1]) {
1.68 + skipEnd++;
1.69 + }
1.70 +
1.71 + uint32_t strLen1 = oldLen - aSkipStart - skipEnd;
1.72 + uint32_t strLen2 = newLen - aSkipStart - skipEnd;
1.73 +
1.74 + const nsAString& str1 = Substring(aOldText, aSkipStart, strLen1);
1.75 + const nsAString& str2 = Substring(aNewText, aSkipStart, strLen2);
1.76 +
1.77 + // Increase offset of the text leaf on skipped characters amount.
1.78 + mTextOffset += aSkipStart;
1.79 +
1.80 + // It could be single insertion or removal or the case of long strings. Do not
1.81 + // calculate the difference between long strings and prefer to fire pair of
1.82 + // insert/remove events as the old string was replaced on the new one.
1.83 + if (strLen1 == 0 || strLen2 == 0 ||
1.84 + strLen1 > kMaxStrLen || strLen2 > kMaxStrLen) {
1.85 + if (strLen1 > 0) {
1.86 + // Fire text change event for removal.
1.87 + nsRefPtr<AccEvent> textRemoveEvent =
1.88 + new AccTextChangeEvent(mHyperText, mTextOffset, str1, false);
1.89 + mDocument->FireDelayedEvent(textRemoveEvent);
1.90 + }
1.91 +
1.92 + if (strLen2 > 0) {
1.93 + // Fire text change event for insertion.
1.94 + nsRefPtr<AccEvent> textInsertEvent =
1.95 + new AccTextChangeEvent(mHyperText, mTextOffset, str2, true);
1.96 + mDocument->FireDelayedEvent(textInsertEvent);
1.97 + }
1.98 +
1.99 + mDocument->MaybeNotifyOfValueChange(mHyperText);
1.100 +
1.101 + // Update the text.
1.102 + mTextLeaf->SetText(aNewText);
1.103 + return;
1.104 + }
1.105 +
1.106 + // Otherwise find the difference between strings and fire events.
1.107 + // Note: we can skip initial and final coinciding characters since they don't
1.108 + // affect the Levenshtein distance.
1.109 +
1.110 + // Compute the flat structured matrix need to compute the difference.
1.111 + uint32_t len1 = strLen1 + 1, len2 = strLen2 + 1;
1.112 + uint32_t* entries = new uint32_t[len1 * len2];
1.113 +
1.114 + for (uint32_t colIdx = 0; colIdx < len1; colIdx++)
1.115 + entries[colIdx] = colIdx;
1.116 +
1.117 + uint32_t* row = entries;
1.118 + for (uint32_t rowIdx = 1; rowIdx < len2; rowIdx++) {
1.119 + uint32_t* prevRow = row;
1.120 + row += len1;
1.121 + row[0] = rowIdx;
1.122 + for (uint32_t colIdx = 1; colIdx < len1; colIdx++) {
1.123 + if (str1[colIdx - 1] != str2[rowIdx - 1]) {
1.124 + uint32_t left = row[colIdx - 1];
1.125 + uint32_t up = prevRow[colIdx];
1.126 + uint32_t upleft = prevRow[colIdx - 1];
1.127 + row[colIdx] = std::min(upleft, std::min(left, up)) + 1;
1.128 + } else {
1.129 + row[colIdx] = prevRow[colIdx - 1];
1.130 + }
1.131 + }
1.132 + }
1.133 +
1.134 + // Compute events based on the difference.
1.135 + nsTArray<nsRefPtr<AccEvent> > events;
1.136 + ComputeTextChangeEvents(str1, str2, entries, events);
1.137 +
1.138 + delete [] entries;
1.139 +
1.140 + // Fire events.
1.141 + for (int32_t idx = events.Length() - 1; idx >= 0; idx--)
1.142 + mDocument->FireDelayedEvent(events[idx]);
1.143 +
1.144 + mDocument->MaybeNotifyOfValueChange(mHyperText);
1.145 +
1.146 + // Update the text.
1.147 + mTextLeaf->SetText(aNewText);
1.148 +}
1.149 +
1.150 +void
1.151 +TextUpdater::ComputeTextChangeEvents(const nsAString& aStr1,
1.152 + const nsAString& aStr2,
1.153 + uint32_t* aEntries,
1.154 + nsTArray<nsRefPtr<AccEvent> >& aEvents)
1.155 +{
1.156 + int32_t colIdx = aStr1.Length(), rowIdx = aStr2.Length();
1.157 +
1.158 + // Point at which strings last matched.
1.159 + int32_t colEnd = colIdx;
1.160 + int32_t rowEnd = rowIdx;
1.161 +
1.162 + int32_t colLen = colEnd + 1;
1.163 + uint32_t* row = aEntries + rowIdx * colLen;
1.164 + uint32_t dist = row[colIdx]; // current Levenshtein distance
1.165 + while (rowIdx && colIdx) { // stop when we can't move diagonally
1.166 + if (aStr1[colIdx - 1] == aStr2[rowIdx - 1]) { // match
1.167 + if (rowIdx < rowEnd) { // deal with any pending insertion
1.168 + FireInsertEvent(Substring(aStr2, rowIdx, rowEnd - rowIdx),
1.169 + rowIdx, aEvents);
1.170 + }
1.171 + if (colIdx < colEnd) { // deal with any pending deletion
1.172 + FireDeleteEvent(Substring(aStr1, colIdx, colEnd - colIdx),
1.173 + rowIdx, aEvents);
1.174 + }
1.175 +
1.176 + colEnd = --colIdx; // reset the match point
1.177 + rowEnd = --rowIdx;
1.178 + row -= colLen;
1.179 + continue;
1.180 + }
1.181 + --dist;
1.182 + if (dist == row[colIdx - 1 - colLen]) { // substitution
1.183 + --colIdx;
1.184 + --rowIdx;
1.185 + row -= colLen;
1.186 + continue;
1.187 + }
1.188 + if (dist == row[colIdx - colLen]) { // insertion
1.189 + --rowIdx;
1.190 + row -= colLen;
1.191 + continue;
1.192 + }
1.193 + if (dist == row[colIdx - 1]) { // deletion
1.194 + --colIdx;
1.195 + continue;
1.196 + }
1.197 + NS_NOTREACHED("huh?");
1.198 + return;
1.199 + }
1.200 +
1.201 + if (rowEnd)
1.202 + FireInsertEvent(Substring(aStr2, 0, rowEnd), 0, aEvents);
1.203 + if (colEnd)
1.204 + FireDeleteEvent(Substring(aStr1, 0, colEnd), 0, aEvents);
1.205 +}
