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{AtspiDbusInterfaceAccessible};
 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::GetInterfaces);
 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 Component* BridgeAccessible::GetObjectInRelation(Accessible* obj, RelationType relationType)
 427 {
 428   if(!obj)
 429   {
 430     return nullptr;
 431   }
 432
 433   for(auto& relation : obj->GetRelationSet())
 434   {
 435     if(relation.relationType == relationType)
 436     {
 437       for(auto& address : relation.targets)
 438       {
 439         auto component = dynamic_cast<Component*>(Find(address));
 440         if(component)
 441         {
 442           return component;
 443         }
 444       }
 445     }
 446   }
 447   return nullptr;
 448 }
 449
 450 Component* BridgeAccessible::CalculateNavigableAccessibleAtPoint(Accessible* root, Point point, CoordinateType type, unsigned int maxRecursionDepth)
 451 {
 452   if(!root || maxRecursionDepth == 0)
 453   {
 454     return nullptr;
 455   }
 456
 457   auto rootComponent = dynamic_cast<Component*>(root);
 458   LOG() << "CalculateNavigableAccessibleAtPoint: checking: " << MakeIndent(maxRecursionDepth) << GetComponentInfo(rootComponent);
 459
 460   if(rootComponent && !rootComponent->IsAccessibleContainingPoint(point, type))
 461   {
 462     return nullptr;
 463   }
 464
 465   auto children = root->GetChildren();
 466   for(auto childIt = children.rbegin(); childIt != children.rend(); childIt++)
 467   {
 468     //check recursively all children first
 469     auto result = CalculateNavigableAccessibleAtPoint(*childIt, point, type, maxRecursionDepth - 1);
 470     if(result)
 471     {
 472       return result;
 473     }
 474   }
 475
 476   if(rootComponent)
 477   {
 478     //Found a candidate, all its children are already checked
 479     auto controledBy = GetObjectInRelation(rootComponent, RelationType::CONTROLLED_BY);
 480     if(!controledBy)
 481     {
 482       controledBy = rootComponent;
 483     }
 484
 485     if(controledBy->IsProxy() || IsObjectAcceptable(controledBy))
 486     {
 487       LOG() << "CalculateNavigableAccessibleAtPoint: found:    " << MakeIndent(maxRecursionDepth) << GetComponentInfo(rootComponent);
 488       return controledBy;
 489     }
 490   }
 491   return nullptr;
 492 }
 493
 494 BridgeAccessible::ReadingMaterialType BridgeAccessible::GetReadingMaterial()
 495 {
 496   auto self                     = FindSelf();
 497   auto findObjectByRelationType = [this, &self](RelationType relationType) {
 498     auto relations = self->GetRelationSet();
 499     auto relation  = std::find_if(relations.begin(),
 500                                  relations.end(),
 501                                  [relationType](const Dali::Accessibility::Relation& relation) -> bool {
 502                                    return relation.relationType == relationType;
 503                                  });
 504     return relations.end() != relation && !relation->targets.empty() ? Find(relation->targets.back()) : nullptr;
 505   };
 506
 507   auto        labellingObject = findObjectByRelationType(RelationType::LABELLED_BY);
 508   std::string labeledByName   = labellingObject ? labellingObject->GetName() : "";
 509
 510   auto describedByObject = findObjectByRelationType(RelationType::DESCRIBED_BY);
 511
 512   double currentValue     = 0.0;
 513   double minimumIncrement = 0.0;
 514   double maximumValue     = 0.0;
 515   double minimumValue     = 0.0;
 516   auto*  valueInterface   = dynamic_cast<Dali::Accessibility::Value*>(self);
 517   if(valueInterface)
 518   {
 519     currentValue     = valueInterface->GetCurrent();
 520     minimumIncrement = valueInterface->GetMinimumIncrement();
 521     maximumValue     = valueInterface->GetMaximum();
 522     minimumValue     = valueInterface->GetMinimum();
 523   }
 524
 525   int32_t firstSelectedChildIndex = -1;
 526   int32_t selectedChildCount      = 0;
 527   auto*   selfSelectionInterface  = dynamic_cast<Dali::Accessibility::Selection*>(self);
 528   if(selfSelectionInterface)
 529   {
 530     selectedChildCount      = selfSelectionInterface->GetSelectedChildrenCount();
 531     auto firstSelectedChild = selfSelectionInterface->GetSelectedChild(0);
 532     if(firstSelectedChild)
 533     {
 534       firstSelectedChildIndex = firstSelectedChild->GetIndexInParent();
 535     }
 536   }
 537
 538   auto childCount       = static_cast<int32_t>(self->GetChildCount());
 539   bool hasCheckBoxChild = false;
 540   for(auto i = 0u; i < static_cast<size_t>(childCount); ++i)
 541   {
 542     auto child = self->GetChildAtIndex(i);
 543     if(child->GetRole() == Role::CHECK_BOX)
 544     {
 545       hasCheckBoxChild = true;
 546       break;
 547     }
 548   }
 549
 550   auto    atspiRole         = self->GetRole();
 551   int32_t listChildrenCount = 0;
 552   if(atspiRole == Role::DIALOG)
 553   {
 554     listChildrenCount = GetItemCountOfFirstDescendantContainer(self, Role::LIST, Role::LIST_ITEM, true);
 555   }
 556   else if(atspiRole == Role::POPUP_MENU)
 557   {
 558     listChildrenCount = GetItemCountOfFirstDescendantContainer(self, Role::POPUP_MENU, Role::MENU_ITEM, false);
 559   }
 560
 561   auto*       textInterface         = dynamic_cast<Dali::Accessibility::Text*>(self);
 562   std::string nameFromTextInterface = "";
 563   if(textInterface)
 564   {
 565     nameFromTextInterface = textInterface->GetText(0, textInterface->GetCharacterCount());
 566   }
 567
 568   auto attributes        = self->GetAttributes();
 569   auto name              = self->GetName();
 570   auto role              = static_cast<uint32_t>(atspiRole);
 571   auto states            = self->GetStates();
 572   auto localizedRoleName = self->GetLocalizedRoleName();
 573   auto description       = self->GetDescription();
 574   auto indexInParent     = static_cast<int32_t>(self->GetIndexInParent());
 575
 576   auto  parent                   = self->GetParent();
 577   auto  parentRole               = static_cast<uint32_t>(parent ? parent->GetRole() : Role{});
 578   auto  parentChildCount         = parent ? static_cast<int32_t>(parent->GetChildCount()) : 0;
 579   auto  parentStateSet           = parent ? parent->GetStates() : States{};
 580   bool  isSelectedInParent       = false;
 581   auto* parentSelectionInterface = dynamic_cast<Dali::Accessibility::Selection*>(parent);
 582   if(parentSelectionInterface)
 583   {
 584     isSelectedInParent = parentSelectionInterface->IsChildSelected(indexInParent);
 585   }
 586
 587   return {
 588     attributes,
 589     name,
 590     labeledByName,
 591     nameFromTextInterface,
 592     role,
 593     states,
 594     localizedRoleName,
 595     childCount,
 596     currentValue,
 597     minimumIncrement,
 598     maximumValue,
 599     minimumValue,
 600     description,
 601     indexInParent,
 602     isSelectedInParent,
 603     hasCheckBoxChild,
 604     listChildrenCount,
 605     firstSelectedChildIndex,
 606     parent,
 607     parentStateSet,
 608     parentChildCount,
 609     parentRole,
 610     selectedChildCount,
 611     describedByObject};
 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 template<class T>
 694 struct CycleDetection
 695 {
 696   CycleDetection(const T value)
 697   : mKey(value),
 698     mCurrentSearchSize(1),
 699     mCounter(1)
 700   {
 701   }
 702
 703   bool Check(const T value)
 704   {
 705     if(mKey == value)
 706     {
 707       return true;
 708     }
 709
 710     if(--mCounter == 0)
 711     {
 712       mCurrentSearchSize <<= 1;
 713       if(mCurrentSearchSize == 0)
 714       {
 715         return true; // UNDEFINED BEHAVIOR
 716       }
 717       mCounter = mCurrentSearchSize;
 718       mKey     = value;
 719     }
 720     return false;
 721   }
 722
 723   T            mKey;
 724   unsigned int mCurrentSearchSize;
 725   unsigned int mCounter;
 726 };
 727
 728 Accessible* BridgeAccessible::GetNextNonDefunctSibling(Accessible* obj, Accessible* start, unsigned char forward)
 729 {
 730   if(!obj)
 731   {
 732     return nullptr;
 733   }
 734
 735   auto parent = obj->GetParent();
 736   if(!parent)
 737   {
 738     return nullptr;
 739   }
 740
 741   auto children = GetValidChildren(parent->GetChildren(), start);
 742   SortChildrenFromTopLeft(children);
 743
 744   unsigned int childrenCount = children.size();
 745   if(childrenCount == 0)
 746   {
 747     return nullptr;
 748   }
 749
 750   unsigned int current = 0;
 751   for(; current < childrenCount && children[current] != obj; ++current)
 752   {
 753   }
 754
 755   if(current >= childrenCount)
 756   {
 757     return nullptr;
 758   }
 759
 760   forward ? ++current : --current;
 761   auto ret = FindNonDefunctChild(children, current, forward);
 762   return ret;
 763 }
 764
 765 Accessible* BridgeAccessible::FindNonDefunctSibling(bool& areAllChildrenVisited, Accessible* node, Accessible* start, Accessible* root, unsigned char forward)
 766 {
 767   while(true)
 768   {
 769     Accessible* sibling = GetNextNonDefunctSibling(node, start, forward);
 770     if(sibling)
 771     {
 772       node                  = sibling;
 773       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.
 774       break;
 775     }
 776     // walk up...
 777     node = node->GetParent();
 778     if(node == nullptr || node == root)
 779     {
 780       return nullptr;
 781     }
 782
 783     // in backward traversing stop the walk up on parent
 784     if(!forward)
 785     {
 786       break;
 787     }
 788   }
 789
 790   return node;
 791 }
 792
 793 Accessible* BridgeAccessible::CalculateNeighbor(Accessible* root, Accessible* start, unsigned char forward, BridgeAccessible::NeighborSearchMode searchMode)
 794 {
 795   if(start && CheckChainEndWithAttribute(start, forward))
 796   {
 797     return start;
 798   }
 799   if(root && root->GetStates()[State::DEFUNCT])
 800   {
 801     return NULL;
 802   }
 803   if(start && start->GetStates()[State::DEFUNCT])
 804   {
 805     start   = NULL;
 806     forward = 1;
 807   }
 808
 809   if(searchMode == BridgeAccessible::NeighborSearchMode::RECURSE_TO_OUTSIDE)
 810   {
 811     // This only works if we navigate backward, and it is not possible to
 812     // find in embedded process. In this case the deputy should be used */
 813     return GetDeputyOfProxyInParent(start);
 814   }
 815
 816   Accessible* node = start ? start : root;
 817   if(!node)
 818   {
 819     return nullptr;
 820   }
 821
 822   // initialization of all-children-visited flag for start node - we assume
 823   // that when we begin at start node and we navigate backward, then all children
 824   // are visited, so navigation will ignore start's children and go to
 825   // previous sibling available.
 826   // Regarding condtion (start != root):
 827   // The last object can be found only if areAllChildrenVisited is false.
 828   // The start is same with root, when looking for the last object.
 829   bool areAllChildrenVisited = (start != root) && (searchMode != BridgeAccessible::NeighborSearchMode::RECURSE_FROM_ROOT && !forward);
 830
 831   // true, if starting element should be ignored. this is only used in rare case of
 832   // recursive search failing to find an object.
 833   // consider tree, where element A on bus BUS_A has child B on bus BUS_B. when going "next" from
 834   // element A algorithm has to descend into BUS_B and search element B and its children. this is done
 835   // by returning to our caller object B with special flag set (meaning - continue the search from B on bus BUS_B).
 836   // if next object will be found there (on BUS_B), then search ends. but if not, then our caller will find it out
 837   // and will call us again with object A and flag searchMode set to NEIGHBOR_SEARCH_MODE_CONTINUE_AFTER_FAILED_RECURSING.
 838   // this flag means, that object A was already checked previously and we should skip it and its children.
 839   bool forceNext = (searchMode == BridgeAccessible::NeighborSearchMode::CONTINUE_AFTER_FAILED_RECURSION);
 840
 841   CycleDetection<Accessible*> cycleDetection(node);
 842   while(node)
 843   {
 844     if(node->GetStates()[State::DEFUNCT])
 845     {
 846       return nullptr;
 847     }
 848
 849     // always accept proxy object from different world
 850     if(!forceNext && node->IsProxy())
 851     {
 852       return node;
 853     }
 854
 855     auto children = GetValidChildren(node->GetChildren(), start);
 856     SortChildrenFromTopLeft(children);
 857
 858     // do accept:
 859     // 1. not start node
 860     // 2. parent after all children in backward traversing
 861     // 3. Nodes with roles: ATSPI_ROLE_PAGE_TAB, ATSPI_ROLE_POPUP_MENU and ATSPI_ROLE_DIALOG, only when looking for first or last element.
 862     //    Objects with those roles shouldnt be reachable, when navigating next / prev.
 863     bool areAllChildrenVisitedOrMovingForward = (children.size() == 0 || forward || areAllChildrenVisited);
 864
 865     if(!forceNext && node != start && areAllChildrenVisitedOrMovingForward && IsObjectAcceptable(node))
 866     {
 867       if(start == NULL || IsRoleAcceptableWhenNavigatingNextPrev(node))
 868       {
 869         return node;
 870       }
 871     }
 872
 873     Accessible* nextRelatedInDirection = !forceNext ? GetObjectInRelation(node, forward ? RelationType::FLOWS_TO : RelationType::FLOWS_FROM) : nullptr;
 874     // forceNext means that the searchMode is NEIGHBOR_SEARCH_MODE_CONTINUE_AFTER_FAILED_RECURSING
 875     // in this case the node is elm_layout which is parent of proxy object.
 876     // There is an access object working for the proxy object, and the access
 877     // object could have relation information. This relation information should
 878     // be checked first before using the elm_layout as a node.
 879     if(forceNext && forward)
 880     {
 881       auto deputy            = GetDeputyOfProxyInParent(node);
 882       nextRelatedInDirection = GetObjectInRelation(deputy, RelationType::FLOWS_TO);
 883     }
 884
 885     if(nextRelatedInDirection && start && start->GetStates()[State::DEFUNCT])
 886     {
 887       nextRelatedInDirection = NULL;
 888     }
 889
 890     unsigned char wantCycleDetection = 0;
 891     if(nextRelatedInDirection)
 892     {
 893       // Check whether nextRelatedInDirection is deputy object or not
 894       Accessible* parent;
 895       if(!forward)
 896       {
 897         // If the prev object is deputy, then go to inside of its proxy first
 898         if(IsDeputy(nextRelatedInDirection))
 899         {
 900           parent                 = nextRelatedInDirection->GetParent();
 901           nextRelatedInDirection = GetProxyInParent(parent);
 902         }
 903       }
 904       else
 905       {
 906         // If current object is deputy, and it has relation next object,
 907         // then do not use the relation next object, and use proxy first
 908         if(IsDeputy(node))
 909         {
 910           parent                 = node->GetParent();
 911           nextRelatedInDirection = GetProxyInParent(parent);
 912         }
 913       }
 914       node               = nextRelatedInDirection;
 915       wantCycleDetection = 1;
 916     }
 917     else
 918     {
 919       auto child = !forceNext && !areAllChildrenVisited ? FindNonDefunctChildWithDepthFirstSearch(node, children, forward) : nullptr;
 920       if(child)
 921       {
 922         wantCycleDetection = 1;
 923       }
 924       else
 925       {
 926         if(!forceNext && node == root)
 927         {
 928           return NULL;
 929         }
 930         areAllChildrenVisited = true;
 931         child                 = FindNonDefunctSibling(areAllChildrenVisited, node, start, root, forward);
 932       }
 933       node = child;
 934     }
 935
 936     forceNext = 0;
 937     if(wantCycleDetection && cycleDetection.Check(node))
 938     {
 939       return NULL;
 940     }
 941   }
 942   return NULL;
 943 }
 944
 945 DBus::ValueOrError<Accessible*, uint8_t> BridgeAccessible::GetNeighbor(std::string rootPath, int32_t direction, int32_t searchMode)
 946 {
 947   auto start               = FindSelf();
 948   rootPath                 = StripPrefix(rootPath);
 949   auto          root       = !rootPath.empty() ? Find(rootPath) : nullptr;
 950   auto          accessible = CalculateNeighbor(root, start, direction == 1, static_cast<NeighborSearchMode>(searchMode));
 951   unsigned char recurse    = 0;
 952   if(accessible)
 953   {
 954     recurse = accessible->IsProxy();
 955   }
 956   return {accessible, recurse};
 957 }
 958
 959 Accessible* BridgeAccessible::GetParent()
 960 {
 961   // NOTE: currently bridge supports single application root element.
 962   // only element set as application root might return nullptr from GetParent
 963   // if you want more, then you need to change setApplicationRoot to
 964   // add/remove ApplicationRoot and make roots a vector.
 965   auto parent = FindSelf()->GetParent();
 966
 967   return parent;
 968 }
 969
 970 DBus::ValueOrError<std::vector<Accessible*>> BridgeAccessible::GetChildren()
 971 {
 972   return FindSelf()->GetChildren();
 973 }
 974
 975 std::string BridgeAccessible::GetDescription()
 976 {
 977   return FindSelf()->GetDescription();
 978 }
 979
 980 DBus::ValueOrError<uint32_t> BridgeAccessible::GetRole()
 981 {
 982   return static_cast<unsigned int>(FindSelf()->GetRole());
 983 }
 984
 985 DBus::ValueOrError<std::string> BridgeAccessible::GetRoleName()
 986 {
 987   return FindSelf()->GetRoleName();
 988 }
 989
 990 DBus::ValueOrError<std::string> BridgeAccessible::GetLocalizedRoleName()
 991 {
 992   return FindSelf()->GetLocalizedRoleName();
 993 }
 994
 995 DBus::ValueOrError<int32_t> BridgeAccessible::GetIndexInParent()
 996 {
 997   return FindSelf()->GetIndexInParent();
 998 }
 999
1000 DBus::ValueOrError<std::array<uint32_t, 2>> BridgeAccessible::GetStates()
1001 {
1002   return FindSelf()->GetStates().GetRawData();
1003 }
1004
1005 DBus::ValueOrError<std::unordered_map<std::string, std::string>> BridgeAccessible::GetAttributes()
1006 {
1007   std::unordered_map<std::string, std::string> attributes = FindSelf()->GetAttributes();
1008
1009   if(mIsScreenReaderSuppressed)
1010   {
1011     attributes.insert({"suppress-screen-reader", "true"});
1012   }
1013
1014   return attributes;
1015 }
1016
1017 DBus::ValueOrError<std::vector<std::string>> BridgeAccessible::GetInterfaces()
1018 {
1019   return FindSelf()->GetInterfaces();
1020 }
1021
1022 int BridgeAccessible::GetChildCount()
1023 {
1024   return FindSelf()->GetChildCount();
1025 }
1026
1027 DBus::ValueOrError<Accessible*> BridgeAccessible::GetChildAtIndex(int index)
1028 {
1029   if(index < 0)
1030   {
1031     throw std::domain_error{"negative index (" + std::to_string(index) + ")"};
1032   }
1033   return FindSelf()->GetChildAtIndex(static_cast<size_t>(index));
1034 }
1035
1036 std::string BridgeAccessible::GetName()
1037 {
1038   return FindSelf()->GetName();
1039 }
1040
1041 DBus::ValueOrError<Accessible*, uint32_t, std::unordered_map<std::string, std::string>> BridgeAccessible::GetDefaultLabelInfo()
1042 {
1043   auto defaultLabel = GetDefaultLabel();
1044   if(defaultLabel == nullptr)
1045   {
1046     defaultLabel = FindSelf();
1047   }
1048   // By default, the text is taken from navigation context root's accessibility properties name and description.
1049   return {defaultLabel, static_cast<uint32_t>(defaultLabel->GetRole()), defaultLabel->GetAttributes()};
1050 }
1051
1052 DBus::ValueOrError<std::vector<BridgeAccessible::Relation>> BridgeAccessible::GetRelationSet()
1053 {
1054   auto                                    relations = FindSelf()->GetRelationSet();
1055   std::vector<BridgeAccessible::Relation> ret;
1056
1057   for(auto& it : relations)
1058   {
1059     ret.emplace_back(Relation{static_cast<uint32_t>(it.relationType), it.targets});
1060   }
1061
1062   return ret;
1063 }