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

   1 /*
   2  * Copyright (c) 2023 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   AddFunctionToInterface(desc, "SetListenPostRender", &BridgeAccessible::SetListenPostRender);
 397   mDbusServer.addInterface("/", desc, true);
 398 }
 399
 400 Accessible* BridgeAccessible::FindSelf() const
 401 {
 402   return FindCurrentObject();
 403 }
 404
 405 Component* BridgeAccessible::GetObjectInRelation(Accessible* obj, RelationType relationType)
 406 {
 407   if(!obj)
 408   {
 409     return nullptr;
 410   }
 411
 412   for(auto& relation : obj->GetRelationSet())
 413   {
 414     if(relation.mRelationType == relationType)
 415     {
 416       for(auto& target : relation.mTargets)
 417       {
 418         auto component = dynamic_cast<Component*>(target);
 419         if(component)
 420         {
 421           return component;
 422         }
 423       }
 424     }
 425   }
 426   return nullptr;
 427 }
 428
 429 Component* BridgeAccessible::CalculateNavigableAccessibleAtPoint(Accessible* root, Point point, CoordinateType type, unsigned int maxRecursionDepth)
 430 {
 431   if(!root || maxRecursionDepth == 0)
 432   {
 433     return nullptr;
 434   }
 435
 436   auto rootComponent = dynamic_cast<Component*>(root);
 437   LOG() << "CalculateNavigableAccessibleAtPoint: checking: " << MakeIndent(maxRecursionDepth) << GetComponentInfo(rootComponent);
 438
 439   if(rootComponent && !rootComponent->IsAccessibleContainingPoint(point, type))
 440   {
 441     return nullptr;
 442   }
 443
 444   auto children = root->GetChildren();
 445   for(auto childIt = children.rbegin(); childIt != children.rend(); childIt++)
 446   {
 447     //check recursively all children first
 448     auto result = CalculateNavigableAccessibleAtPoint(*childIt, point, type, maxRecursionDepth - 1);
 449     if(result)
 450     {
 451       return result;
 452     }
 453   }
 454
 455   if(rootComponent)
 456   {
 457     //Found a candidate, all its children are already checked
 458     auto controledBy = GetObjectInRelation(rootComponent, RelationType::CONTROLLED_BY);
 459     if(!controledBy)
 460     {
 461       controledBy = rootComponent;
 462     }
 463
 464     if(controledBy->IsProxy() || IsObjectAcceptable(controledBy))
 465     {
 466       LOG() << "CalculateNavigableAccessibleAtPoint: found:    " << MakeIndent(maxRecursionDepth) << GetComponentInfo(rootComponent);
 467       return controledBy;
 468     }
 469   }
 470   return nullptr;
 471 }
 472
 473 BridgeAccessible::ReadingMaterialType BridgeAccessible::GetReadingMaterial()
 474 {
 475   auto self                     = FindSelf();
 476   auto findObjectByRelationType = [this, &self](RelationType relationType) {
 477     auto relations = self->GetRelationSet();
 478     auto relation  = std::find_if(relations.begin(),
 479                                  relations.end(),
 480                                  [relationType](const Dali::Accessibility::Relation& relation) -> bool {
 481                                    return relation.mRelationType == relationType;
 482                                  });
 483     return relations.end() != relation && !relation->mTargets.empty() ? relation->mTargets.back() : nullptr;
 484   };
 485
 486   auto        labellingObject = findObjectByRelationType(RelationType::LABELLED_BY);
 487   std::string labeledByName   = labellingObject ? labellingObject->GetName() : "";
 488
 489   auto describedByObject = findObjectByRelationType(RelationType::DESCRIBED_BY);
 490
 491   double currentValue     = 0.0;
 492   double minimumIncrement = 0.0;
 493   double maximumValue     = 0.0;
 494   double minimumValue     = 0.0;
 495   auto*  valueInterface   = Value::DownCast(self);
 496   if(valueInterface)
 497   {
 498     currentValue     = valueInterface->GetCurrent();
 499     minimumIncrement = valueInterface->GetMinimumIncrement();
 500     maximumValue     = valueInterface->GetMaximum();
 501     minimumValue     = valueInterface->GetMinimum();
 502   }
 503
 504   int32_t firstSelectedChildIndex = -1;
 505   int32_t selectedChildCount      = 0;
 506   auto*   selfSelectionInterface  = Selection::DownCast(self);
 507   if(selfSelectionInterface)
 508   {
 509     selectedChildCount      = selfSelectionInterface->GetSelectedChildrenCount();
 510     auto firstSelectedChild = selfSelectionInterface->GetSelectedChild(0);
 511     if(firstSelectedChild)
 512     {
 513       firstSelectedChildIndex = firstSelectedChild->GetIndexInParent();
 514     }
 515   }
 516
 517   auto childCount       = static_cast<int32_t>(self->GetChildCount());
 518   bool hasCheckBoxChild = false;
 519   for(auto i = 0u; i < static_cast<size_t>(childCount); ++i)
 520   {
 521     auto child = self->GetChildAtIndex(i);
 522     if(child->GetRole() == Role::CHECK_BOX)
 523     {
 524       hasCheckBoxChild = true;
 525       break;
 526     }
 527   }
 528
 529   auto    atspiRole         = self->GetRole();
 530   int32_t listChildrenCount = 0;
 531   if(atspiRole == Role::DIALOG)
 532   {
 533     listChildrenCount = GetItemCountOfFirstDescendantContainer(self, Role::LIST, Role::LIST_ITEM, true);
 534   }
 535   else if(atspiRole == Role::POPUP_MENU)
 536   {
 537     listChildrenCount = GetItemCountOfFirstDescendantContainer(self, Role::POPUP_MENU, Role::MENU_ITEM, false);
 538   }
 539
 540   auto*       textInterface         = Text::DownCast(self);
 541   std::string nameFromTextInterface = "";
 542   if(textInterface)
 543   {
 544     nameFromTextInterface = textInterface->GetText(0, textInterface->GetCharacterCount());
 545   }
 546
 547   auto attributes        = self->GetAttributes();
 548   auto name              = self->GetName();
 549   auto role              = static_cast<uint32_t>(atspiRole);
 550   auto states            = self->GetStates();
 551   auto localizedRoleName = self->GetLocalizedRoleName();
 552   auto description       = self->GetDescription();
 553   auto indexInParent     = static_cast<int32_t>(self->GetIndexInParent());
 554
 555   auto  parent                   = self->GetParent();
 556   auto  parentRole               = static_cast<uint32_t>(parent ? parent->GetRole() : Role{});
 557   auto  parentChildCount         = parent ? static_cast<int32_t>(parent->GetChildCount()) : 0;
 558   auto  parentStateSet           = parent ? parent->GetStates() : States{};
 559   bool  isSelectedInParent       = false;
 560   auto* parentSelectionInterface = Selection::DownCast(parent);
 561   if(parentSelectionInterface)
 562   {
 563     isSelectedInParent = parentSelectionInterface->IsChildSelected(indexInParent);
 564   }
 565
 566   return {
 567     attributes,
 568     name,
 569     labeledByName,
 570     nameFromTextInterface,
 571     role,
 572     states,
 573     localizedRoleName,
 574     childCount,
 575     currentValue,
 576     minimumIncrement,
 577     maximumValue,
 578     minimumValue,
 579     description,
 580     indexInParent,
 581     isSelectedInParent,
 582     hasCheckBoxChild,
 583     listChildrenCount,
 584     firstSelectedChildIndex,
 585     parent,
 586     parentStateSet,
 587     parentChildCount,
 588     parentRole,
 589     selectedChildCount,
 590     describedByObject};
 591 }
 592
 593 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)
 594 {
 595   // Please be aware of sending GestureInfo point in the different order with parameters
 596   return FindSelf()->DoGesture(Dali::Accessibility::GestureInfo{type, startPositionX, endPositionX, startPositionY, endPositionY, state, eventTime});
 597 }
 598
 599 DBus::ValueOrError<Accessible*, uint8_t, Accessible*> BridgeAccessible::GetNavigableAtPoint(int32_t x, int32_t y, uint32_t coordinateType)
 600 {
 601   Accessible* deputy     = nullptr;
 602   auto        accessible = FindSelf();
 603   auto        cType      = static_cast<CoordinateType>(coordinateType);
 604
 605   x -= mData->mExtentsOffset.first;
 606   y -= mData->mExtentsOffset.second;
 607
 608   LOG() << "GetNavigableAtPoint: " << x << ", " << y << " type: " << coordinateType;
 609   auto component = CalculateNavigableAccessibleAtPoint(accessible, {x, y}, cType, GET_NAVIGABLE_AT_POINT_MAX_RECURSION_DEPTH);
 610   bool recurse   = false;
 611   if(component)
 612   {
 613     recurse = component->IsProxy();
 614   }
 615   //TODO: add deputy
 616   return {component, recurse, deputy};
 617 }
 618
 619 Accessible* BridgeAccessible::GetCurrentlyHighlighted()
 620 {
 621   //TODO: add currently highlighted object
 622   return nullptr;
 623 }
 624
 625 std::vector<Component*> BridgeAccessible::GetValidChildren(const std::vector<Accessible*>& children, Accessible* start)
 626 {
 627   if(children.empty())
 628   {
 629     return {};
 630   }
 631
 632   std::vector<Component*> vec;
 633
 634   Dali::Rect<> scrollableParentExtents;
 635   auto         nonDuplicatedScrollableParents = GetNonDuplicatedScrollableParents(children.front(), start);
 636   if(!nonDuplicatedScrollableParents.empty())
 637   {
 638     scrollableParentExtents = nonDuplicatedScrollableParents.front()->GetExtents(CoordinateType::WINDOW);
 639   }
 640
 641   for(auto child : children)
 642   {
 643     auto* component = dynamic_cast<Component*>(child);
 644     if(component)
 645     {
 646       if(nonDuplicatedScrollableParents.empty() || scrollableParentExtents.Intersects(component->GetExtents(CoordinateType::WINDOW)))
 647       {
 648         vec.push_back(component);
 649       }
 650     }
 651   }
 652
 653   return vec;
 654 }
 655
 656 void BridgeAccessible::SortChildrenFromTopLeft(std::vector<Dali::Accessibility::Component*>& children)
 657 {
 658   if(children.empty())
 659   {
 660     return;
 661   }
 662
 663   std::vector<Component*> sortedChildren;
 664
 665   std::sort(children.begin(), children.end(), &SortVertically);
 666
 667   for(auto& line : SplitLines(children))
 668   {
 669     std::sort(line.begin(), line.end(), &SortHorizontally);
 670     sortedChildren.insert(sortedChildren.end(), line.begin(), line.end());
 671   }
 672
 673   children = sortedChildren;
 674 }
 675
 676 template<class T>
 677 struct CycleDetection
 678 {
 679   CycleDetection(const T value)
 680   : mKey(value),
 681     mCurrentSearchSize(1),
 682     mCounter(1)
 683   {
 684   }
 685
 686   bool Check(const T value)
 687   {
 688     if(mKey == value)
 689     {
 690       return true;
 691     }
 692
 693     if(--mCounter == 0)
 694     {
 695       mCurrentSearchSize <<= 1;
 696       if(mCurrentSearchSize == 0)
 697       {
 698         return true; // UNDEFINED BEHAVIOR
 699       }
 700       mCounter = mCurrentSearchSize;
 701       mKey     = value;
 702     }
 703     return false;
 704   }
 705
 706   T            mKey;
 707   unsigned int mCurrentSearchSize;
 708   unsigned int mCounter;
 709 };
 710
 711 Accessible* BridgeAccessible::GetNextNonDefunctSibling(Accessible* obj, Accessible* start, unsigned char forward)
 712 {
 713   if(!obj)
 714   {
 715     return nullptr;
 716   }
 717
 718   auto parent = obj->GetParent();
 719   if(!parent)
 720   {
 721     return nullptr;
 722   }
 723   else if(parent->IsProxy())
 724   {
 725     return parent;
 726   }
 727
 728   auto children = GetValidChildren(parent->GetChildren(), start);
 729   SortChildrenFromTopLeft(children);
 730
 731   unsigned int childrenCount = children.size();
 732   if(childrenCount == 0)
 733   {
 734     return nullptr;
 735   }
 736
 737   unsigned int current = 0;
 738   for(; current < childrenCount && children[current] != obj; ++current)
 739   {
 740   }
 741
 742   if(current >= childrenCount)
 743   {
 744     return nullptr;
 745   }
 746
 747   forward ? ++current : --current;
 748   auto ret = FindNonDefunctChild(children, current, forward);
 749   return ret;
 750 }
 751
 752 Accessible* BridgeAccessible::FindNonDefunctSibling(bool& areAllChildrenVisited, Accessible* node, Accessible* start, Accessible* root, unsigned char forward)
 753 {
 754   while(true)
 755   {
 756     Accessible* sibling = GetNextNonDefunctSibling(node, start, forward);
 757     if(sibling)
 758     {
 759       node                  = sibling;
 760       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.
 761       break;
 762     }
 763     // walk up...
 764     node = node->GetParent();
 765     if(node == nullptr || node == root)
 766     {
 767       return nullptr;
 768     }
 769
 770     // in backward traversing stop the walk up on parent
 771     if(!forward)
 772     {
 773       break;
 774     }
 775   }
 776
 777   return node;
 778 }
 779
 780 Accessible* BridgeAccessible::CalculateNeighbor(Accessible* root, Accessible* start, unsigned char forward, BridgeAccessible::NeighborSearchMode searchMode)
 781 {
 782   if(start && CheckChainEndWithAttribute(start, forward))
 783   {
 784     return start;
 785   }
 786   if(root && root->GetStates()[State::DEFUNCT])
 787   {
 788     return NULL;
 789   }
 790   if(start && start->GetStates()[State::DEFUNCT])
 791   {
 792     start   = NULL;
 793     forward = 1;
 794   }
 795
 796   if(searchMode == BridgeAccessible::NeighborSearchMode::RECURSE_TO_OUTSIDE)
 797   {
 798     searchMode = BridgeAccessible::NeighborSearchMode::CONTINUE_AFTER_FAILED_RECURSION;
 799   }
 800
 801   Accessible* node = start ? start : root;
 802   if(!node)
 803   {
 804     return nullptr;
 805   }
 806
 807   // initialization of all-children-visited flag for start node - we assume
 808   // that when we begin at start node and we navigate backward, then all children
 809   // are visited, so navigation will ignore start's children and go to
 810   // previous sibling available.
 811   // Regarding condtion (start != root):
 812   // The last object can be found only if areAllChildrenVisited is false.
 813   // The start is same with root, when looking for the last object.
 814   bool areAllChildrenVisited = (start != root) && (searchMode != BridgeAccessible::NeighborSearchMode::RECURSE_FROM_ROOT && !forward);
 815
 816   // true, if starting element should be ignored. this is only used in rare case of
 817   // recursive search failing to find an object.
 818   // consider tree, where element A on bus BUS_A has child B on bus BUS_B. when going "next" from
 819   // element A algorithm has to descend into BUS_B and search element B and its children. this is done
 820   // by returning to our caller object B with special flag set (meaning - continue the search from B on bus BUS_B).
 821   // if next object will be found there (on BUS_B), then search ends. but if not, then our caller will find it out
 822   // and will call us again with object A and flag searchMode set to NEIGHBOR_SEARCH_MODE_CONTINUE_AFTER_FAILED_RECURSING.
 823   // this flag means, that object A was already checked previously and we should skip it and its children.
 824   bool forceNext = (searchMode == BridgeAccessible::NeighborSearchMode::CONTINUE_AFTER_FAILED_RECURSION);
 825
 826   CycleDetection<Accessible*> cycleDetection(node);
 827   while(node)
 828   {
 829     if(node->GetStates()[State::DEFUNCT])
 830     {
 831       return nullptr;
 832     }
 833
 834     // always accept proxy object from different world
 835     if(!forceNext && node->IsProxy())
 836     {
 837       return node;
 838     }
 839
 840     auto children = GetValidChildren(node->GetChildren(), start);
 841     SortChildrenFromTopLeft(children);
 842
 843     // do accept:
 844     // 1. not start node
 845     // 2. parent after all children in backward traversing
 846     // 3. Nodes with roles: ATSPI_ROLE_PAGE_TAB, ATSPI_ROLE_POPUP_MENU and ATSPI_ROLE_DIALOG, only when looking for first or last element.
 847     //    Objects with those roles shouldnt be reachable, when navigating next / prev.
 848     bool areAllChildrenVisitedOrMovingForward = (children.size() == 0 || forward || areAllChildrenVisited);
 849
 850     if(!forceNext && node != start && areAllChildrenVisitedOrMovingForward && IsObjectAcceptable(node))
 851     {
 852       if(start == NULL || IsRoleAcceptableWhenNavigatingNextPrev(node))
 853       {
 854         return node;
 855       }
 856     }
 857
 858     Accessible* nextRelatedInDirection = !forceNext ? GetObjectInRelation(node, forward ? RelationType::FLOWS_TO : RelationType::FLOWS_FROM) : nullptr;
 859     if(nextRelatedInDirection && start && start->GetStates()[State::DEFUNCT])
 860     {
 861       nextRelatedInDirection = NULL;
 862     }
 863
 864     unsigned char wantCycleDetection = 0;
 865     if(nextRelatedInDirection)
 866     {
 867       node               = nextRelatedInDirection;
 868       wantCycleDetection = 1;
 869     }
 870     else
 871     {
 872       auto child = !forceNext && !areAllChildrenVisited ? FindNonDefunctChildWithDepthFirstSearch(node, children, forward) : nullptr;
 873       if(child)
 874       {
 875         wantCycleDetection = 1;
 876       }
 877       else
 878       {
 879         if(!forceNext && node == root)
 880         {
 881           return NULL;
 882         }
 883         areAllChildrenVisited = true;
 884         child                 = FindNonDefunctSibling(areAllChildrenVisited, node, start, root, forward);
 885       }
 886       node = child;
 887     }
 888
 889     forceNext = 0;
 890     if(wantCycleDetection && cycleDetection.Check(node))
 891     {
 892       return NULL;
 893     }
 894   }
 895   return NULL;
 896 }
 897
 898 DBus::ValueOrError<Accessible*, uint8_t> BridgeAccessible::GetNeighbor(std::string rootPath, int32_t direction, int32_t searchMode)
 899 {
 900   auto          start      = FindSelf();
 901   auto          root       = !rootPath.empty() ? Find(StripPrefix(rootPath)) : nullptr;
 902   auto          accessible = CalculateNeighbor(root, start, direction == 1, static_cast<NeighborSearchMode>(searchMode));
 903   unsigned char recurse    = 0;
 904   if(accessible)
 905   {
 906     recurse = accessible->IsProxy();
 907   }
 908   return {accessible, recurse};
 909 }
 910
 911 Accessible* BridgeAccessible::GetParent()
 912 {
 913   // NOTE: currently bridge supports single application root element.
 914   // only element set as application root might return nullptr from GetParent
 915   // if you want more, then you need to change setApplicationRoot to
 916   // add/remove ApplicationRoot and make roots a vector.
 917   auto parent = FindSelf()->GetParent();
 918
 919   return parent;
 920 }
 921
 922 DBus::ValueOrError<std::vector<Accessible*>> BridgeAccessible::GetChildren()
 923 {
 924   return FindSelf()->GetChildren();
 925 }
 926
 927 std::string BridgeAccessible::GetDescription()
 928 {
 929   return FindSelf()->GetDescription();
 930 }
 931
 932 DBus::ValueOrError<uint32_t> BridgeAccessible::GetRole()
 933 {
 934   return static_cast<unsigned int>(FindSelf()->GetRole());
 935 }
 936
 937 DBus::ValueOrError<std::string> BridgeAccessible::GetRoleName()
 938 {
 939   return FindSelf()->GetRoleName();
 940 }
 941
 942 DBus::ValueOrError<std::string> BridgeAccessible::GetLocalizedRoleName()
 943 {
 944   return FindSelf()->GetLocalizedRoleName();
 945 }
 946
 947 DBus::ValueOrError<int32_t> BridgeAccessible::GetIndexInParent()
 948 {
 949   return FindSelf()->GetIndexInParent();
 950 }
 951
 952 DBus::ValueOrError<std::array<uint32_t, 2>> BridgeAccessible::GetStates()
 953 {
 954   return FindSelf()->GetStates().GetRawData();
 955 }
 956
 957 DBus::ValueOrError<std::unordered_map<std::string, std::string>> BridgeAccessible::GetAttributes()
 958 {
 959   std::unordered_map<std::string, std::string> attributes = FindSelf()->GetAttributes();
 960
 961   if(mIsScreenReaderSuppressed)
 962   {
 963     attributes.insert({"suppress-screen-reader", "true"});
 964   }
 965
 966   return attributes;
 967 }
 968
 969 DBus::ValueOrError<std::vector<std::string>> BridgeAccessible::GetInterfacesAsStrings()
 970 {
 971   return FindSelf()->GetInterfacesAsStrings();
 972 }
 973
 974 int BridgeAccessible::GetChildCount()
 975 {
 976   return FindSelf()->GetChildCount();
 977 }
 978
 979 DBus::ValueOrError<Accessible*> BridgeAccessible::GetChildAtIndex(int index)
 980 {
 981   if(index < 0)
 982   {
 983     throw std::domain_error{"negative index (" + std::to_string(index) + ")"};
 984   }
 985   return FindSelf()->GetChildAtIndex(static_cast<size_t>(index));
 986 }
 987
 988 std::string BridgeAccessible::GetName()
 989 {
 990   return FindSelf()->GetName();
 991 }
 992
 993 DBus::ValueOrError<Accessible*, uint32_t, std::unordered_map<std::string, std::string>> BridgeAccessible::GetDefaultLabelInfo()
 994 {
 995   auto* defaultLabel = GetDefaultLabel(FindSelf());
 996   DALI_ASSERT_DEBUG(defaultLabel);
 997
 998   // By default, the text is taken from navigation context root's accessibility properties name and description.
 999   return {defaultLabel, static_cast<uint32_t>(defaultLabel->GetRole()), defaultLabel->GetAttributes()};
1000 }
1001
1002 DBus::ValueOrError<std::vector<BridgeAccessible::Relation>> BridgeAccessible::GetRelationSet()
1003 {
1004   auto                                    relations = FindSelf()->GetRelationSet();
1005   std::vector<BridgeAccessible::Relation> ret;
1006
1007   for(auto& it : relations)
1008   {
1009     ret.emplace_back(Relation{static_cast<uint32_t>(it.mRelationType), it.mTargets});
1010   }
1011
1012   return ret;
1013 }
1014
1015 DBus::ValueOrError<void> BridgeAccessible::SetListenPostRender(bool enabled)
1016 {
1017   FindSelf()->SetListenPostRender(enabled);
1018   return {};
1019 }