dali/internal/accessibility/bridge/bridge-accessible.cpp

   1 /*
   2  * Copyright (c) 2022 Samsung Electronics Co., Ltd.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *
  16  */
  17
  18 // CLASS HEADER
  19 #include <dali/internal/accessibility/bridge/bridge-accessible.h>
  20
  21 // EXTERNAL INCLUDES
  22 #include <dali/public-api/math/math-utils.h>
  23
  24 #include <algorithm>
  25 #include <iostream>
  26
  27 // INTERNAL INCLUDES
  28 #include <dali/devel-api/atspi-interfaces/accessible.h>
  29 #include <dali/devel-api/atspi-interfaces/component.h>
  30 #include <dali/devel-api/atspi-interfaces/selection.h>
  31 #include <dali/devel-api/atspi-interfaces/text.h>
  32 #include <dali/devel-api/atspi-interfaces/value.h>
  33
  34 //comment out 2 lines below to get more logs
  35 #undef LOG
  36 #define LOG() _LoggerEmpty()
  37
  38 using namespace Dali::Accessibility;
  39
  40 #define GET_NAVIGABLE_AT_POINT_MAX_RECURSION_DEPTH 10000
  41
  42 namespace
  43 {
  44 bool SortVertically(Component* lhs, Component* rhs)
  45 {
  46   auto leftRect  = lhs->GetExtents(CoordinateType::WINDOW);
  47   auto rightRect = rhs->GetExtents(CoordinateType::WINDOW);
  48
  49   return leftRect.y < rightRect.y;
  50 }
  51
  52 bool SortHorizontally(Component* lhs, Component* rhs)
  53 {
  54   auto leftRect  = lhs->GetExtents(CoordinateType::WINDOW);
  55   auto rightRect = rhs->GetExtents(CoordinateType::WINDOW);
  56
  57   return leftRect.x < rightRect.x;
  58 }
  59
  60 std::vector<std::vector<Component*>> SplitLines(const std::vector<Component*>& children)
  61 {
  62   // Find first with non-zero area
  63   auto first = std::find_if(children.begin(), children.end(), [](Component* child) -> bool {
  64     auto extents = child->GetExtents(CoordinateType::WINDOW);
  65     return !Dali::EqualsZero(extents.height) && !Dali::EqualsZero(extents.width);
  66   });
  67
  68   if(first == children.end())
  69   {
  70     return {};
  71   }
  72
  73   std::vector<std::vector<Component*>> lines(1);
  74   Dali::Rect<>                         lineRect = (*first)->GetExtents(CoordinateType::WINDOW);
  75   Dali::Rect<>                         rect;
  76
  77   // Split into lines
  78   for(auto it = first; it != children.end(); ++it)
  79   {
  80     auto child = *it;
  81
  82     rect = child->GetExtents(CoordinateType::WINDOW);
  83     if(Dali::EqualsZero(rect.height) || Dali::EqualsZero(rect.width))
  84     {
  85       // Zero area, ignore
  86       continue;
  87     }
  88
  89     if(lineRect.y + (0.5 * lineRect.height) >= rect.y + (0.5 * rect.height))
  90     {
  91       // Same line
  92       lines.back().push_back(child);
  93     }
  94     else
  95     {
  96       // Start a new line
  97       lineRect = rect;
  98       lines.emplace_back();
  99       lines.back().push_back(child);
 100     }
 101   }
 102
 103   return lines;
 104 }
 105
 106 static bool AcceptObjectCheckRelations(Component* obj)
 107 {
 108   auto relations = obj->GetRelationSet();
 109
 110   for(const auto& it : relations)
 111   {
 112     if(it.mRelationType == RelationType::CONTROLLED_BY)
 113     {
 114       return false;
 115     }
 116   }
 117   return true;
 118 }
 119
 120 static Component* GetScrollableParent(Accessible* obj)
 121 {
 122   while(obj)
 123   {
 124     obj       = obj->GetParent();
 125     auto comp = dynamic_cast<Component*>(obj);
 126     if(comp && comp->IsScrollable())
 127     {
 128       return comp;
 129     }
 130   }
 131   return nullptr;
 132 }
 133
 134 static bool IsObjectItem(Component* obj)
 135 {
 136   if(!obj)
 137   {
 138     return false;
 139   }
 140   auto role = obj->GetRole();
 141   return role == Role::LIST_ITEM || role == Role::MENU_ITEM;
 142 }
 143
 144 static bool IsObjectCollapsed(Component* obj)
 145 {
 146   if(!obj)
 147   {
 148     return false;
 149   }
 150   const auto states = obj->GetStates();
 151   return states[State::EXPANDABLE] && !states[State::EXPANDED];
 152 }
 153
 154 static bool IsObjectZeroSize(Component* obj)
 155 {
 156   if(!obj)
 157   {
 158     return false;
 159   }
 160   auto extents = obj->GetExtents(CoordinateType::WINDOW);
 161   return Dali::EqualsZero(extents.height) || Dali::EqualsZero(extents.width);
 162 }
 163
 164 static bool IsObjectAcceptable(Component* obj)
 165 {
 166   if(!obj)
 167   {
 168     return false;
 169   }
 170
 171   const auto states = obj->GetStates();
 172   if(!states[State::VISIBLE])
 173   {
 174     return false;
 175   }
 176   if(!AcceptObjectCheckRelations(obj))
 177   {
 178     return false;
 179   }
 180   if(!states[State::HIGHLIGHTABLE])
 181   {
 182     return false;
 183   }
 184
 185   if(GetScrollableParent(obj) != nullptr)
 186   {
 187     auto parent = dynamic_cast<Component*>(obj->GetParent());
 188
 189     if(parent)
 190     {
 191       return !IsObjectItem(obj) || !IsObjectCollapsed(parent);
 192     }
 193   }
 194   else
 195   {
 196     if(IsObjectZeroSize(obj))
 197     {
 198       return false;
 199     }
 200     if(!states[State::SHOWING])
 201     {
 202       return false;
 203     }
 204   }
 205   return true;
 206 }
 207
 208 static bool IsObjectAcceptable(Accessible* obj)
 209 {
 210   auto component = dynamic_cast<Component*>(obj);
 211   return IsObjectAcceptable(component);
 212 }
 213
 214 static int32_t GetItemCountOfContainer(Accessible* obj, Dali::Accessibility::Role containerRole, Dali::Accessibility::Role itemRole, bool isDirectChild)
 215 {
 216   int32_t itemCount = 0;
 217   if(obj && (!isDirectChild || obj->GetRole() == containerRole))
 218   {
 219     for(auto i = 0u; i < static_cast<size_t>(obj->GetChildCount()); ++i)
 220     {
 221       auto child = obj->GetChildAtIndex(i);
 222       if(child && child->GetRole() == itemRole)
 223       {
 224         itemCount++;
 225       }
 226     }
 227   }
 228   return itemCount;
 229 }
 230
 231 static int32_t GetItemCountOfFirstDescendantContainer(Accessible* obj, Dali::Accessibility::Role containerRole, Dali::Accessibility::Role itemRole, bool isDirectChild)
 232 {
 233   int32_t itemCount = 0;
 234   itemCount         = GetItemCountOfContainer(obj, containerRole, itemRole, isDirectChild);
 235   if(itemCount > 0 || !obj)
 236   {
 237     return itemCount;
 238   }
 239
 240   for(auto i = 0u; i < static_cast<size_t>(obj->GetChildCount()); ++i)
 241   {
 242     auto child = obj->GetChildAtIndex(i);
 243     itemCount  = GetItemCountOfFirstDescendantContainer(child, containerRole, itemRole, isDirectChild);
 244     if(itemCount > 0)
 245     {
 246       return itemCount;
 247     }
 248   }
 249   return itemCount;
 250 }
 251
 252 static std::string GetComponentInfo(Component* obj)
 253 {
 254   if(!obj)
 255   {
 256     return "nullptr";
 257   }
 258
 259   std::ostringstream object;
 260   auto               extent = obj->GetExtents(CoordinateType::SCREEN);
 261   object << "name: " << obj->GetName() << " extent: (" << extent.x << ", "
 262          << extent.y << "), [" << extent.width << ", " << extent.height << "]";
 263   return object.str();
 264 }
 265
 266 static std::string MakeIndent(unsigned int maxRecursionDepth)
 267 {
 268   return std::string(GET_NAVIGABLE_AT_POINT_MAX_RECURSION_DEPTH - maxRecursionDepth, ' ');
 269 }
 270
 271 static bool IsRoleAcceptableWhenNavigatingNextPrev(Accessible* obj)
 272 {
 273   if(!obj)
 274   {
 275     return false;
 276   }
 277   auto role = obj->GetRole();
 278   return role != Role::POPUP_MENU && role != Role::DIALOG;
 279 }
 280
 281 static Accessible* FindNonDefunctChild(const std::vector<Component*>& children, unsigned int currentIndex, unsigned char forward)
 282 {
 283   unsigned int childrenCount = children.size();
 284   for(; currentIndex < childrenCount; forward ? ++currentIndex : --currentIndex)
 285   {
 286     Accessible* object = children[currentIndex];
 287     if(object && !object->GetStates()[State::DEFUNCT])
 288     {
 289       return object;
 290     }
 291   }
 292   return nullptr;
 293 }
 294
 295 // The auxiliary method for Depth-First Search (DFS) algorithm to find non defunct child directionally
 296 static Accessible* FindNonDefunctChildWithDepthFirstSearch(Accessible* node, const std::vector<Component*>& children, unsigned char forward)
 297 {
 298   if(!node)
 299   {
 300     return nullptr;
 301   }
 302
 303   auto childrenCount = children.size();
 304   if(childrenCount > 0)
 305   {
 306     const bool isShowing = GetScrollableParent(node) == nullptr ? node->GetStates()[State::SHOWING] : true;
 307     if(isShowing)
 308     {
 309       return FindNonDefunctChild(children, forward ? 0 : childrenCount - 1, forward);
 310     }
 311   }
 312   return nullptr;
 313 }
 314
 315 static bool CheckChainEndWithAttribute(Accessible* obj, unsigned char forward)
 316 {
 317   if(!obj)
 318   {
 319     return false;
 320   }
 321
 322   auto attrs = obj->GetAttributes();
 323   for(auto& attr : attrs)
 324   {
 325     if(attr.first == "relation_chain_end")
 326     {
 327       if((attr.second == "prev,end" && forward == 0) || (attr.second == "next,end" && forward == 1) || attr.second == "prev,next,end")
 328       {
 329         return true;
 330       }
 331     }
 332   }
 333   return false;
 334 }
 335
 336 static std::vector<Component*> GetScrollableParents(Accessible* accessible)
 337 {
 338   std::vector<Component*> scrollableParents;
 339
 340   while(accessible)
 341   {
 342     accessible     = accessible->GetParent();
 343     auto component = dynamic_cast<Component*>(accessible);
 344     if(component && component->IsScrollable())
 345     {
 346       scrollableParents.push_back(component);
 347     }
 348   }
 349   return scrollableParents;
 350 }
 351
 352 static std::vector<Component*> GetNonDuplicatedScrollableParents(Accessible* child, Accessible* start)
 353 {
 354   auto scrollableParentsOfChild = GetScrollableParents(child);
 355   auto scrollableParentsOfStart = GetScrollableParents(start);
 356
 357   // find the first different scrollable parent by comparing from top to bottom.
 358   // since it can not be the same after that, there is no need to compare.
 359   while(!scrollableParentsOfChild.empty() && !scrollableParentsOfStart.empty() && scrollableParentsOfChild.back() == scrollableParentsOfStart.back())
 360   {
 361     scrollableParentsOfChild.pop_back();
 362     scrollableParentsOfStart.pop_back();
 363   }
 364
 365   return scrollableParentsOfChild;
 366 }
 367
 368 } // anonymous namespace
 369
 370 BridgeAccessible::BridgeAccessible()
 371 {
 372 }
 373
 374 void BridgeAccessible::RegisterInterfaces()
 375 {
 376   DBus::DBusInterfaceDescription desc{Accessible::GetInterfaceName(AtspiInterface::ACCESSIBLE)};
 377   AddGetPropertyToInterface(desc, "ChildCount", &BridgeAccessible::GetChildCount);
 378   AddGetPropertyToInterface(desc, "Name", &BridgeAccessible::GetName);
 379   AddGetPropertyToInterface(desc, "Description", &BridgeAccessible::GetDescription);
 380   AddGetPropertyToInterface(desc, "Parent", &BridgeAccessible::GetParent);
 381   AddFunctionToInterface(desc, "GetRole", &BridgeAccessible::GetRole);
 382   AddFunctionToInterface(desc, "GetRoleName", &BridgeAccessible::GetRoleName);
 383   AddFunctionToInterface(desc, "GetLocalizedRoleName", &BridgeAccessible::GetLocalizedRoleName);
 384   AddFunctionToInterface(desc, "GetState", &BridgeAccessible::GetStates);
 385   AddFunctionToInterface(desc, "GetAttributes", &BridgeAccessible::GetAttributes);
 386   AddFunctionToInterface(desc, "GetInterfaces", &BridgeAccessible::GetInterfacesAsStrings);
 387   AddFunctionToInterface(desc, "GetChildAtIndex", &BridgeAccessible::GetChildAtIndex);
 388   AddFunctionToInterface(desc, "GetChildren", &BridgeAccessible::GetChildren);
 389   AddFunctionToInterface(desc, "GetIndexInParent", &BridgeAccessible::GetIndexInParent);
 390   AddFunctionToInterface(desc, "GetNavigableAtPoint", &BridgeAccessible::GetNavigableAtPoint);
 391   AddFunctionToInterface(desc, "GetNeighbor", &BridgeAccessible::GetNeighbor);
 392   AddFunctionToInterface(desc, "GetDefaultLabelInfo", &BridgeAccessible::GetDefaultLabelInfo);
 393   AddFunctionToInterface(desc, "DoGesture", &BridgeAccessible::DoGesture);
 394   AddFunctionToInterface(desc, "GetReadingMaterial", &BridgeAccessible::GetReadingMaterial);
 395   AddFunctionToInterface(desc, "GetRelationSet", &BridgeAccessible::GetRelationSet);
 396   mDbusServer.addInterface("/", desc, true);
 397 }
 398
 399 Accessible* BridgeAccessible::FindSelf() const
 400 {
 401   return FindCurrentObject();
 402 }
 403
 404 Component* BridgeAccessible::GetObjectInRelation(Accessible* obj, RelationType relationType)
 405 {
 406   if(!obj)
 407   {
 408     return nullptr;
 409   }
 410
 411   for(auto& relation : obj->GetRelationSet())
 412   {
 413     if(relation.mRelationType == relationType)
 414     {
 415       for(auto& target : relation.mTargets)
 416       {
 417         auto component = dynamic_cast<Component*>(target);
 418         if(component)
 419         {
 420           return component;
 421         }
 422       }
 423     }
 424   }
 425   return nullptr;
 426 }
 427
 428 Component* BridgeAccessible::CalculateNavigableAccessibleAtPoint(Accessible* root, Point point, CoordinateType type, unsigned int maxRecursionDepth)
 429 {
 430   if(!root || maxRecursionDepth == 0)
 431   {
 432     return nullptr;
 433   }
 434
 435   auto rootComponent = dynamic_cast<Component*>(root);
 436   LOG() << "CalculateNavigableAccessibleAtPoint: checking: " << MakeIndent(maxRecursionDepth) << GetComponentInfo(rootComponent);
 437
 438   if(rootComponent && !rootComponent->IsAccessibleContainingPoint(point, type))
 439   {
 440     return nullptr;
 441   }
 442
 443   auto children = root->GetChildren();
 444   for(auto childIt = children.rbegin(); childIt != children.rend(); childIt++)
 445   {
 446     //check recursively all children first
 447     auto result = CalculateNavigableAccessibleAtPoint(*childIt, point, type, maxRecursionDepth - 1);
 448     if(result)
 449     {
 450       return result;
 451     }
 452   }
 453
 454   if(rootComponent)
 455   {
 456     //Found a candidate, all its children are already checked
 457     auto controledBy = GetObjectInRelation(rootComponent, RelationType::CONTROLLED_BY);
 458     if(!controledBy)
 459     {
 460       controledBy = rootComponent;
 461     }
 462
 463     if(controledBy->IsProxy() || IsObjectAcceptable(controledBy))
 464     {
 465       LOG() << "CalculateNavigableAccessibleAtPoint: found:    " << MakeIndent(maxRecursionDepth) << GetComponentInfo(rootComponent);
 466       return controledBy;
 467     }
 468   }
 469   return nullptr;
 470 }
 471
 472 BridgeAccessible::ReadingMaterialType BridgeAccessible::GetReadingMaterial()
 473 {
 474   auto self                     = FindSelf();
 475   auto findObjectByRelationType = [this, &self](RelationType relationType) {
 476     auto relations = self->GetRelationSet();
 477     auto relation  = std::find_if(relations.begin(),
 478                                  relations.end(),
 479                                  [relationType](const Dali::Accessibility::Relation& relation) -> bool {
 480                                    return relation.mRelationType == relationType;
 481                                  });
 482     return relations.end() != relation && !relation->mTargets.empty() ? relation->mTargets.back() : nullptr;
 483   };
 484
 485   auto        labellingObject = findObjectByRelationType(RelationType::LABELLED_BY);
 486   std::string labeledByName   = labellingObject ? labellingObject->GetName() : "";
 487
 488   auto describedByObject = findObjectByRelationType(RelationType::DESCRIBED_BY);
 489
 490   double currentValue     = 0.0;
 491   double minimumIncrement = 0.0;
 492   double maximumValue     = 0.0;
 493   double minimumValue     = 0.0;
 494   auto*  valueInterface   = Value::DownCast(self);
 495   if(valueInterface)
 496   {
 497     currentValue     = valueInterface->GetCurrent();
 498     minimumIncrement = valueInterface->GetMinimumIncrement();
 499     maximumValue     = valueInterface->GetMaximum();
 500     minimumValue     = valueInterface->GetMinimum();
 501   }
 502
 503   int32_t firstSelectedChildIndex = -1;
 504   int32_t selectedChildCount      = 0;
 505   auto*   selfSelectionInterface  = Selection::DownCast(self);
 506   if(selfSelectionInterface)
 507   {
 508     selectedChildCount      = selfSelectionInterface->GetSelectedChildrenCount();
 509     auto firstSelectedChild = selfSelectionInterface->GetSelectedChild(0);
 510     if(firstSelectedChild)
 511     {
 512       firstSelectedChildIndex = firstSelectedChild->GetIndexInParent();
 513     }
 514   }
 515
 516   auto childCount       = static_cast<int32_t>(self->GetChildCount());
 517   bool hasCheckBoxChild = false;
 518   for(auto i = 0u; i < static_cast<size_t>(childCount); ++i)
 519   {
 520     auto child = self->GetChildAtIndex(i);
 521     if(child->GetRole() == Role::CHECK_BOX)
 522     {
 523       hasCheckBoxChild = true;
 524       break;
 525     }
 526   }
 527
 528   auto    atspiRole         = self->GetRole();
 529   int32_t listChildrenCount = 0;
 530   if(atspiRole == Role::DIALOG)
 531   {
 532     listChildrenCount = GetItemCountOfFirstDescendantContainer(self, Role::LIST, Role::LIST_ITEM, true);
 533   }
 534   else if(atspiRole == Role::POPUP_MENU)
 535   {
 536     listChildrenCount = GetItemCountOfFirstDescendantContainer(self, Role::POPUP_MENU, Role::MENU_ITEM, false);
 537   }
 538
 539   auto*       textInterface         = Text::DownCast(self);
 540   std::string nameFromTextInterface = "";
 541   if(textInterface)
 542   {
 543     nameFromTextInterface = textInterface->GetText(0, textInterface->GetCharacterCount());
 544   }
 545
 546   auto attributes        = self->GetAttributes();
 547   auto name              = self->GetName();
 548   auto role              = static_cast<uint32_t>(atspiRole);
 549   auto states            = self->GetStates();
 550   auto localizedRoleName = self->GetLocalizedRoleName();
 551   auto description       = self->GetDescription();
 552   auto indexInParent     = static_cast<int32_t>(self->GetIndexInParent());
 553
 554   auto  parent                   = self->GetParent();
 555   auto  parentRole               = static_cast<uint32_t>(parent ? parent->GetRole() : Role{});
 556   auto  parentChildCount         = parent ? static_cast<int32_t>(parent->GetChildCount()) : 0;
 557   auto  parentStateSet           = parent ? parent->GetStates() : States{};
 558   bool  isSelectedInParent       = false;
 559   auto* parentSelectionInterface = Selection::DownCast(parent);
 560   if(parentSelectionInterface)
 561   {
 562     isSelectedInParent = parentSelectionInterface->IsChildSelected(indexInParent);
 563   }
 564
 565   return {
 566     attributes,
 567     name,
 568     labeledByName,
 569     nameFromTextInterface,
 570     role,
 571     states,
 572     localizedRoleName,
 573     childCount,
 574     currentValue,
 575     minimumIncrement,
 576     maximumValue,
 577     minimumValue,
 578     description,
 579     indexInParent,
 580     isSelectedInParent,
 581     hasCheckBoxChild,
 582     listChildrenCount,
 583     firstSelectedChildIndex,
 584     parent,
 585     parentStateSet,
 586     parentChildCount,
 587     parentRole,
 588     selectedChildCount,
 589     describedByObject};
 590 }
 591
 592 DBus::ValueOrError<bool> BridgeAccessible::DoGesture(Dali::Accessibility::Gesture type, int32_t startPositionX, int32_t startPositionY, int32_t endPositionX, int32_t endPositionY, Dali::Accessibility::GestureState state, uint32_t eventTime)
 593 {
 594   // Please be aware of sending GestureInfo point in the different order with parameters
 595   return FindSelf()->DoGesture(Dali::Accessibility::GestureInfo{type, startPositionX, endPositionX, startPositionY, endPositionY, state, eventTime});
 596 }
 597
 598 DBus::ValueOrError<Accessible*, uint8_t, Accessible*> BridgeAccessible::GetNavigableAtPoint(int32_t x, int32_t y, uint32_t coordinateType)
 599 {
 600   Accessible* deputy     = nullptr;
 601   auto        accessible = FindSelf();
 602   auto        cType      = static_cast<CoordinateType>(coordinateType);
 603
 604   x -= mData->mExtentsOffset.first;
 605   y -= mData->mExtentsOffset.second;
 606
 607   LOG() << "GetNavigableAtPoint: " << x << ", " << y << " type: " << coordinateType;
 608   auto component = CalculateNavigableAccessibleAtPoint(accessible, {x, y}, cType, GET_NAVIGABLE_AT_POINT_MAX_RECURSION_DEPTH);
 609   bool recurse   = false;
 610   if(component)
 611   {
 612     recurse = component->IsProxy();
 613   }
 614   //TODO: add deputy
 615   return {component, recurse, deputy};
 616 }
 617
 618 Accessible* BridgeAccessible::GetCurrentlyHighlighted()
 619 {
 620   //TODO: add currently highlighted object
 621   return nullptr;
 622 }
 623
 624 std::vector<Component*> BridgeAccessible::GetValidChildren(const std::vector<Accessible*>& children, Accessible* start)
 625 {
 626   if(children.empty())
 627   {
 628     return {};
 629   }
 630
 631   std::vector<Component*> vec;
 632
 633   Dali::Rect<> scrollableParentExtents;
 634   auto         nonDuplicatedScrollableParents = GetNonDuplicatedScrollableParents(children.front(), start);
 635   if(!nonDuplicatedScrollableParents.empty())
 636   {
 637     scrollableParentExtents = nonDuplicatedScrollableParents.front()->GetExtents(CoordinateType::WINDOW);
 638   }
 639
 640   for(auto child : children)
 641   {
 642     auto* component = dynamic_cast<Component*>(child);
 643     if(component)
 644     {
 645       if(nonDuplicatedScrollableParents.empty() || scrollableParentExtents.Intersects(component->GetExtents(CoordinateType::WINDOW)))
 646       {
 647         vec.push_back(component);
 648       }
 649     }
 650   }
 651
 652   return vec;
 653 }
 654
 655 void BridgeAccessible::SortChildrenFromTopLeft(std::vector<Dali::Accessibility::Component*>& children)
 656 {
 657   if(children.empty())
 658   {
 659     return;
 660   }
 661
 662   std::vector<Component*> sortedChildren;
 663
 664   std::sort(children.begin(), children.end(), &SortVertically);
 665
 666   for(auto& line : SplitLines(children))
 667   {
 668     std::sort(line.begin(), line.end(), &SortHorizontally);
 669     sortedChildren.insert(sortedChildren.end(), line.begin(), line.end());
 670   }
 671
 672   children = sortedChildren;
 673 }
 674
 675 template<class T>
 676 struct CycleDetection
 677 {
 678   CycleDetection(const T value)
 679   : mKey(value),
 680     mCurrentSearchSize(1),
 681     mCounter(1)
 682   {
 683   }
 684
 685   bool Check(const T value)
 686   {
 687     if(mKey == value)
 688     {
 689       return true;
 690     }
 691
 692     if(--mCounter == 0)
 693     {
 694       mCurrentSearchSize <<= 1;
 695       if(mCurrentSearchSize == 0)
 696       {
 697         return true; // UNDEFINED BEHAVIOR
 698       }
 699       mCounter = mCurrentSearchSize;
 700       mKey     = value;
 701     }
 702     return false;
 703   }
 704
 705   T            mKey;
 706   unsigned int mCurrentSearchSize;
 707   unsigned int mCounter;
 708 };
 709
 710 Accessible* BridgeAccessible::GetNextNonDefunctSibling(Accessible* obj, Accessible* start, unsigned char forward)
 711 {
 712   if(!obj)
 713   {
 714     return nullptr;
 715   }
 716
 717   auto parent = obj->GetParent();
 718   if(!parent)
 719   {
 720     return nullptr;
 721   }
 722   else if(parent->IsProxy())
 723   {
 724     return parent;
 725   }
 726
 727   auto children = GetValidChildren(parent->GetChildren(), start);
 728   SortChildrenFromTopLeft(children);
 729
 730   unsigned int childrenCount = children.size();
 731   if(childrenCount == 0)
 732   {
 733     return nullptr;
 734   }
 735
 736   unsigned int current = 0;
 737   for(; current < childrenCount && children[current] != obj; ++current)
 738   {
 739   }
 740
 741   if(current >= childrenCount)
 742   {
 743     return nullptr;
 744   }
 745
 746   forward ? ++current : --current;
 747   auto ret = FindNonDefunctChild(children, current, forward);
 748   return ret;
 749 }
 750
 751 Accessible* BridgeAccessible::FindNonDefunctSibling(bool& areAllChildrenVisited, Accessible* node, Accessible* start, Accessible* root, unsigned char forward)
 752 {
 753   while(true)
 754   {
 755     Accessible* sibling = GetNextNonDefunctSibling(node, start, forward);
 756     if(sibling)
 757     {
 758       node                  = sibling;
 759       areAllChildrenVisited = false; // Note that this is passed by non-const reference, so it is the caller that can determine whether this search exhausted all children.
 760       break;
 761     }
 762     // walk up...
 763     node = node->GetParent();
 764     if(node == nullptr || node == root)
 765     {
 766       return nullptr;
 767     }
 768
 769     // in backward traversing stop the walk up on parent
 770     if(!forward)
 771     {
 772       break;
 773     }
 774   }
 775
 776   return node;
 777 }
 778
 779 Accessible* BridgeAccessible::CalculateNeighbor(Accessible* root, Accessible* start, unsigned char forward, BridgeAccessible::NeighborSearchMode searchMode)
 780 {
 781   if(start && CheckChainEndWithAttribute(start, forward))
 782   {
 783     return start;
 784   }
 785   if(root && root->GetStates()[State::DEFUNCT])
 786   {
 787     return NULL;
 788   }
 789   if(start && start->GetStates()[State::DEFUNCT])
 790   {
 791     start   = NULL;
 792     forward = 1;
 793   }
 794
 795   if(searchMode == BridgeAccessible::NeighborSearchMode::RECURSE_TO_OUTSIDE)
 796   {
 797     searchMode = BridgeAccessible::NeighborSearchMode::CONTINUE_AFTER_FAILED_RECURSION;
 798   }
 799
 800   Accessible* node = start ? start : root;
 801   if(!node)
 802   {
 803     return nullptr;
 804   }
 805
 806   // initialization of all-children-visited flag for start node - we assume
 807   // that when we begin at start node and we navigate backward, then all children
 808   // are visited, so navigation will ignore start's children and go to
 809   // previous sibling available.
 810   // Regarding condtion (start != root):
 811   // The last object can be found only if areAllChildrenVisited is false.
 812   // The start is same with root, when looking for the last object.
 813   bool areAllChildrenVisited = (start != root) && (searchMode != BridgeAccessible::NeighborSearchMode::RECURSE_FROM_ROOT && !forward);
 814
 815   // true, if starting element should be ignored. this is only used in rare case of
 816   // recursive search failing to find an object.
 817   // consider tree, where element A on bus BUS_A has child B on bus BUS_B. when going "next" from
 818   // element A algorithm has to descend into BUS_B and search element B and its children. this is done
 819   // by returning to our caller object B with special flag set (meaning - continue the search from B on bus BUS_B).
 820   // if next object will be found there (on BUS_B), then search ends. but if not, then our caller will find it out
 821   // and will call us again with object A and flag searchMode set to NEIGHBOR_SEARCH_MODE_CONTINUE_AFTER_FAILED_RECURSING.
 822   // this flag means, that object A was already checked previously and we should skip it and its children.
 823   bool forceNext = (searchMode == BridgeAccessible::NeighborSearchMode::CONTINUE_AFTER_FAILED_RECURSION);
 824
 825   CycleDetection<Accessible*> cycleDetection(node);
 826   while(node)
 827   {
 828     if(node->GetStates()[State::DEFUNCT])
 829     {
 830       return nullptr;
 831     }
 832
 833     // always accept proxy object from different world
 834     if(!forceNext && node->IsProxy())
 835     {
 836       return node;
 837     }
 838
 839     auto children = GetValidChildren(node->GetChildren(), start);
 840     SortChildrenFromTopLeft(children);
 841
 842     // do accept:
 843     // 1. not start node
 844     // 2. parent after all children in backward traversing
 845     // 3. Nodes with roles: ATSPI_ROLE_PAGE_TAB, ATSPI_ROLE_POPUP_MENU and ATSPI_ROLE_DIALOG, only when looking for first or last element.
 846     //    Objects with those roles shouldnt be reachable, when navigating next / prev.
 847     bool areAllChildrenVisitedOrMovingForward = (children.size() == 0 || forward || areAllChildrenVisited);
 848
 849     if(!forceNext && node != start && areAllChildrenVisitedOrMovingForward && IsObjectAcceptable(node))
 850     {
 851       if(start == NULL || IsRoleAcceptableWhenNavigatingNextPrev(node))
 852       {
 853         return node;
 854       }
 855     }
 856
 857     Accessible* nextRelatedInDirection = !forceNext ? GetObjectInRelation(node, forward ? RelationType::FLOWS_TO : RelationType::FLOWS_FROM) : nullptr;
 858     if(nextRelatedInDirection && start && start->GetStates()[State::DEFUNCT])
 859     {
 860       nextRelatedInDirection = NULL;
 861     }
 862
 863     unsigned char wantCycleDetection = 0;
 864     if(nextRelatedInDirection)
 865     {
 866       node               = nextRelatedInDirection;
 867       wantCycleDetection = 1;
 868     }
 869     else
 870     {
 871       auto child = !forceNext && !areAllChildrenVisited ? FindNonDefunctChildWithDepthFirstSearch(node, children, forward) : nullptr;
 872       if(child)
 873       {
 874         wantCycleDetection = 1;
 875       }
 876       else
 877       {
 878         if(!forceNext && node == root)
 879         {
 880           return NULL;
 881         }
 882         areAllChildrenVisited = true;
 883         child                 = FindNonDefunctSibling(areAllChildrenVisited, node, start, root, forward);
 884       }
 885       node = child;
 886     }
 887
 888     forceNext = 0;
 889     if(wantCycleDetection && cycleDetection.Check(node))
 890     {
 891       return NULL;
 892     }
 893   }
 894   return NULL;
 895 }
 896
 897 DBus::ValueOrError<Accessible*, uint8_t> BridgeAccessible::GetNeighbor(std::string rootPath, int32_t direction, int32_t searchMode)
 898 {
 899   auto          start      = FindSelf();
 900   auto          root       = !rootPath.empty() ? Find(StripPrefix(rootPath)) : nullptr;
 901   auto          accessible = CalculateNeighbor(root, start, direction == 1, static_cast<NeighborSearchMode>(searchMode));
 902   unsigned char recurse    = 0;
 903   if(accessible)
 904   {
 905     recurse = accessible->IsProxy();
 906   }
 907   return {accessible, recurse};
 908 }
 909
 910 Accessible* BridgeAccessible::GetParent()
 911 {
 912   // NOTE: currently bridge supports single application root element.
 913   // only element set as application root might return nullptr from GetParent
 914   // if you want more, then you need to change setApplicationRoot to
 915   // add/remove ApplicationRoot and make roots a vector.
 916   auto parent = FindSelf()->GetParent();
 917
 918   return parent;
 919 }
 920
 921 DBus::ValueOrError<std::vector<Accessible*>> BridgeAccessible::GetChildren()
 922 {
 923   return FindSelf()->GetChildren();
 924 }
 925
 926 std::string BridgeAccessible::GetDescription()
 927 {
 928   return FindSelf()->GetDescription();
 929 }
 930
 931 DBus::ValueOrError<uint32_t> BridgeAccessible::GetRole()
 932 {
 933   return static_cast<unsigned int>(FindSelf()->GetRole());
 934 }
 935
 936 DBus::ValueOrError<std::string> BridgeAccessible::GetRoleName()
 937 {
 938   return FindSelf()->GetRoleName();
 939 }
 940
 941 DBus::ValueOrError<std::string> BridgeAccessible::GetLocalizedRoleName()
 942 {
 943   return FindSelf()->GetLocalizedRoleName();
 944 }
 945
 946 DBus::ValueOrError<int32_t> BridgeAccessible::GetIndexInParent()
 947 {
 948   return FindSelf()->GetIndexInParent();
 949 }
 950
 951 DBus::ValueOrError<std::array<uint32_t, 2>> BridgeAccessible::GetStates()
 952 {
 953   return FindSelf()->GetStates().GetRawData();
 954 }
 955
 956 DBus::ValueOrError<std::unordered_map<std::string, std::string>> BridgeAccessible::GetAttributes()
 957 {
 958   std::unordered_map<std::string, std::string> attributes = FindSelf()->GetAttributes();
 959
 960   if(mIsScreenReaderSuppressed)
 961   {
 962     attributes.insert({"suppress-screen-reader", "true"});
 963   }
 964
 965   return attributes;
 966 }
 967
 968 DBus::ValueOrError<std::vector<std::string>> BridgeAccessible::GetInterfacesAsStrings()
 969 {
 970   return FindSelf()->GetInterfacesAsStrings();
 971 }
 972
 973 int BridgeAccessible::GetChildCount()
 974 {
 975   return FindSelf()->GetChildCount();
 976 }
 977
 978 DBus::ValueOrError<Accessible*> BridgeAccessible::GetChildAtIndex(int index)
 979 {
 980   if(index < 0)
 981   {
 982     throw std::domain_error{"negative index (" + std::to_string(index) + ")"};
 983   }
 984   return FindSelf()->GetChildAtIndex(static_cast<size_t>(index));
 985 }
 986
 987 std::string BridgeAccessible::GetName()
 988 {
 989   return FindSelf()->GetName();
 990 }
 991
 992 DBus::ValueOrError<Accessible*, uint32_t, std::unordered_map<std::string, std::string>> BridgeAccessible::GetDefaultLabelInfo()
 993 {
 994   auto* defaultLabel = GetDefaultLabel(FindSelf());
 995   DALI_ASSERT_DEBUG(defaultLabel);
 996
 997   // By default, the text is taken from navigation context root's accessibility properties name and description.
 998   return {defaultLabel, static_cast<uint32_t>(defaultLabel->GetRole()), defaultLabel->GetAttributes()};
 999 }
1000
1001 DBus::ValueOrError<std::vector<BridgeAccessible::Relation>> BridgeAccessible::GetRelationSet()
1002 {
1003   auto                                    relations = FindSelf()->GetRelationSet();
1004   std::vector<BridgeAccessible::Relation> ret;
1005
1006   for(auto& it : relations)
1007   {
1008     ret.emplace_back(Relation{static_cast<uint32_t>(it.mRelationType), it.mTargets});
1009   }
1010
1011   return ret;
1012 }