[orca] More work on flat review: Improve efficiency getting showing table cells

[Joanmarie Diggs <joanied src gnome org>]

commit d67067f89cc0f03136c10199cb885a00212ff140
Author: Joanmarie Diggs <jdiggs igalia com>
Date:   Wed Aug 31 16:11:23 2016 -0400

    More work on flat review: Improve efficiency getting showing table cells
    
    Should solve the problem of non-responsiveness when invoking flat review
    in ginormous tables (e.g. Thunderbird folder with 40,000 messages).

 src/orca/flat_review.py                            |   11 +-
 src/orca/script_utilities.py                       |  172 +++++++++-----------
 .../scripts/toolkits/Gecko/script_utilities.py     |  101 ------------
 3 files changed, 83 insertions(+), 201 deletions(-)
---
diff --git a/src/orca/flat_review.py b/src/orca/flat_review.py
index d141e41..6a57745 100644
--- a/src/orca/flat_review.py
+++ b/src/orca/flat_review.py
@@ -991,11 +991,12 @@ class Context:
         except NotImplementedError:
             pass
 
-        showingDescendants = \
-            self.script.utilities.showingDescendants(root)
-        if len(showingDescendants):
-            for child in showingDescendants:
-                zones.extend(self.getShowingZones(child))
+        cells = None
+        if "Table" in pyatspi.listInterfaces(root):
+            cells = self.script.utilities.getVisibleTableCells(root, rootexts)
+        if cells:
+            for cell in cells:
+                zones.extend(self.getShowingZones(cell))
         else:
             for i in range(0, root.childCount):
                 child = root.getChildAtIndex(i)
diff --git a/src/orca/script_utilities.py b/src/orca/script_utilities.py
index 076ffd2..15c0fe6 100644
--- a/src/orca/script_utilities.py
+++ b/src/orca/script_utilities.py
@@ -1653,101 +1653,6 @@ class Utilities:
             activeDescendant or obj
         return self._script.generatorCache[self.REAL_ACTIVE_DESCENDANT][obj]
 
