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

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