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