accessible/base/NotificationController.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 "NotificationController.h"
   7
   8 #include "CacheConstants.h"
   9 #include "DocAccessible-inl.h"
  10 #include "DocAccessibleChild.h"
  11 #include "nsEventShell.h"
  12 #include "TextLeafAccessible.h"
  13 #include "TextUpdater.h"
  14
  15 #include "nsIContentInlines.h"
  16
  17 #include "mozilla/dom/BrowserChild.h"
  18 #include "mozilla/dom/Element.h"
  19 #include "mozilla/PresShell.h"
  20 #include "mozilla/ProfilerLabels.h"
  21 #include "mozilla/StaticPrefs_accessibility.h"
  22 #include "mozilla/Telemetry.h"
  23
  24 using namespace mozilla;
  25 using namespace mozilla::a11y;
  26 using namespace mozilla::dom;
  27
  28 ////////////////////////////////////////////////////////////////////////////////
  29 // NotificationCollector
  30 ////////////////////////////////////////////////////////////////////////////////
  31
  32 NotificationController::NotificationController(DocAccessible* aDocument,
  33                                                PresShell* aPresShell)
  34     : EventQueue(aDocument),
  35       mObservingState(eNotObservingRefresh),
  36       mPresShell(aPresShell),
  37       mEventGeneration(0) {
  38 #ifdef DEBUG
  39   mMoveGuardOnStack = false;
  40 #endif
  41
  42   // Schedule initial accessible tree construction.
  43   ScheduleProcessing();
  44 }
  45
  46 NotificationController::~NotificationController() {
  47   NS_ASSERTION(!mDocument, "Controller wasn't shutdown properly!");
  48   if (mDocument) Shutdown();
  49 }
  50
  51 ////////////////////////////////////////////////////////////////////////////////
  52 // NotificationCollector: AddRef/Release and cycle collection
  53
  54 NS_IMPL_CYCLE_COLLECTING_NATIVE_ADDREF(NotificationController)
  55 NS_IMPL_CYCLE_COLLECTING_NATIVE_RELEASE(NotificationController)
  56
  57 NS_IMPL_CYCLE_COLLECTION_CLASS(NotificationController)
  58
  59 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(NotificationController)
  60   if (tmp->mDocument) tmp->Shutdown();
  61 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
  62
  63 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(NotificationController)
  64   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mHangingChildDocuments)
  65   for (const auto& entry : tmp->mContentInsertions) {
  66     NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(cb, "mContentInsertions key");
  67     cb.NoteXPCOMChild(entry.GetKey());
  68     nsTArray<nsCOMPtr<nsIContent>>* list = entry.GetData().get();
  69     for (uint32_t i = 0; i < list->Length(); i++) {
  70       NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(cb, "mContentInsertions value item");
  71       cb.NoteXPCOMChild(list->ElementAt(i));
  72     }
  73   }
  74   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mFocusEvent)
  75   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mEvents)
  76   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mRelocations)
  77 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
  78
  79 NS_IMPL_CYCLE_COLLECTION_ROOT_NATIVE(NotificationController, AddRef)
  80 NS_IMPL_CYCLE_COLLECTION_UNROOT_NATIVE(NotificationController, Release)
  81
  82 ////////////////////////////////////////////////////////////////////////////////
  83 // NotificationCollector: public
  84
  85 void NotificationController::Shutdown() {
  86   if (mObservingState != eNotObservingRefresh &&
  87       mPresShell->RemoveRefreshObserver(this, FlushType::Display)) {
  88     mObservingState = eNotObservingRefresh;
  89   }
  90
  91   // Shutdown handling child documents.
  92   int32_t childDocCount = mHangingChildDocuments.Length();
  93   for (int32_t idx = childDocCount - 1; idx >= 0; idx--) {
  94     if (!mHangingChildDocuments[idx]->IsDefunct()) {
  95       mHangingChildDocuments[idx]->Shutdown();
  96     }
  97   }
  98
  99   mHangingChildDocuments.Clear();
 100
 101   mDocument = nullptr;
 102   mPresShell = nullptr;
 103
 104   mTextHash.Clear();
 105   mContentInsertions.Clear();
 106   mNotifications.Clear();
 107   mFocusEvent = nullptr;
 108   mEvents.Clear();
 109   mRelocations.Clear();
 110   mEventTree.Clear();
 111 }
 112
 113 EventTree* NotificationController::QueueMutation(LocalAccessible* aContainer) {
 114   EventTree* tree = mEventTree.FindOrInsert(aContainer);
 115   if (tree) {
 116     ScheduleProcessing();
 117   }
 118   return tree;
 119 }
 120
 121 void NotificationController::CoalesceHideEvent(AccHideEvent* aHideEvent) {
 122   LocalAccessible* parent = aHideEvent->LocalParent();
 123   while (parent) {
 124     if (parent->IsDoc()) {
 125       break;
 126     }
 127
 128     if (parent->HideEventTarget()) {
 129       DropMutationEvent(aHideEvent);
 130       break;
 131     }
 132
 133     if (parent->ShowEventTarget()) {
 134       AccShowEvent* showEvent =
 135           downcast_accEvent(mMutationMap.GetEvent(parent, EventMap::ShowEvent));
 136       if (showEvent->EventGeneration() < aHideEvent->EventGeneration()) {
 137         DropMutationEvent(aHideEvent);
 138         break;
 139       }
 140     }
 141
 142     parent = parent->LocalParent();
 143   }
 144 }
 145
 146 bool NotificationController::QueueMutationEvent(AccTreeMutationEvent* aEvent) {
 147   if (aEvent->GetEventType() == nsIAccessibleEvent::EVENT_HIDE) {
 148     // We have to allow there to be a hide and then a show event for a target
 149     // because of targets getting moved.  However we need to coalesce a show and
 150     // then a hide for a target which means we need to check for that here.
 151     if (aEvent->GetAccessible()->ShowEventTarget()) {
 152       AccTreeMutationEvent* showEvent =
 153           mMutationMap.GetEvent(aEvent->GetAccessible(), EventMap::ShowEvent);
 154       DropMutationEvent(showEvent);
 155       return false;
 156     }
 157
 158     // If this is an additional hide event, the accessible may be hidden, or
 159     // moved again after a move. Preserve the original hide event since
 160     // its properties are consistent with the tree that existed before
 161     // the next batch of mutation events is processed.
 162     if (aEvent->GetAccessible()->HideEventTarget()) {
 163       return false;
 164     }
 165   }
 166
 167   AccMutationEvent* mutEvent = downcast_accEvent(aEvent);
 168   mEventGeneration++;
 169   mutEvent->SetEventGeneration(mEventGeneration);
 170
 171   if (!mFirstMutationEvent) {
 172     mFirstMutationEvent = aEvent;
 173     ScheduleProcessing();
 174   }
 175
 176   if (mLastMutationEvent) {
 177     NS_ASSERTION(!mLastMutationEvent->NextEvent(),
 178                  "why isn't the last event the end?");
 179     mLastMutationEvent->SetNextEvent(aEvent);
 180   }
 181
 182   aEvent->SetPrevEvent(mLastMutationEvent);
 183   mLastMutationEvent = aEvent;
 184   mMutationMap.PutEvent(aEvent);
 185
 186   // Because we could be hiding the target of a show event we need to get rid
 187   // of any such events.
 188   if (aEvent->GetEventType() == nsIAccessibleEvent::EVENT_HIDE) {
 189     CoalesceHideEvent(downcast_accEvent(aEvent));
 190
 191     // mLastMutationEvent will point to something other than aEvent if and only
 192     // if aEvent was just coalesced away.  In that case a parent accessible
 193     // must already have the required reorder and text change events so we are
 194     // done here.
 195     if (mLastMutationEvent != aEvent) {
 196       return false;
 197     }
 198   }
 199
 200   // We need to fire a reorder event after all of the events targeted at shown
 201   // or hidden children of a container.  So either queue a new one, or move an
 202   // existing one to the end of the queue if the container already has a
 203   // reorder event.
 204   LocalAccessible* target = aEvent->GetAccessible();
 205   LocalAccessible* container = aEvent->GetAccessible()->LocalParent();
 206   RefPtr<AccReorderEvent> reorder;
 207   if (!container->ReorderEventTarget()) {
 208     reorder = new AccReorderEvent(container);
 209     container->SetReorderEventTarget(true);
 210     mMutationMap.PutEvent(reorder);
 211
 212     // Since this is the first child of container that is changing, the name
 213     // and/or description of dependent Accessibles may be changing.
 214     if (PushNameOrDescriptionChange(target)) {
 215       ScheduleProcessing();
 216     }
 217   } else {
 218     AccReorderEvent* event = downcast_accEvent(
 219         mMutationMap.GetEvent(container, EventMap::ReorderEvent));
 220     reorder = event;
 221     if (mFirstMutationEvent == event) {
 222       mFirstMutationEvent = event->NextEvent();
 223     } else {
 224       event->PrevEvent()->SetNextEvent(event->NextEvent());
 225     }
 226
 227     event->NextEvent()->SetPrevEvent(event->PrevEvent());
 228     event->SetNextEvent(nullptr);
 229   }
 230
 231   reorder->SetEventGeneration(mEventGeneration);
 232   reorder->SetPrevEvent(mLastMutationEvent);
 233   mLastMutationEvent->SetNextEvent(reorder);
 234   mLastMutationEvent = reorder;
 235
 236   // It is not possible to have a text change event for something other than a
 237   // hyper text accessible.
 238   if (!container->IsHyperText()) {
 239     return true;
 240   }
 241
 242   MOZ_ASSERT(mutEvent);
 243
 244   nsString text;
 245   aEvent->GetAccessible()->AppendTextTo(text);
 246   if (text.IsEmpty()) {
 247     return true;
 248   }
 249
 250   int32_t offset = container->AsHyperText()->GetChildOffset(target);
 251   AccTreeMutationEvent* prevEvent = aEvent->PrevEvent();
 252   while (prevEvent &&
 253          prevEvent->GetEventType() == nsIAccessibleEvent::EVENT_REORDER) {
 254     prevEvent = prevEvent->PrevEvent();
 255   }
 256
 257   if (prevEvent &&
 258       prevEvent->GetEventType() == nsIAccessibleEvent::EVENT_HIDE &&
 259       mutEvent->IsHide()) {
 260     AccHideEvent* prevHide = downcast_accEvent(prevEvent);
 261     AccTextChangeEvent* prevTextChange = prevHide->mTextChangeEvent;
 262     if (prevTextChange && prevHide->LocalParent() == mutEvent->LocalParent()) {
 263       if (prevHide->mNextSibling == target) {
 264         target->AppendTextTo(prevTextChange->mModifiedText);
 265         prevHide->mTextChangeEvent.swap(mutEvent->mTextChangeEvent);
 266       } else if (prevHide->mPrevSibling == target) {
 267         nsString temp;
 268         target->AppendTextTo(temp);
 269
 270         uint32_t extraLen = temp.Length();
 271         temp += prevTextChange->mModifiedText;
 272         ;
 273         prevTextChange->mModifiedText = temp;
 274         prevTextChange->mStart -= extraLen;
 275         prevHide->mTextChangeEvent.swap(mutEvent->mTextChangeEvent);
 276       }
 277     }
 278   } else if (prevEvent && mutEvent->IsShow() &&
 279              prevEvent->GetEventType() == nsIAccessibleEvent::EVENT_SHOW) {
 280     AccShowEvent* prevShow = downcast_accEvent(prevEvent);
 281     AccTextChangeEvent* prevTextChange = prevShow->mTextChangeEvent;
 282     if (prevTextChange && prevShow->LocalParent() == target->LocalParent()) {
 283       int32_t index = target->IndexInParent();
 284       int32_t prevIndex = prevShow->GetAccessible()->IndexInParent();
 285       if (prevIndex + 1 == index) {
 286         target->AppendTextTo(prevTextChange->mModifiedText);
 287         prevShow->mTextChangeEvent.swap(mutEvent->mTextChangeEvent);
 288       } else if (index + 1 == prevIndex) {
 289         nsString temp;
 290         target->AppendTextTo(temp);
 291         prevTextChange->mStart -= temp.Length();
 292         temp += prevTextChange->mModifiedText;
 293         prevTextChange->mModifiedText = temp;
 294         prevShow->mTextChangeEvent.swap(mutEvent->mTextChangeEvent);
 295       }
 296     }
 297   }
 298
 299   if (!mutEvent->mTextChangeEvent) {
 300     mutEvent->mTextChangeEvent = new AccTextChangeEvent(
 301         container, offset, text, mutEvent->IsShow(),
 302         aEvent->mIsFromUserInput ? eFromUserInput : eNoUserInput);
 303   }
 304
 305   return true;
 306 }
 307
 308 void NotificationController::DropMutationEvent(AccTreeMutationEvent* aEvent) {
 309   if (aEvent->GetEventType() == nsIAccessibleEvent::EVENT_REORDER) {
 310     // We don't fully drop reorder events, we just change them to inner reorder
 311     // events.
 312     AccReorderEvent* reorderEvent = downcast_accEvent(aEvent);
 313
 314     MOZ_ASSERT(reorderEvent);
 315     reorderEvent->SetInner();
 316     return;
 317   } else if (aEvent->GetEventType() == nsIAccessibleEvent::EVENT_SHOW) {
 318     // unset the event bits since the event isn't being fired any more.
 319     aEvent->GetAccessible()->SetShowEventTarget(false);
 320   } else {
 321     // unset the event bits since the event isn't being fired any more.
 322     aEvent->GetAccessible()->SetHideEventTarget(false);
 323
 324     AccHideEvent* hideEvent = downcast_accEvent(aEvent);
 325     MOZ_ASSERT(hideEvent);
 326
 327     if (hideEvent->NeedsShutdown()) {
 328       mDocument->ShutdownChildrenInSubtree(aEvent->GetAccessible());
 329     }
 330   }
 331
 332   // Do the work to splice the event out of the list.
 333   if (mFirstMutationEvent == aEvent) {
 334     mFirstMutationEvent = aEvent->NextEvent();
 335   } else {
 336     aEvent->PrevEvent()->SetNextEvent(aEvent->NextEvent());
 337   }
 338
 339   if (mLastMutationEvent == aEvent) {
 340     mLastMutationEvent = aEvent->PrevEvent();
 341   } else {
 342     aEvent->NextEvent()->SetPrevEvent(aEvent->PrevEvent());
 343   }
 344
 345   aEvent->SetPrevEvent(nullptr);
 346   aEvent->SetNextEvent(nullptr);
 347   mMutationMap.RemoveEvent(aEvent);
 348 }
 349
 350 void NotificationController::CoalesceMutationEvents() {
 351   AccTreeMutationEvent* event = mFirstMutationEvent;
 352   while (event) {
 353     AccTreeMutationEvent* nextEvent = event->NextEvent();
 354     uint32_t eventType = event->GetEventType();
 355     if (event->GetEventType() == nsIAccessibleEvent::EVENT_REORDER) {
 356       LocalAccessible* acc = event->GetAccessible();
 357       while (acc) {
 358         if (acc->IsDoc()) {
 359           break;
 360         }
 361
 362         // if a parent of the reorder event's target is being hidden that
 363         // hide event's target must have a parent that is also a reorder event
 364         // target.  That means we don't need this reorder event.
 365         if (acc->HideEventTarget()) {
 366           DropMutationEvent(event);
 367           break;
 368         }
 369
 370         LocalAccessible* parent = acc->LocalParent();
 371         if (parent && parent->ReorderEventTarget()) {
 372           AccReorderEvent* reorder = downcast_accEvent(
 373               mMutationMap.GetEvent(parent, EventMap::ReorderEvent));
 374
 375           // We want to make sure that a reorder event comes after any show or
 376           // hide events targeted at the children of its target.  We keep the
 377           // invariant that event generation goes up as you are farther in the
 378           // queue, so we want to use the spot of the event with the higher
 379           // generation number, and keep that generation number.
 380           if (reorder &&
 381               reorder->EventGeneration() < event->EventGeneration()) {
 382             reorder->SetEventGeneration(event->EventGeneration());
 383
 384             // It may be true that reorder was before event, and we coalesced
 385             // away all the show / hide events between them.  In that case
 386             // event is already immediately after reorder in the queue and we
 387             // do not need to rearrange the list of events.
 388             if (event != reorder->NextEvent()) {
 389               // There really should be a show or hide event before the first
 390               // reorder event.
 391               if (reorder->PrevEvent()) {
 392                 reorder->PrevEvent()->SetNextEvent(reorder->NextEvent());
 393               } else {
 394                 mFirstMutationEvent = reorder->NextEvent();
 395               }
 396
 397               reorder->NextEvent()->SetPrevEvent(reorder->PrevEvent());
 398               event->PrevEvent()->SetNextEvent(reorder);
 399               reorder->SetPrevEvent(event->PrevEvent());
 400               event->SetPrevEvent(reorder);
 401               reorder->SetNextEvent(event);
 402             }
 403           }
 404           DropMutationEvent(event);
 405           break;
 406         }
 407
 408         acc = parent;
 409       }
 410     } else if (eventType == nsIAccessibleEvent::EVENT_SHOW) {
 411       LocalAccessible* parent = event->GetAccessible()->LocalParent();
 412       while (parent) {
 413         if (parent->IsDoc()) {
 414           break;
 415         }
 416
 417         // if the parent of a show event is being either shown or hidden then
 418         // we don't need to fire a show event for a subtree of that change.
 419         if (parent->ShowEventTarget() || parent->HideEventTarget()) {
 420           DropMutationEvent(event);
 421           break;
 422         }
 423
 424         parent = parent->LocalParent();
 425       }
 426     } else if (eventType == nsIAccessibleEvent::EVENT_HIDE) {
 427       MOZ_ASSERT(eventType == nsIAccessibleEvent::EVENT_HIDE,
 428                  "mutation event list has an invalid event");
 429
 430       AccHideEvent* hideEvent = downcast_accEvent(event);
 431       CoalesceHideEvent(hideEvent);
 432     }
 433
 434     event = nextEvent;
 435   }
 436 }
 437
 438 void NotificationController::ScheduleChildDocBinding(DocAccessible* aDocument) {
 439   // Schedule child document binding to the tree.
 440   mHangingChildDocuments.AppendElement(aDocument);
 441   ScheduleProcessing();
 442 }
 443
 444 void NotificationController::ScheduleContentInsertion(
 445     LocalAccessible* aContainer, nsTArray<nsCOMPtr<nsIContent>>& aInsertions) {
 446   if (!aInsertions.IsEmpty()) {
 447     mContentInsertions.GetOrInsertNew(aContainer)->AppendElements(aInsertions);
 448     ScheduleProcessing();
 449   }
 450 }
 451
 452 void NotificationController::ScheduleProcessing() {
 453   // If notification flush isn't planed yet start notification flush
 454   // asynchronously (after style and layout).
 455   if (mObservingState == eNotObservingRefresh) {
 456     if (mPresShell->AddRefreshObserver(this, FlushType::Display,
 457                                        "Accessibility notifications")) {
 458       mObservingState = eRefreshObserving;
 459     }
 460   }
 461 }
 462
 463 ////////////////////////////////////////////////////////////////////////////////
 464 // NotificationCollector: protected
 465
 466 bool NotificationController::IsUpdatePending() {
 467   return mPresShell->IsLayoutFlushObserver() ||
 468          mObservingState == eRefreshProcessingForUpdate || WaitingForParent() ||
 469          mContentInsertions.Count() != 0 || mNotifications.Length() != 0 ||
 470          mTextHash.Count() != 0 ||
 471          !mDocument->HasLoadState(DocAccessible::eTreeConstructed);
 472 }
 473
 474 bool NotificationController::WaitingForParent() {
 475   DocAccessible* parentdoc = mDocument->ParentDocument();
 476   if (!parentdoc) {
 477     return false;
 478   }
 479
 480   NotificationController* parent = parentdoc->mNotificationController;
 481   if (!parent || parent == this) {
 482     // Do not wait for nothing or ourselves
 483     return false;
 484   }
 485
 486   // Wait for parent's notifications processing
 487   return parent->mContentInsertions.Count() != 0 ||
 488          parent->mNotifications.Length() != 0;
 489 }
 490
 491 void NotificationController::ProcessMutationEvents() {
 492   // there is no reason to fire a hide event for a child of a show event
 493   // target.  That can happen if something is inserted into the tree and
 494   // removed before the next refresh driver tick, but it should not be
 495   // observable outside gecko so it should be safe to coalesce away any such
 496   // events.  This means that it should be fine to fire all of the hide events
 497   // first, and then deal with any shown subtrees.
 498   for (AccTreeMutationEvent* event = mFirstMutationEvent; event;
 499        event = event->NextEvent()) {
 500     if (event->GetEventType() != nsIAccessibleEvent::EVENT_HIDE) {
 501       continue;
 502     }
 503
 504     nsEventShell::FireEvent(event);
 505     if (!mDocument) {
 506       return;
 507     }
 508
 509     AccMutationEvent* mutEvent = downcast_accEvent(event);
 510     if (mutEvent->mTextChangeEvent) {
 511       nsEventShell::FireEvent(mutEvent->mTextChangeEvent);
 512       if (!mDocument) {
 513         return;
 514       }
 515     }
 516
 517     // Fire menupopup end event before a hide event if a menu goes away.
 518
 519     // XXX: We don't look into children of hidden subtree to find hiding
 520     // menupopup (as we did prior bug 570275) because we don't do that when
 521     // menu is showing (and that's impossible until bug 606924 is fixed).
 522     // Nevertheless we should do this at least because layout coalesces
 523     // the changes before our processing and we may miss some menupopup
 524     // events. Now we just want to be consistent in content insertion/removal
 525     // handling.
 526     if (event->mAccessible->ARIARole() == roles::MENUPOPUP) {
 527       nsEventShell::FireEvent(nsIAccessibleEvent::EVENT_MENUPOPUP_END,
 528                               event->mAccessible);
 529       if (!mDocument) {
 530         return;
 531       }
 532     }
 533
 534     AccHideEvent* hideEvent = downcast_accEvent(event);
 535     if (hideEvent->NeedsShutdown()) {
 536       mDocument->ShutdownChildrenInSubtree(event->mAccessible);
 537     }
 538   }
 539
 540   // Group the show events by the parent of their target.
 541   nsTHashMap<nsPtrHashKey<LocalAccessible>, nsTArray<AccTreeMutationEvent*>>
 542       showEvents;
 543   for (AccTreeMutationEvent* event = mFirstMutationEvent; event;
 544        event = event->NextEvent()) {
 545     if (event->GetEventType() != nsIAccessibleEvent::EVENT_SHOW) {
 546       continue;
 547     }
 548
 549     LocalAccessible* parent = event->GetAccessible()->LocalParent();
 550     showEvents.LookupOrInsert(parent).AppendElement(event);
 551   }
 552
 553   // We need to fire show events for the children of an accessible in the order
 554   // of their indices at this point.  So sort each set of events for the same
 555   // container by the index of their target.
 556   for (auto iter = showEvents.Iter(); !iter.Done(); iter.Next()) {
 557     struct AccIdxComparator {
 558       bool LessThan(const AccTreeMutationEvent* a,
 559                     const AccTreeMutationEvent* b) const {
 560         int32_t aIdx = a->GetAccessible()->IndexInParent();
 561         int32_t bIdx = b->GetAccessible()->IndexInParent();
 562         MOZ_ASSERT(aIdx >= 0 && bIdx >= 0 && aIdx != bIdx);
 563         return aIdx < bIdx;
 564       }
 565       bool Equals(const AccTreeMutationEvent* a,
 566                   const AccTreeMutationEvent* b) const {
 567         DebugOnly<int32_t> aIdx = a->GetAccessible()->IndexInParent();
 568         DebugOnly<int32_t> bIdx = b->GetAccessible()->IndexInParent();
 569         MOZ_ASSERT(aIdx >= 0 && bIdx >= 0 && aIdx != bIdx);
 570         return false;
 571       }
 572     };
 573
 574     nsTArray<AccTreeMutationEvent*>& events = iter.Data();
 575     events.Sort(AccIdxComparator());
 576     for (AccTreeMutationEvent* event : events) {
 577       nsEventShell::FireEvent(event);
 578       if (!mDocument) {
 579         return;
 580       }
 581
 582       AccMutationEvent* mutEvent = downcast_accEvent(event);
 583       if (mutEvent->mTextChangeEvent) {
 584         nsEventShell::FireEvent(mutEvent->mTextChangeEvent);
 585         if (!mDocument) {
 586           return;
 587         }
 588       }
 589     }
 590   }
 591
 592   // Now we can fire the reorder events after all the show and hide events.
 593   for (const uint32_t reorderType : {nsIAccessibleEvent::EVENT_INNER_REORDER,
 594                                      nsIAccessibleEvent::EVENT_REORDER}) {
 595     for (AccTreeMutationEvent* event = mFirstMutationEvent; event;
 596          event = event->NextEvent()) {
 597       if (event->GetEventType() != reorderType) {
 598         continue;
 599       }
 600
 601       if (event->GetAccessible()->IsDefunct()) {
 602         // An inner reorder target may have been hidden itself and no
 603         // longer bound to the document.
 604         MOZ_ASSERT(reorderType == nsIAccessibleEvent::EVENT_INNER_REORDER,
 605                    "An 'outer' reorder target should not be defunct");
 606         continue;
 607       }
 608
 609       nsEventShell::FireEvent(event);
 610       if (!mDocument) {
 611         return;
 612       }
 613
 614       LocalAccessible* target = event->GetAccessible();
 615       target->Document()->MaybeNotifyOfValueChange(target);
 616       if (!mDocument) {
 617         return;
 618       }
 619     }
 620   }
 621 }
 622
 623 ////////////////////////////////////////////////////////////////////////////////
 624 // NotificationCollector: private
 625
 626 void NotificationController::WillRefresh(mozilla::TimeStamp aTime) {
 627   Telemetry::AutoTimer<Telemetry::A11Y_TREE_UPDATE_TIMING_MS> timer;
 628
 629   AUTO_PROFILER_LABEL("NotificationController::WillRefresh", OTHER);
 630
 631   // If the document accessible that notification collector was created for is
 632   // now shut down, don't process notifications anymore.
 633   NS_ASSERTION(
 634       mDocument,
 635       "The document was shut down while refresh observer is attached!");
 636   if (!mDocument) return;
 637
 638   // Wait until an update, we have started, or an interruptible reflow is
 639   // finished.
 640   if (mObservingState == eRefreshProcessing ||
 641       mObservingState == eRefreshProcessingForUpdate ||
 642       mPresShell->IsReflowInterrupted()) {
 643     return;
 644   }
 645
 646   // Process parent's notifications before ours, to get proper ordering between
 647   // e.g. tab event and content event.
 648   if (WaitingForParent()) {
 649     mDocument->ParentDocument()->mNotificationController->WillRefresh(aTime);
 650     if (!mDocument) {
 651       return;
 652     }
 653   }
 654
 655   // Any generic notifications should be queued if we're processing content
 656   // insertions or generic notifications.
 657   mObservingState = eRefreshProcessingForUpdate;
 658
 659   // Initial accessible tree construction.
 660   if (!mDocument->HasLoadState(DocAccessible::eTreeConstructed)) {
 661     // If document is not bound to parent at this point then the document is not
 662     // ready yet (process notifications later).
 663     if (!mDocument->IsBoundToParent()) {
 664       mObservingState = eRefreshObserving;
 665       return;
 666     }
 667
 668 #ifdef A11Y_LOG
 669     if (logging::IsEnabled(logging::eTree)) {
 670       logging::MsgBegin("TREE", "initial tree created");
 671       logging::Address("document", mDocument);
 672       logging::MsgEnd();
 673     }
 674 #endif
 675
 676     mDocument->DoInitialUpdate();
 677
 678     NS_ASSERTION(mContentInsertions.Count() == 0,
 679                  "Pending content insertions while initial accessible tree "
 680                  "isn't created!");
 681   }
 682
 683   mDocument->ProcessPendingUpdates();
 684
 685   // Process rendered text change notifications.
 686   for (nsIContent* textNode : mTextHash) {
 687     LocalAccessible* textAcc = mDocument->GetAccessible(textNode);
 688
 689     // If the text node is not in tree or doesn't have a frame, or placed in
 690     // another document, then this case should have been handled already by
 691     // content removal notifications.
 692     nsINode* containerNode = textNode->GetFlattenedTreeParentNode();
 693     if (!containerNode || textNode->OwnerDoc() != mDocument->DocumentNode()) {
 694       MOZ_ASSERT(!textAcc,
 695                  "Text node was removed but accessible is kept alive!");
 696       continue;
 697     }
 698
 699     nsIFrame* textFrame = textNode->GetPrimaryFrame();
 700     if (!textFrame) {
 701       MOZ_ASSERT(!textAcc,
 702                  "Text node isn't rendered but accessible is kept alive!");
 703       continue;
 704     }
 705
 706 #ifdef A11Y_LOG
 707     nsIContent* containerElm =
 708         containerNode->IsElement() ? containerNode->AsElement() : nullptr;
 709 #endif
 710
 711     nsIFrame::RenderedText text = textFrame->GetRenderedText(
 712         0, UINT32_MAX, nsIFrame::TextOffsetType::OffsetsInContentText,
 713         nsIFrame::TrailingWhitespace::DontTrim);
 714
 715     // Remove text accessible if rendered text is empty.
 716     if (textAcc) {
 717       if (text.mString.IsEmpty()) {
 718 #ifdef A11Y_LOG
 719         if (logging::IsEnabled(logging::eTree | logging::eText)) {
 720           logging::MsgBegin("TREE", "text node lost its content; doc: %p",
 721                             mDocument);
 722           logging::Node("container", containerElm);
 723           logging::Node("content", textNode);
 724           logging::MsgEnd();
 725         }
 726 #endif
 727
 728         mDocument->ContentRemoved(textAcc);
 729         continue;
 730       }
 731
 732       // Update text of the accessible and fire text change events.
 733 #ifdef A11Y_LOG
 734       if (logging::IsEnabled(logging::eText)) {
 735         logging::MsgBegin("TEXT", "text may be changed; doc: %p", mDocument);
 736         logging::Node("container", containerElm);
 737         logging::Node("content", textNode);
 738         logging::MsgEntry(
 739             "old text '%s'",
 740             NS_ConvertUTF16toUTF8(textAcc->AsTextLeaf()->Text()).get());
 741         logging::MsgEntry("new text: '%s'",
 742                           NS_ConvertUTF16toUTF8(text.mString).get());
 743         logging::MsgEnd();
 744       }
 745 #endif
 746
 747       TextUpdater::Run(mDocument, textAcc->AsTextLeaf(), text.mString);
 748       if (IPCAccessibilityActive() &&
 749           StaticPrefs::accessibility_cache_enabled_AtStartup()) {
 750         mDocument->QueueCacheUpdate(textAcc, CacheDomain::Text);
 751       }
 752       continue;
 753     }
 754
 755     // Append an accessible if rendered text is not empty.
 756     if (!text.mString.IsEmpty()) {
 757 #ifdef A11Y_LOG
 758       if (logging::IsEnabled(logging::eTree | logging::eText)) {
 759         logging::MsgBegin("TREE", "text node gains new content; doc: %p",
 760                           mDocument);
 761         logging::Node("container", containerElm);
 762         logging::Node("content", textNode);
 763         logging::MsgEnd();
 764       }
 765 #endif
 766
 767       MOZ_ASSERT(mDocument->AccessibleOrTrueContainer(containerNode),
 768                  "Text node having rendered text hasn't accessible document!");
 769
 770       LocalAccessible* container =
 771           mDocument->AccessibleOrTrueContainer(containerNode, true);
 772       if (container) {
 773         nsTArray<nsCOMPtr<nsIContent>>* list =
 774             mContentInsertions.GetOrInsertNew(container);
 775         list->AppendElement(textNode);
 776       }
 777     }
 778   }
 779   mTextHash.Clear();
 780
 781   // Process content inserted notifications to update the tree.
 782   // Processing an insertion can indirectly run script (e.g. querying a XUL
 783   // interface), which might result in another insertion being queued.
 784   // We don't want to lose any queued insertions if this happens. Therefore, we
 785   // move the current insertions into a temporary data structure and process
 786   // them from there. Any insertions queued during processing will get handled
 787   // in subsequent refresh driver ticks.
 788   const auto contentInsertions = std::move(mContentInsertions);
 789   for (const auto& entry : contentInsertions) {
 790     mDocument->ProcessContentInserted(entry.GetKey(), entry.GetData().get());
 791     if (!mDocument) {
 792       return;
 793     }
 794   }
 795
 796   // Bind hanging child documents unless we are using IPC and the
 797   // document has no IPC actor.  If we fail to bind the child doc then
 798   // shut it down.
 799   uint32_t hangingDocCnt = mHangingChildDocuments.Length();
 800   nsTArray<RefPtr<DocAccessible>> newChildDocs;
 801   for (uint32_t idx = 0; idx < hangingDocCnt; idx++) {
 802     DocAccessible* childDoc = mHangingChildDocuments[idx];
 803     if (childDoc->IsDefunct()) continue;
 804
 805     if (IPCAccessibilityActive() && !mDocument->IPCDoc()) {
 806       childDoc->Shutdown();
 807       continue;
 808     }
 809
 810     nsIContent* ownerContent = childDoc->DocumentNode()->GetEmbedderElement();
 811     if (ownerContent) {
 812       LocalAccessible* outerDocAcc = mDocument->GetAccessible(ownerContent);
 813       if (outerDocAcc && outerDocAcc->AppendChild(childDoc)) {
 814         if (mDocument->AppendChildDocument(childDoc)) {
 815           newChildDocs.AppendElement(std::move(mHangingChildDocuments[idx]));
 816           continue;
 817         }
 818
 819         outerDocAcc->RemoveChild(childDoc);
 820       }
 821
 822       // Failed to bind the child document, destroy it.
 823       childDoc->Shutdown();
 824     }
 825   }
 826
 827   // Clear the hanging documents list, even if we didn't bind them.
 828   mHangingChildDocuments.Clear();
 829   MOZ_ASSERT(mDocument, "Illicit document shutdown");
 830   if (!mDocument) {
 831     return;
 832   }
 833
 834   // If the document is ready and all its subdocuments are completely loaded
 835   // then process the document load.
 836   if (mDocument->HasLoadState(DocAccessible::eReady) &&
 837       !mDocument->HasLoadState(DocAccessible::eCompletelyLoaded) &&
 838       hangingDocCnt == 0) {
 839     uint32_t childDocCnt = mDocument->ChildDocumentCount(), childDocIdx = 0;
 840     for (; childDocIdx < childDocCnt; childDocIdx++) {
 841       DocAccessible* childDoc = mDocument->GetChildDocumentAt(childDocIdx);
 842       if (!childDoc->HasLoadState(DocAccessible::eCompletelyLoaded)) break;
 843     }
 844
 845     if (childDocIdx == childDocCnt) {
 846       mDocument->ProcessLoad();
 847       if (!mDocument) return;
 848     }
 849   }
 850
 851   // Process invalidation list of the document after all accessible tree
 852   // mutation is done.
 853   mDocument->ProcessInvalidationList();
 854
 855   // Process relocation list.
 856   for (uint32_t idx = 0; idx < mRelocations.Length(); idx++) {
 857     // owner should be in a document and have na associated DOM node (docs
 858     // sometimes don't)
 859     if (mRelocations[idx]->IsInDocument() &&
 860         mRelocations[idx]->HasOwnContent()) {
 861       mDocument->DoARIAOwnsRelocation(mRelocations[idx]);
 862     }
 863   }
 864   mRelocations.Clear();
 865
 866   // Process only currently queued generic notifications.
 867   // These are used for processing aria-activedescendant, DOMMenuItemActive,
 868   // etc. Therefore, they must be processed after relocations, since relocated
 869   // subtrees might not have been created before relocation processing and the
 870   // target might be inside a relocated subtree.
 871   const nsTArray<RefPtr<Notification>> notifications =
 872       std::move(mNotifications);
 873
 874   uint32_t notificationCount = notifications.Length();
 875   for (uint32_t idx = 0; idx < notificationCount; idx++) {
 876     notifications[idx]->Process();
 877     if (!mDocument) return;
 878   }
 879
 880   // If a generic notification occurs after this point then we may be allowed to
 881   // process it synchronously.  However we do not want to reenter if fireing
 882   // events causes script to run.
 883   mObservingState = eRefreshProcessing;
 884
 885   mDocument->SendAccessiblesWillMove();
 886
 887   // Send any queued cache updates before we fire any mutation events so the
 888   // cache is up to date when mutation events are fired. We do this after
 889   // insertions (but not their events) so that cache updates dependent on the
 890   // tree work correctly; e.g. line start calculation.
 891   if (IPCAccessibilityActive() && mDocument) {
 892     mDocument->ProcessQueuedCacheUpdates();
 893   }
 894
 895   CoalesceMutationEvents();
 896   ProcessMutationEvents();
 897   mEventGeneration = 0;
 898
 899   // Now that we are done with them get rid of the events we fired.
 900   RefPtr<AccTreeMutationEvent> mutEvent = std::move(mFirstMutationEvent);
 901   mLastMutationEvent = nullptr;
 902   mFirstMutationEvent = nullptr;
 903   while (mutEvent) {
 904     RefPtr<AccTreeMutationEvent> nextEvent = mutEvent->NextEvent();
 905     LocalAccessible* target = mutEvent->GetAccessible();
 906
 907     // We need to be careful here, while it may seem that we can simply 0 all
 908     // the pending event bits that is not true.  Because accessibles may be
 909     // reparented they may be the target of both a hide event and a show event
 910     // at the same time.
 911     if (mutEvent->GetEventType() == nsIAccessibleEvent::EVENT_SHOW) {
 912       target->SetShowEventTarget(false);
 913     }
 914
 915     if (mutEvent->GetEventType() == nsIAccessibleEvent::EVENT_HIDE) {
 916       target->SetHideEventTarget(false);
 917     }
 918
 919     // However it is not possible for a reorder event target to also be the
 920     // target of a show or hide, so we can just zero that.
 921     target->SetReorderEventTarget(false);
 922
 923     mutEvent->SetPrevEvent(nullptr);
 924     mutEvent->SetNextEvent(nullptr);
 925     mMutationMap.RemoveEvent(mutEvent);
 926     mutEvent = nextEvent;
 927   }
 928
 929   if (mDocument) {
 930     mDocument->ClearMovedAccessibles();
 931   }
 932
 933   ProcessEventQueue();
 934
 935   if (IPCAccessibilityActive()) {
 936     size_t newDocCount = newChildDocs.Length();
 937     for (size_t i = 0; i < newDocCount; i++) {
 938       DocAccessible* childDoc = newChildDocs[i];
 939       if (childDoc->IsDefunct()) {
 940         continue;
 941       }
 942
 943       LocalAccessible* parent = childDoc->LocalParent();
 944       DocAccessibleChild* parentIPCDoc = mDocument->IPCDoc();
 945       MOZ_DIAGNOSTIC_ASSERT(parentIPCDoc);
 946       uint64_t id = reinterpret_cast<uintptr_t>(parent->UniqueID());
 947       MOZ_DIAGNOSTIC_ASSERT(id);
 948       DocAccessibleChild* ipcDoc = childDoc->IPCDoc();
 949       if (ipcDoc) {
 950         parentIPCDoc->SendBindChildDoc(ipcDoc, id);
 951         continue;
 952       }
 953
 954       ipcDoc = new DocAccessibleChild(childDoc, parentIPCDoc->Manager());
 955       childDoc->SetIPCDoc(ipcDoc);
 956
 957 #if defined(XP_WIN)
 958       parentIPCDoc->ConstructChildDocInParentProcess(
 959           ipcDoc, id,
 960           StaticPrefs::accessibility_cache_enabled_AtStartup()
 961               ? 0
 962               : MsaaAccessible::GetChildIDFor(childDoc));
 963 #else
 964       nsCOMPtr<nsIBrowserChild> browserChild =
 965           do_GetInterface(mDocument->DocumentNode()->GetDocShell());
 966       if (browserChild) {
 967         static_cast<BrowserChild*>(browserChild.get())
 968             ->SendPDocAccessibleConstructor(ipcDoc, parentIPCDoc, id, 0, 0);
 969         ipcDoc->SendPDocAccessiblePlatformExtConstructor();
 970       }
 971 #endif
 972     }
 973   }
 974
 975   mObservingState = eRefreshObserving;
 976   if (!mDocument) return;
 977
 978   // Stop further processing if there are no new notifications of any kind or
 979   // events and document load is processed.
 980   if (mContentInsertions.Count() == 0 && mNotifications.IsEmpty() &&
 981       !mFocusEvent && mEvents.IsEmpty() && mTextHash.Count() == 0 &&
 982       mHangingChildDocuments.IsEmpty() &&
 983       mDocument->HasLoadState(DocAccessible::eCompletelyLoaded) &&
 984       mPresShell->RemoveRefreshObserver(this, FlushType::Display)) {
 985     mObservingState = eNotObservingRefresh;
 986   }
 987 }
 988
 989 void NotificationController::EventMap::PutEvent(AccTreeMutationEvent* aEvent) {
 990   EventType type = GetEventType(aEvent);
 991   uint64_t addr = reinterpret_cast<uintptr_t>(aEvent->GetAccessible());
 992   MOZ_ASSERT((addr & 0x3) == 0, "accessible is not 4 byte aligned");
 993   addr |= type;
 994   mTable.InsertOrUpdate(addr, RefPtr{aEvent});
 995 }
 996
 997 AccTreeMutationEvent* NotificationController::EventMap::GetEvent(
 998     LocalAccessible* aTarget, EventType aType) {
 999   uint64_t addr = reinterpret_cast<uintptr_t>(aTarget);
1000   MOZ_ASSERT((addr & 0x3) == 0, "target is not 4 byte aligned");
1001
1002   addr |= aType;
1003   return mTable.GetWeak(addr);
1004 }
1005
1006 void NotificationController::EventMap::RemoveEvent(
1007     AccTreeMutationEvent* aEvent) {
1008   EventType type = GetEventType(aEvent);
1009   uint64_t addr = reinterpret_cast<uintptr_t>(aEvent->GetAccessible());
1010   MOZ_ASSERT((addr & 0x3) == 0, "accessible is not 4 byte aligned");
1011   addr |= type;
1012
1013   MOZ_ASSERT(mTable.GetWeak(addr) == aEvent, "mTable has the wrong event");
1014   mTable.Remove(addr);
1015 }
1016
1017 NotificationController::EventMap::EventType
1018 NotificationController::EventMap::GetEventType(AccTreeMutationEvent* aEvent) {
1019   switch (aEvent->GetEventType()) {
1020     case nsIAccessibleEvent::EVENT_SHOW:
1021       return ShowEvent;
1022     case nsIAccessibleEvent::EVENT_HIDE:
1023       return HideEvent;
1024     case nsIAccessibleEvent::EVENT_REORDER:
1025     case nsIAccessibleEvent::EVENT_INNER_REORDER:
1026       return ReorderEvent;
1027     default:
1028       MOZ_ASSERT_UNREACHABLE("event has invalid type");
1029       return ShowEvent;
1030   }
1031 }