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