accessible/base/TextUpdater.cpp

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