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