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