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