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