-    def showingDescendants(self, parent):
-        """Given a parent that manages its descendants, return a list of
-        Accessible children that are actually showing.  This algorithm
-        was inspired a little by the srw_elements_from_accessible logic
-        in Gnopernicus, and makes the assumption that the children of
-        an object that manages its descendants are arranged in a row
-        and column format.
-
-        Arguments:
-        - parent: The accessible which manages its descendants
-
-        Returns a list of Accessible descendants which are showing.
-        """
-
-        import sys
-
-        if not parent:
-            return []
-
-        if not parent.getState().contains(pyatspi.STATE_MANAGES_DESCENDANTS) \
-           or parent.childCount <= 50:
-            return []
-
-        try:
-            icomponent = parent.queryComponent()
-        except NotImplementedError:
-            return []
-
-        descendants = []
-
-        parentExtents = icomponent.getExtents(0)
-
-        # [[[TODO: WDW - HACK related to GAIL bug where table column
-        # headers seem to be ignored:
-        # http://bugzilla.gnome.org/show_bug.cgi?id=325809.  The
-        # problem is that this causes getAccessibleAtPoint to return
-        # the cell effectively below the real cell at a given point,
-        # making a mess of everything.  So...we just manually add in
-        # showing headers for now.  The remainder of the logic below
-        # accidentally accounts for this offset, yet it should also
-        # work when bug 325809 is fixed.]]]
-        #
-        try:
-            table = parent.queryTable()
-        except NotImplementedError:
-            table = None
-
-        if table:
-            for i in range(0, table.nColumns):
-                header = table.getColumnHeader(i)
-                if header:
-                    extents = header.queryComponent().getExtents(0)
-                    stateset = header.getState()
-                    if stateset.contains(pyatspi.STATE_SHOWING) \
-                       and (extents.x >= 0) and (extents.y >= 0) \
-                       and (extents.width > 0) and (extents.height > 0) \
-                       and self.containsRegion(extents, parentExtents):
-                        descendants.append(header)
-
-        # This algorithm goes left to right, top to bottom while attempting
-        # to do *some* optimization over queries.  It could definitely be
-        # improved. The gridSize is a minimal chunk to jump around in the
-        # table.
-        #
-        gridSize = 7
-        currentY = parentExtents.y
-        while currentY < (parentExtents.y + parentExtents.height):
-            currentX = parentExtents.x
-            minHeight = sys.maxsize
-            index = -1
-            while currentX < (parentExtents.x + parentExtents.width):
-                child = \
-                    icomponent.getAccessibleAtPoint(currentX, currentY + 1, 0)
-                if child:
-                    index = child.getIndexInParent()
-                    extents = child.queryComponent().getExtents(0)
-                    if extents.x >= 0 and extents.y >= 0:
-                        newX = extents.x + extents.width
-                        minHeight = min(minHeight, extents.height)
-                        if not descendants.count(child):
-                            descendants.append(child)
-                    else:
-                        newX = currentX + gridSize
-                else:
-                    break
-                if newX <= currentX:
-                    currentX += gridSize
-                else:
-                    currentX = newX
-            if minHeight == sys.maxsize:
-                minHeight = gridSize
-            currentY += minHeight
-
-        return descendants
-
     def statusBar(self, obj):
         """Returns the status bar in the window which contains obj.
 
@@ -3464,6 +3369,9 @@ class Utilities:
         return obj.getRole() in roles
 
     def descendantAtPoint(self, root, x, y, coordType=None):
+        if not root:
+            return None
+
         if coordType is None:
             coordType = pyatspi.DESKTOP_COORDS
 
@@ -3473,6 +3381,17 @@ class Utilities:
         elif self._treatAsLeafNode(root) or self._boundsIncludeChildren(root):
             return None
 
+        if "Table" in pyatspi.listInterfaces(root):
+            try:
+                component = root.queryComponent()
+            except:
+                child = None
+            else:
+                child = component.getAccessibleAtPoint(x, y, coordType)
+                if child and child != root:
+                    return self.descendantAtPoint(child, x, y, coordType)
+                return None
+
         for child in root:
             obj = self.descendantAtPoint(child, x, y, coordType)
             if obj:
@@ -3512,6 +3431,69 @@ class Utilities:
 
         return string, start, end
 
+    def visibleRows(self, obj, boundingbox):
+        try:
+            table = obj.queryTable()
+            nRows = table.nRows
+        except:
+            return []
+
+        x, y, width, height = boundingbox
+        cell = self.descendantAtPoint(obj, x, y + 1)
+        row, col = self.coordinatesForCell(cell)
+        startIndex = max(0, row)
+
+        # Just in case the row above is a static header row in a scrollable table.
+        try:
+            extents = cell.queryComponent().getExtents(pyatspi.DESKTOP_COORDS)
+        except:
+            nextIndex = startIndex
+        else:
+            cell = self.descendantAtPoint(obj, x, y + extents.height + 1)
+            row, col = self.coordinatesForCell(cell)
+            nextIndex = max(startIndex, row)
+
+        cell = self.descendantAtPoint(obj, x, y + height - 1)
+        row, col = self.coordinatesForCell(cell)
+        if row == -1:
+            row = nRows
+        endIndex = row
+
+        rows = list(range(nextIndex, endIndex))
+        if startIndex not in rows:
+            rows.insert(0, startIndex)
+
+        return rows
+
+    def getVisibleTableCells(self, obj, extents):
+        try:
+            table = obj.queryTable()
+        except:
+            return []
+
+        rows = self.visibleRows(obj, extents)
+        if not rows:
+            return []
+
+        colStartIndex, colEndIndex = self._getTableRowRange(obj)
+        if colStartIndex == colEndIndex:
+            return []
+
+        cells = []
+        for col in range(colStartIndex, colEndIndex):
+            colHeader = table.getColumnHeader(col)
+            if colHeader:
+                cells.append(colHeader)
+            for row in rows:
+                try:
+                    cell = table.getAccessibleAt(row, col)
+                except:
+                    continue
+                if cell:
+                    cells.append(cell)
+
+        return cells
+
     def _getTableRowRange(self, obj):
         rowCount, columnCount = self.rowAndColumnCount(obj)
         startIndex, endIndex = 0, columnCount
diff --git a/src/orca/scripts/toolkits/Gecko/script_utilities.py 
b/src/orca/scripts/toolkits/Gecko/script_utilities.py
index 11f1db8..ac80920 100644
--- a/src/orca/scripts/toolkits/Gecko/script_utilities.py
+++ b/src/orca/scripts/toolkits/Gecko/script_utilities.py
@@ -103,104 +103,3 @@ class Utilities(web.Utilities):
         msg = "GECKO: Treating %s and %s as same object: %s" % (obj1, obj2, rv)
         debug.println(debug.LEVEL_INFO, msg, True)
         return rv
-
-    def showingDescendants(self, parent):
-        """Given an accessible object, returns a list of accessible children
-        that are actually showing/visible/pursable for flat review. We're
-        overriding the default method here primarily to handle enormous
-        tree tables (such as the Thunderbird message list) which do not
-        manage their descendants.
-
-        Arguments:
-        - parent: The accessible which manages its descendants
-
-        Returns a list of Accessible descendants which are showing.
-        """
-
-        if not parent:
-            return []
-
-        # If this object is not a tree table, if it manages its descendants,
-        # or if it doesn't have very many children, let the default script
-        # handle it.
-        #
-        if parent.getRole() != pyatspi.ROLE_TREE_TABLE \
-           or parent.getState().contains(pyatspi.STATE_MANAGES_DESCENDANTS) \
-           or parent.childCount <= 50:
-            return super().showingDescendants(parent)
-
-        try:
-            table = parent.queryTable()
-        except NotImplementedError:
-            return []
-
-        descendants = []
-
-        # First figure out what columns are visible as there's no point
-        # in examining cells which we know won't be visible.
-        # 
-        visibleColumns = []
-        for i in range(table.nColumns):
-            header = table.getColumnHeader(i)
-            if self.pursueForFlatReview(header):
-                visibleColumns.append(i)
-                descendants.append(header)
-
-        if not len(visibleColumns):
-            return []
-
-        # Now that we know in which columns we can expect to find visible
-        # cells, try to quickly locate a visible row.
-        #
-        startingRow = 0
-
-        # If we have one or more selected items, odds are fairly good
-        # (although not guaranteed) that one of those items happens to
-        # be showing. Failing that, calculate how many rows can fit in
-        # the exposed portion of the tree table and scroll down.
-        #
-        selectedRows = table.getSelectedRows()
-        for row in selectedRows:
-            acc = table.getAccessibleAt(row, visibleColumns[0])
-            if self.pursueForFlatReview(acc):
-                startingRow = row
-                break
-        else:
-            try:
-                tableExtents = parent.queryComponent().getExtents(0)
-                acc = table.getAccessibleAt(0, visibleColumns[0])
-                cellExtents = acc.queryComponent().getExtents(0)
-            except:
-                pass
-            else:
-                rowIncrement = max(1, tableExtents.height / cellExtents.height)
-                for row in range(0, table.nRows, rowIncrement):
-                    acc = table.getAccessibleAt(row, visibleColumns[0])
-                    if acc and self.pursueForFlatReview(acc):
-                        startingRow = row
-                        break
-
-        # Get everything after this point which is visible.
-        #
-        for row in range(startingRow, table.nRows):
-            acc = table.getAccessibleAt(row, visibleColumns[0])
-            if self.pursueForFlatReview(acc):
-                descendants.append(acc)
-                for col in visibleColumns[1:len(visibleColumns)]:
-                    descendants.append(table.getAccessibleAt(row, col))
-            else:
-                break
-
-        # Get everything before this point which is visible.
-        #
-        for row in range(startingRow - 1, -1, -1):
-            acc = table.getAccessibleAt(row, visibleColumns[0])
-            if self.pursueForFlatReview(acc):
-                thisRow = [acc]
-                for col in visibleColumns[1:len(visibleColumns)]:
-                    thisRow.append(table.getAccessibleAt(row, col))
-                descendants[0:0] = thisRow
-            else:
-                break
-
-        return descendants