[orca] More structural navigation clean-up



commit b69b844bc84b7b2c10398ceee6f8da13be33b775
Author: Joanmarie Diggs <jdiggs igalia com>
Date:   Wed Jun 10 12:52:25 2015 -0400

    More structural navigation clean-up
    
    * Simplify structural navigation's object-finding methods
    * Cache results for performance
    * Move utility methods that are not limited to structural navigation
      where they can be used elsewhere in the scripts

 src/orca/braille_generator.py                      |    7 +-
 src/orca/formatting.py                             |    7 +-
 src/orca/script.py                                 |    6 +-
 src/orca/script_utilities.py                       |  127 ++++-
 src/orca/scripts/apps/soffice/script_utilities.py  |   14 +
 .../scripts/apps/soffice/structural_navigation.py  |   45 +-
 src/orca/scripts/default.py                        |    5 +
 src/orca/scripts/toolkits/Gecko/Makefile.am        |    1 -
 src/orca/scripts/toolkits/Gecko/script.py          |   75 +--
 .../toolkits/Gecko/structural_navigation.py        |  121 ----
 src/orca/scripts/toolkits/WebKitGtk/script.py      |    6 -
 src/orca/speech_generator.py                       |   10 +-
 src/orca/structural_navigation.py                  |  739 ++++----------------
 test/html/lists.html                               |   41 +-
 test/keystrokes/firefox/aria_landmarks.py          |   49 +-
 15 files changed, 384 insertions(+), 869 deletions(-)
---
diff --git a/src/orca/braille_generator.py b/src/orca/braille_generator.py
index 23fceb2..86e6361 100644
--- a/src/orca/braille_generator.py
+++ b/src/orca/braille_generator.py
@@ -32,6 +32,7 @@ from . import braille
 from . import debug
 from . import generator
 from . import messages
+from . import object_properties
 from . import orca_state
 from . import settings
 from . import settings_manager
@@ -146,7 +147,11 @@ class BrailleGenerator(generator.Generator):
         if verbosityLevel == settings.VERBOSITY_LEVEL_BRIEF:
             doNotPresent.extend([pyatspi.ROLE_ICON, pyatspi.ROLE_CANVAS])
 
-        if verbosityLevel == settings.VERBOSITY_LEVEL_VERBOSE \
+        if role == pyatspi.ROLE_HEADING:
+            level = self._script.utilities.headingLevel(obj)
+            result.append(object_properties.ROLE_HEADING_LEVEL_BRAILLE % level)
+
+        elif verbosityLevel == settings.VERBOSITY_LEVEL_VERBOSE \
            and not args.get('readingRow', False) and role not in doNotPresent:
             result.append(self.getLocalizedRoleName(obj, role))
         return result
diff --git a/src/orca/formatting.py b/src/orca/formatting.py
index 498b11b..49c04b3 100644
--- a/src/orca/formatting.py
+++ b/src/orca/formatting.py
@@ -180,7 +180,8 @@ formatting = {
             'unfocused': 'labelOrName + allTextSelection + roleName + unfocusedDialogCount + availability'
             },
         pyatspi.ROLE_HEADING: {
-            'unfocused': 'displayedText + roleName + expandableState + availability + ' + MNEMONIC,
+            'focused': 'displayedText + roleName + expandableState',
+            'unfocused': 'displayedText + roleName + expandableState',
             'basicWhereAmI': 'label + readOnly + textRole + textContent + anyTextSelection + ' + MNEMONIC,
             'detailedWhereAmI': 'label + readOnly + textRole + textContentWithAttributes + anyTextSelection 
+ ' + MNEMONIC + ' + ' + TUTORIAL
             },
@@ -662,8 +663,8 @@ if settings.useExperimentalSpeechProsody:
     formatting['speech'][pyatspi.ROLE_COMBO_BOX]['unfocused'] = 'label + name + roleName + pause + 
positionInList + ' + MNEMONIC + ' + accelerator'
     formatting['speech'][pyatspi.ROLE_COMBO_BOX]['basicWhereAmI'] = \
         'label + roleName + pause + name + positionInList + ' + MNEMONIC + ' + accelerator'
-    formatting['speech'][pyatspi.ROLE_HEADING]['unfocused'] = \
-        'displayedText + roleName + expandableState + availability + ' + MNEMONIC
+    formatting['speech'][pyatspi.ROLE_HEADING]['focused'] = 'displayedText + roleName + expandableState'
+    formatting['speech'][pyatspi.ROLE_HEADING]['unfocused'] = 'displayedText + roleName + expandableState'
     formatting['speech'][pyatspi.ROLE_HEADING]['basicWhereAmI'] = \
         'label + readOnly + textRole + pause + textContent + anyTextSelection + ' + MNEMONIC
     formatting['speech'][pyatspi.ROLE_HEADING]['detailedWhereAmI'] = \
diff --git a/src/orca/script.py b/src/orca/script.py
index a228382..05ba265 100644
--- a/src/orca/script.py
+++ b/src/orca/script.py
@@ -247,10 +247,10 @@ class Script:
         return []
 
     def getStructuralNavigation(self):
-        """Returns the 'structural navigation' class for this script.
-        """
+        """Returns the 'structural navigation' class for this script."""
         types = self.getEnabledStructuralNavigationTypes()
-        return structural_navigation.StructuralNavigation(self, types)
+        enable = _settingsManager.getSetting('structuralNavigationEnabled')
+        return structural_navigation.StructuralNavigation(self, types, enable)
 
     def getLiveRegionManager(self):
         """Returns the live region support for this script."""
diff --git a/src/orca/script_utilities.py b/src/orca/script_utilities.py
index bf47c4e..69c11be 100644
--- a/src/orca/script_utilities.py
+++ b/src/orca/script_utilities.py
@@ -41,6 +41,7 @@ from . import input_event
 from . import mathsymbols
 from . import messages
 from . import mouse_review
+from . import orca
 from . import orca_state
 from . import object_properties
 from . import pronunciation_dict
@@ -446,11 +447,25 @@ class Utilities:
         self._script.generatorCache[self.DISPLAYED_TEXT][obj] = displayedText
         return self._script.generatorCache[self.DISPLAYED_TEXT][obj]
 
-    def documentFrame(self):
+    def documentFrame(self, obj=None):
         """Returns the document frame which is displaying the content.
         Note that this is intended primarily for web content."""
 
-        return None
+        if not obj:
+            obj, offset = self.getCaretContext()
+        docRoles = [pyatspi.ROLE_DOCUMENT_EMAIL,
+                    pyatspi.ROLE_DOCUMENT_FRAME,
+                    pyatspi.ROLE_DOCUMENT_PRESENTATION,
+                    pyatspi.ROLE_DOCUMENT_SPREADSHEET,
+                    pyatspi.ROLE_DOCUMENT_TEXT,
+                    pyatspi.ROLE_DOCUMENT_WEB]
+        stopRoles = [pyatspi.ROLE_FRAME, pyatspi.ROLE_SCROLL_PANE]
+        document = self.ancestorWithRole(obj, docRoles, stopRoles)
+        if not document and orca_state.locusOfFocus:
+            if orca_state.locusOfFocus.getRole() in docRoles:
+                return orca_state.locusOfFocus
+
+        return document
 
     def documentFrameURI(self):
         """Returns the URI of the document frame that is active."""
@@ -1322,6 +1337,26 @@ class Utilities:
         return abs(center1 - center2) <= delta
 
     @staticmethod
+    def pathComparison(path1, path2, treatDescendantAsSame=False):
+        """Compares the two paths and returns -1, 0, or 1 to indicate if path1
+        is before, the same, or after path2."""
+
+        if path1 == path2:
+            return 0
+
+        for x in range(min(len(path1), len(path2))):
+            if path1[x] < path2[x]:
+                return -1
+            if path1[x] > path2[x]:
+                return 1
+
+        if treatDescendantAsSame:
+            return 0
+
+        rv = len(path1) - len(path2)
+        return min(max(rv, -1), 1)
+
+    @staticmethod
     def spatialComparison(obj1, obj2):
         """Compares the physical locations of obj1 and obj2 and returns -1,
         0, or 1 to indicate if obj1 physically is before, is in the same
@@ -1743,6 +1778,10 @@ class Utilities:
 
         return obj, offset
 
+    def setCaretPosition(self, obj, offset):
+        orca.setLocusOfFocus(None, obj, False)
+        self.setCaretOffset(obj, offset)
+
     def setCaretOffset(self, obj, offset):
         """Set the caret offset on a given accessible. Similar to
         Accessible.setCaretOffset()
@@ -2486,6 +2525,48 @@ class Utilities:
 
         return False
 
+    def columnHeadersForCell(self, obj):
+        if not (obj and obj.getRole() == pyatspi.ROLE_TABLE_CELL):
+            return []
+
+        isTable = lambda x: x and 'Table' in pyatspi.listInterfaces(x)
+        parent = pyatspi.findAncestor(obj, isTable)
+        try:
+            table = parent.queryTable()
+        except:
+            return []
+
+        index = self.cellIndex(obj)
+        row, col = table.getRowAtIndex(index), table.getColumnAtIndex(index)
+        colspan = table.getColumnExtentAt(row, col)
+
+        headers = []
+        for c in range(col, col+colspan):
+            headers.append(table.getColumnHeader(c))
+
+        return headers
+
+    def rowHeadersForCell(self, obj):
+        if not (obj and obj.getRole() == pyatspi.ROLE_TABLE_CELL):
+            return []
+
+        isTable = lambda x: x and 'Table' in pyatspi.listInterfaces(x)
+        parent = pyatspi.findAncestor(obj, isTable)
+        try:
+            table = parent.queryTable()
+        except:
+            return []
+
+        index = self.cellIndex(obj)
+        row, col = table.getRowAtIndex(index), table.getColumnAtIndex(index)
+        rowspan = table.getRowExtentAt(row, col)
+
+        headers = []
+        for r in range(row, row+rowspan):
+            headers.append(table.getRowHeader(r))
+
+        return headers
+
     def columnHeaderForCell(self, obj):
         if not (obj and obj.getRole() == pyatspi.ROLE_TABLE_CELL):
             return None
@@ -2517,6 +2598,23 @@ class Utilities:
         return table.getRowHeader(rowIndex)
 
     def coordinatesForCell(self, obj):
+        roles = [pyatspi.ROLE_TABLE_CELL,
+                 pyatspi.ROLE_COLUMN_HEADER,
+                 pyatspi.ROLE_ROW_HEADER]
+        if not (obj and obj.getRole() in roles):
+            return -1, -1
+
+        isTable = lambda x: x and 'Table' in pyatspi.listInterfaces(x)
+        parent = pyatspi.findAncestor(obj, isTable)
+        try:
+            table = parent.queryTable()
+        except:
+            return -1, -1
+
+        index = self.cellIndex(obj)
+        return table.getRowAtIndex(index), table.getColumnAtIndex(index)
+
+    def rowAndColumnSpan(self, obj):
         if not (obj and obj.getRole() == pyatspi.ROLE_TABLE_CELL):
             return -1, -1
 
@@ -2528,7 +2626,30 @@ class Utilities:
             return -1, -1
 
         index = self.cellIndex(obj)
-        return table.getRowAtIndex(index), table.getColumnHeader(index)
+        row, col = table.getRowAtIndex(index), table.getColumnAtIndex(index)
+        return table.getRowExtentAt(row, col), table.getColumnExtentAt(row, col)
+
+    def cellForCoordinates(self, obj, row, column):
+        try:
+            table = obj.queryTable()
+        except:
+            return None
+
+        return table.getAccessibleAt(row, column)
+
+    def isNonUniformTable(self, obj):
+        try:
+            table = obj.queryTable()
+        except:
+            return False
+
+        for r in range(table.nRows):
+            for c in range(table.nColumns):
+                if table.getRowExtentAt(r, c) > 1 \
+                   or table.getColumnExtentAt(r, c) > 1:
+                    return True
+
+        return False
 
     def isZombie(self, obj):
         try:
diff --git a/src/orca/scripts/apps/soffice/script_utilities.py 
b/src/orca/scripts/apps/soffice/script_utilities.py
index d07090b..6da6c47 100644
--- a/src/orca/scripts/apps/soffice/script_utilities.py
+++ b/src/orca/scripts/apps/soffice/script_utilities.py
@@ -254,6 +254,20 @@ class Utilities(script_utilities.Utilities):
 
         return [startIndex, endIndex]
 
+    def rowHeadersForCell(self, obj):
+        rowHeader, colHeader = self.getDynamicHeadersForCell(obj)
+        if rowHeader:
+            return [rowHeader]
+
+        return super().rowHeadersForCell(obj)
+
+    def columnHeadersForCell(self, obj):
+        rowHeader, colHeader = self.getDynamicHeadersForCell(obj)
+        if colHeader:
+            return [colHeader]
+
+        return super().columnHeadersForCell(obj)
+
     def getDynamicHeadersForCell(self, obj, onlyIfNew=False):
         if not (self._script.dynamicRowHeaders or self._script.dynamicColumnHeaders):
             return None, None
diff --git a/src/orca/scripts/apps/soffice/structural_navigation.py 
b/src/orca/scripts/apps/soffice/structural_navigation.py
index 8e9a697..e50ef2f 100644
--- a/src/orca/scripts/apps/soffice/structural_navigation.py
+++ b/src/orca/scripts/apps/soffice/structural_navigation.py
@@ -47,39 +47,6 @@ class StructuralNavigation(structural_navigation.StructuralNavigation):
                                                             enabledTypes,
                                                             enabled)
 
-    def _isHeader(self, obj):
-        """Returns True if the table cell is a header.
-
-        Arguments:
-        - obj: the accessible table cell to examine.
-        """
-
-        if not obj:
-            return False
-
-        if obj.getRole() in [pyatspi.ROLE_TABLE_COLUMN_HEADER,
-                             pyatspi.ROLE_TABLE_ROW_HEADER]:
-            return True
-
-        # Check for dynamic row and column headers.
-        #
-        try:
-            table = obj.parent.queryTable()
-        except:
-            return False
-
-        parent = hash(obj.parent)
-
-        # Make sure we're in the correct table first.
-        #
-        if not (parent in self._script.dynamicRowHeaders or
-                parent in self._script.dynamicColumnHeaders):
-            return False
-
-        [row, col] = self.getCellCoordinates(obj)
-        return (row == self._script.dynamicColumnHeaders.get(parent) \
-                or col == self._script.dynamicRowHeaders.get(parent))
-
     def _tableCellPresentation(self, cell, arg):
         """Presents the table cell or indicates that one was not found.
         Overridden here to avoid the double-speaking of the dynamic
@@ -118,6 +85,16 @@ class StructuralNavigation(structural_navigation.StructuralNavigation):
             self._script.presentMessage(messages.TABLE_CELL_COORDINATES \
                                        % {"row" : row + 1, "column" : col + 1})
 
-        spanString = self._getCellSpanInfo(cell)
+        rowspan, colspan = self._script.utilities.rowAndColumnSpan(cell)
+        spanString = messages.cellSpan(rowspan, colspan)
         if spanString and settings.speakCellSpan:
             self._script.presentMessage(spanString)
+
+    def _getCaretPosition(self, obj):
+        try:
+            text = obj.queryText()
+        except:
+            if obj and obj.childCount:
+                return self._getCaretPosition(obj[0])
+
+        return obj, 0
diff --git a/src/orca/scripts/default.py b/src/orca/scripts/default.py
index c060fd6..42578db 100644
--- a/src/orca/scripts/default.py
+++ b/src/orca/scripts/default.py
@@ -3623,6 +3623,11 @@ class Script(script.Script):
         self._lastWord = word
         speech.speak(word, voice)
 
+    def presentObject(self, obj, offset=0):
+        self.updateBraille(obj)
+        utterances = self.speechGenerator.generateSpeech(obj)
+        speech.speak(utterances, voice)
+
     def stopSpeechOnActiveDescendantChanged(self, event):
         """Whether or not speech should be stopped prior to setting the
         locusOfFocus in onActiveDescendantChanged.
diff --git a/src/orca/scripts/toolkits/Gecko/Makefile.am b/src/orca/scripts/toolkits/Gecko/Makefile.am
index ddcdb9c..0d76502 100644
--- a/src/orca/scripts/toolkits/Gecko/Makefile.am
+++ b/src/orca/scripts/toolkits/Gecko/Makefile.am
@@ -5,7 +5,6 @@ orca_python_PYTHON = \
        script.py \
        script_utilities.py \
        speech_generator.py \
-       structural_navigation.py \
        tutorial_generator.py
 
 orca_pythondir=$(pkgpythondir)/scripts/toolkits/Gecko
diff --git a/src/orca/scripts/toolkits/Gecko/script.py b/src/orca/scripts/toolkits/Gecko/script.py
index 8520ff2..152ba89 100644
--- a/src/orca/scripts/toolkits/Gecko/script.py
+++ b/src/orca/scripts/toolkits/Gecko/script.py
@@ -59,11 +59,11 @@ import orca.settings as settings
 import orca.settings_manager as settings_manager
 import orca.speech as speech
 import orca.speechserver as speechserver
+import orca.structural_navigation as structural_navigation
 
 from .braille_generator import BrailleGenerator
 from .speech_generator import SpeechGenerator
 from .bookmarks import GeckoBookmarks
-from .structural_navigation import GeckoStructuralNavigation
 from .script_utilities import Utilities
 from .tutorial_generator import TutorialGenerator
 
@@ -244,43 +244,34 @@ class Script(default.Script):
         enabled in this script.
         """
 
-        enabledTypes = [GeckoStructuralNavigation.BLOCKQUOTE,
-                        GeckoStructuralNavigation.BUTTON,
-                        GeckoStructuralNavigation.CHECK_BOX,
-                        GeckoStructuralNavigation.CHUNK,
-                        GeckoStructuralNavigation.CLICKABLE,
-                        GeckoStructuralNavigation.COMBO_BOX,
-                        GeckoStructuralNavigation.ENTRY,
-                        GeckoStructuralNavigation.FORM_FIELD,
-                        GeckoStructuralNavigation.HEADING,
-                        GeckoStructuralNavigation.IMAGE,
-                        GeckoStructuralNavigation.LANDMARK,
-                        GeckoStructuralNavigation.LINK,
-                        GeckoStructuralNavigation.LIST,
-                        GeckoStructuralNavigation.LIST_ITEM,
-                        GeckoStructuralNavigation.LIVE_REGION,
-                        GeckoStructuralNavigation.PARAGRAPH,
-                        GeckoStructuralNavigation.RADIO_BUTTON,
-                        GeckoStructuralNavigation.SEPARATOR,
-                        GeckoStructuralNavigation.TABLE,
-                        GeckoStructuralNavigation.TABLE_CELL,
-                        GeckoStructuralNavigation.UNVISITED_LINK,
-                        GeckoStructuralNavigation.VISITED_LINK]
-
-        return enabledTypes
+        return [structural_navigation.StructuralNavigation.BLOCKQUOTE,
+                structural_navigation.StructuralNavigation.BUTTON,
+                structural_navigation.StructuralNavigation.CHECK_BOX,
+                structural_navigation.StructuralNavigation.CHUNK,
+                structural_navigation.StructuralNavigation.CLICKABLE,
+                structural_navigation.StructuralNavigation.COMBO_BOX,
+                structural_navigation.StructuralNavigation.ENTRY,
+                structural_navigation.StructuralNavigation.FORM_FIELD,
+                structural_navigation.StructuralNavigation.HEADING,
+                structural_navigation.StructuralNavigation.IMAGE,
+                structural_navigation.StructuralNavigation.LANDMARK,
+                structural_navigation.StructuralNavigation.LINK,
+                structural_navigation.StructuralNavigation.LIST,
+                structural_navigation.StructuralNavigation.LIST_ITEM,
+                structural_navigation.StructuralNavigation.LIVE_REGION,
+                structural_navigation.StructuralNavigation.PARAGRAPH,
+                structural_navigation.StructuralNavigation.RADIO_BUTTON,
+                structural_navigation.StructuralNavigation.SEPARATOR,
+                structural_navigation.StructuralNavigation.TABLE,
+                structural_navigation.StructuralNavigation.TABLE_CELL,
+                structural_navigation.StructuralNavigation.UNVISITED_LINK,
+                structural_navigation.StructuralNavigation.VISITED_LINK]
 
     def getLiveRegionManager(self):
         """Returns the live region support for this script."""
 
         return liveregions.LiveRegionManager(self)
 
-    def getStructuralNavigation(self):
-        """Returns the 'structural navigation' class for this script.
-        """
-        types = self.getEnabledStructuralNavigationTypes()
-        enable = _settingsManager.getSetting('structuralNavigationEnabled')
-        return GeckoStructuralNavigation(self, types, enable)
-
     def getCaretNavigation(self):
         """Returns the caret navigation support for this script."""
 
@@ -1441,19 +1432,6 @@ class Script(default.Script):
 
         return True
 
-    def presentLine(self, obj, offset):
-        """Presents the current line in speech and in braille.
-
-        Arguments:
-        - obj: the Accessible at the caret
-        - offset: the offset within obj
-        """
-
-        contents = self.utilities.getLineContentsAtOffset(obj, offset)
-        if not isinstance(orca_state.lastInputEvent, input_event.BrailleEvent):
-            self.speakContents(self.utilities.getLineContentsAtOffset(obj, offset))
-        self.updateBraille(obj)
-
     def updateBraille(self, obj, extraRegion=None):
         """Updates the braille display to show the given object."""
 
@@ -1556,13 +1534,18 @@ class Script(default.Script):
     def sayLine(self, obj):
         """Speaks the line at the current caret position."""
 
-        if not self._lastCommandWasCaretNav:
+        if not (self._lastCommandWasCaretNav or self._lastCommandWasStructNav):
             super().sayLine(obj)
             return
 
         obj, offset = self.utilities.getCaretContext(documentFrame=None)
         self.speakContents(self.utilities.getLineContentsAtOffset(obj, offset))
 
+    def presentObject(self, obj, offset=0):
+        contents = self.utilities.getObjectContentsAtOffset(obj, offset)
+        self.displayContents(contents)
+        self.speakContents(contents)
+
     def panBrailleLeft(self, inputEvent=None, panAmount=0):
         """In document content, we want to use the panning keys to browse the
         entire document.
diff --git a/src/orca/scripts/toolkits/WebKitGtk/script.py b/src/orca/scripts/toolkits/WebKitGtk/script.py
index 795f9cd..1afeaa8 100644
--- a/src/orca/scripts/toolkits/WebKitGtk/script.py
+++ b/src/orca/scripts/toolkits/WebKitGtk/script.py
@@ -138,12 +138,6 @@ class Script(default.Script):
 
         return SpeechGenerator(self)
 
-    def getStructuralNavigation(self):
-        """Returns the 'structural navigation' class for this script."""
-
-        types = self.getEnabledStructuralNavigationTypes()
-        return structural_navigation.StructuralNavigation(self, types, True)
-
     def getEnabledStructuralNavigationTypes(self):
         """Returns a list of the structural navigation object types
         enabled in this script."""
diff --git a/src/orca/speech_generator.py b/src/orca/speech_generator.py
index 3f22386..184914a 100644
--- a/src/orca/speech_generator.py
+++ b/src/orca/speech_generator.py
@@ -355,7 +355,15 @@ class SpeechGenerator(generator.Generator):
                 == settings.VERBOSITY_LEVEL_BRIEF:
             doNotPresent.extend([pyatspi.ROLE_ICON, pyatspi.ROLE_CANVAS])
 
-        if role not in doNotPresent:
+        if role == pyatspi.ROLE_HEADING:
+            level = self._script.utilities.headingLevel(obj)
+            if level:
+                result.append(object_properties.ROLE_HEADING_LEVEL_SPEECH % {
+                    'role': self.getLocalizedRoleName(obj, role),
+                    'level': level})
+                result.extend(acss)
+
+        if role not in doNotPresent and not result:
             result.append(self.getLocalizedRoleName(obj, role))
             result.extend(acss)
         return result
diff --git a/src/orca/structural_navigation.py b/src/orca/structural_navigation.py
index 91426c3..2cff96f 100644
--- a/src/orca/structural_navigation.py
+++ b/src/orca/structural_navigation.py
@@ -358,11 +358,15 @@ class StructuralNavigationObject:
         """Show a list of all the items with this object type."""
 
         try:
-            objects = self.structuralNavigation._getAll(self)
+            objects, criteria = self.structuralNavigation._getAll(self)
         except:
             script.presentMessage(messages.NAVIGATION_DIALOG_ERROR)
             return
 
+        objects = list(filter(lambda x: not script.utilities.isHidden(x), objects))
+        if criteria.applyPredicate:
+            objects = list(filter(self.predicate, objects))
+
         title, columnHeaders, rowData = self._dialogData()
         count = len(objects)
         title = "%s: %s" % (title, messages.itemsFound(count))
@@ -420,11 +424,15 @@ class StructuralNavigationObject:
 
         def showListAtLevel(script, inputEvent):
             try:
-                objects = self.structuralNavigation._getAll(self, arg=level)
+                objects, criteria = self.structuralNavigation._getAll(self, arg=level)
             except:
                 script.presentMessage(messages.NAVIGATION_DIALOG_ERROR)
                 return
 
+            objects = list(filter(lambda x: not script.utilities.isHidden(x), objects))
+            if criteria.applyPredicate:
+                objects = list(filter(self.predicate, objects))
+
             title, columnHeaders, rowData = self._dialogData(arg=level)
             count = len(objects)
             title = "%s: %s" % (title, messages.itemsFound(count))
@@ -626,6 +634,14 @@ class StructuralNavigation:
         #
         self.lastTableCell = [-1, -1]
 
+        self._objectCache = {}
+
+    def clearCache(self, document=None):
+        if document:
+            self._objectCache[hash(document)] = {}
+        else:
+            self._objectCache = {}
+
     def structuralNavigationObjectCreator(self, name):
         """This convenience method creates a StructuralNavigationObject
         with the specified name and associated characterists. (See the
@@ -767,8 +783,8 @@ class StructuralNavigation:
         desiredRow, desiredCol = desiredCoordinates
         rowDiff = desiredRow - currentRow
         colDiff = desiredCol - currentCol
-        oldRowHeaders = self._getRowHeaders(thisCell)
-        oldColHeaders = self._getColumnHeaders(thisCell)
+        oldRowHeaders = self._script.utilities.rowHeadersForCell(thisCell)
+        oldColHeaders = self._script.utilities.columnHeadersForCell(thisCell)
         cell = thisCell
         while cell:
             cell = iTable.getAccessibleAt(desiredRow, desiredCol)
@@ -785,8 +801,7 @@ class StructuralNavigation:
                 elif desiredRow > iTable.nRows - 1:
                     self._script.presentMessage(messages.TABLE_COLUMN_BOTTOM)
                     desiredRow = iTable.nRows - 1
-            elif self._script.utilities.isSameObject(thisCell, cell) \
-                 or settings.skipBlankCells and self._isBlankCell(cell):
+            elif thisCell == cell or (settings.skipBlankCells and self._isBlankCell(cell)):
                 if colDiff < 0:
                     desiredCol -= 1
                 elif colDiff > 0:
@@ -806,9 +821,15 @@ class StructuralNavigation:
     def _getAll(self, structuralNavigationObject, arg=None):
         """Returns all the instances of structuralNavigationObject."""
         if not structuralNavigationObject.criteria:
-            return []
+            return [], None
+
+        document = self._script.utilities.documentFrame()
+        cache = self._objectCache.get(hash(document), {})
+        key = "%s:%s" % (structuralNavigationObject.objType, arg)
+        matches, criteria = cache.get(key, ([], None))
+        if matches:
+            return matches.copy(), criteria
 
-        document = self._getDocument()
         col = document.queryCollection()
         criteria = structuralNavigationObject.criteria(col, arg)
         rule = col.createMatchRule(criteria.states.raw(),
@@ -820,12 +841,12 @@ class StructuralNavigation:
                                    criteria.interfaces,
                                    criteria.matchInterfaces,
                                    criteria.invert)
-        rv = col.getMatches(rule, col.SORT_ORDER_CANONICAL, 0, True)
+        matches = col.getMatches(rule, col.SORT_ORDER_CANONICAL, 0, True)
         col.freeMatchRule(rule)
-        if criteria.applyPredicate:
-            rv = list(filter(structuralNavigationObject.predicate, rv))
-        rv = list(filter(lambda x: not self._script.utilities.isHidden(x), rv))
 
+        rv = matches.copy(), criteria
+        cache[key] = matches, criteria
+        self._objectCache[hash(document)] = cache
         return rv
 
     def goObject(self, structuralNavigationObject, isNext, obj=None, arg=None):
@@ -845,392 +866,69 @@ class StructuralNavigation:
           is needed and passed in as arg.
         """
 
-        currentObject, offset = self._script.utilities.getCaretContext()
-        obj = obj or currentObject
-        try:
-            state = obj.getState()
-        except:
-            return [None, False]
-        else:
-            if state.contains(pyatspi.STATE_DEFUNCT):
-                debug.printException(debug.LEVEL_SEVERE)
-                return [None, False]
-
-        wrap = settings.wrappedStructuralNavigation
-        document = self._getDocument()
-        if not document:
+        matches, criteria = list(self._getAll(structuralNavigationObject, arg))
+        if not matches:
+            structuralNavigationObject.present(None, arg)
             return
 
-        collection = document.queryCollection()
-        criteria = structuralNavigationObject.criteria(collection, arg)
-
-        # If the document frame itself contains content and that is
-        # our current object, querying the collection interface will
-        # result in our starting at the top when looking for the next
-        # object rather than the current caret offset. See bug 567984.
-        #
-        if isNext and self._script.utilities.isSameObject(obj, document):
-            try:
-                document.queryText()
-            except NotImplementedError:
-                pass
-            else:
-                pred = self.isAfterDocumentOffset
-                if criteria.applyPredicate:
-                    pred = pred and structuralNavigationObject.predicate
-                criteria.applyPredicate = True
-                structuralNavigationObject.predicate = pred
-
-        rule = collection.createMatchRule(criteria.states.raw(),
-                                          criteria.matchStates,
-                                          criteria.objAttrs,
-                                          criteria.matchObjAttrs,
-                                          criteria.roles,
-                                          criteria.matchRoles,
-                                          criteria.interfaces,
-                                          criteria.matchInterfaces,
-                                          criteria.invert)
-
-        if criteria.applyPredicate:
-            predicate = structuralNavigationObject.predicate
-        else:
-            predicate = None
-
         if not isNext:
-            [obj, wrapped] = self._findPrevByMatchRule(collection,
-                                                       rule,
-                                                       wrap,
-                                                       obj,
-                                                       predicate)
-        else:
-            [obj, wrapped] = self._findNextByMatchRule(collection,
-                                                       rule,
-                                                       wrap,
-                                                       obj,
-                                                       predicate)
-            collection.freeMatchRule(rule)
-
-        if wrapped:
-            if not isNext:
-                self._script.presentMessage(messages.WRAPPING_TO_BOTTOM)
-            else:
-                self._script.presentMessage(messages.WRAPPING_TO_TOP)
-
-        structuralNavigationObject.present(obj, arg)
-
-    #########################################################################
-    #                                                                       #
-    # Utility Methods for Finding Objects                                   #
-    #                                                                       #
-    #########################################################################
-
-    def isAfterDocumentOffset(self, obj, arg=None):
-        """Returns True if obj is after the document's caret offset."""
-        document = self._getDocument()
-        try:
-            offset = document.queryText().caretOffset
-        except:
-            return False
+            matches.reverse()
 
-        start, end = self._script.utilities.getHyperlinkRange(obj)
-        if start > offset:
-            return True
-
-        try:
-            hypertext = document.queryHypertext()
-            hyperlink = hypertext.getLink(hypertext.getNLinks() - 1)
-        except:
-            return False
-
-        return offset > hyperlink.startIndex
-
-    def _findPrevByMatchRule(self, collection, matchRule, wrap, currentObj,
-                             predicate=None):
-        """Finds the previous object using the given match rule as a
-        pattern to match or not match.
-
-        Arguments:
-        -collection: the accessible collection interface
-        -matchRule: the collections match rule to use
-        -wrap: if True and the bottom of the document is reached, move
-         to the top and keep looking.
-        -currentObj: the object from which the search should begin
-        -predicate: an optional predicate to further test if the item
-         found via collection is indeed a match.
-
-        Returns: [obj, wrapped] where wrapped is a boolean reflecting
-        whether wrapping took place.
-        """
-
-        [currentObj, offset] = self._script.utilities.getCaretContext()
-        document = self._getDocument()
+        def _isValidMatch(obj):
+            if self._script.utilities.isHidden(obj):
+                return False
+            if not criteria.applyPredicate:
+                return True
+            return structuralNavigationObject.predicate(obj)
 
-        # If the current object is the document itself, find an actual
-        # object to use as the starting point. Otherwise we're in
-        # danger of skipping over the objects in between our present
-        # location and top of the document.
-        #
-        if self._script.utilities.isSameObject(currentObj, document):
-            currentObj = self._findNextObject(currentObj, document)
-            offset = 0
-
-        # If the caret context is in a block element that contains children,
-        # the "next" match as far as the collection interface is concerned
-        # is actually the "previous" match as far as we're concerned.
-        nextMatch = collection.getMatchesFrom(
-            currentObj,
-            matchRule,
-            collection.SORT_ORDER_CANONICAL,
-            collection.TREE_INORDER,
-            1,
-            True)
-
-        if nextMatch and nextMatch[0].parent == currentObj:
-            o = self._script.utilities.characterOffsetInParent(nextMatch[0])
-            if 0 <= o < offset \
-               and not self._script.utilities.isHidden(nextMatch[0]) \
-               and (not predicate or predicate(nextMatch[0])):
-                return nextMatch[0], False
-
-        ancestors = []
-        obj = currentObj.parent
-        if obj.getRole() in [pyatspi.ROLE_LIST, pyatspi.ROLE_TABLE]:
-            ancestors.append(obj)
-        else:
+        def _getMatchingObjAndIndex(obj):
             while obj:
-                ancestors.append(obj)
+                if obj in matches:
+                    return obj, matches.index(obj)
                 obj = obj.parent
 
-        match, wrapped = None, False
-        results = collection.getMatchesTo(currentObj,
-                                          matchRule,
-                                          collection.SORT_ORDER_CANONICAL,
-                                          collection.TREE_INORDER,
-                                          True,
-                                          1,
-                                          True)
-        while not match:
-            if len(results) == 0:
-                if wrapped or not wrap:
-                    break
-                elif wrap:
-                    lastObj = self._findLastObject(document)
-                    if self._script.utilities.isSameObject(lastObj, document):
-                        wrapped = True
-                        continue
-
-                    # Collection does not do an inclusive search, meaning
-                    # that the start object is not part of the search.  So
-                    # we need to test the lastobj separately using the given
-                    # matchRule.  We don't have this problem for 'Next' because
-                    # the startobj is the doc frame.
-                    #
-                    secondLastObj = self._findPreviousObject(lastObj, document)
-                    results = collection.getMatchesFrom(\
-                        secondLastObj,
-                        matchRule,
-                        collection.SORT_ORDER_CANONICAL,
-                        collection.TREE_INORDER,
-                        1, 
-                        True)
-                    wrapped = True
-                    if len(results) > 0 \
-                       and not self._script.utilities.isHidden(results[0]) \
-                       and (not predicate or predicate(results[0])):
-                        match = results[0]
-                    else:
-                        results = collection.getMatchesTo(\
-                            lastObj,
-                            matchRule,
-                            collection.SORT_ORDER_CANONICAL,
-                            collection.TREE_INORDER, 
-                            True,
-                            1,
-                            True)
-            elif len(results) > 0:
-                if results[0] in ancestors \
-                   or self._script.utilities.isHidden(results[0]) \
-                   or (predicate and not predicate(results[0])):
-                    results = collection.getMatchesTo(\
-                        results[0],
-                        matchRule,
-                        collection.SORT_ORDER_CANONICAL,
-                        collection.TREE_INORDER,
-                        True,
-                        1,
-                        True)
-                else:
-                    match = results[0]
-
-        return [match, wrapped]
-
-    def _findNextByMatchRule(self, collection, matchRule, wrap, currentObj,
-                             predicate=None):
-        """Finds the next object using the given match rule as a pattern
-        to match or not match.
-
-        Arguments:
-        -collection:  the accessible collection interface
-        -matchRule: the collections match rule to use
-        -wrap: if True and the bottom of the document is reached, move
-         to the top and keep looking.
-        -currentObj: the object from which the search should begin
-        -predicate: an optional predicate to further test if the item
-         found via collection is indeed a match.
-
-        Returns: [obj, wrapped] where wrapped is a boolean reflecting
-        whether wrapping took place.
-        """
-
-        ancestors = []
-        [currentObj, offset] = self._script.utilities.getCaretContext()
-        obj = currentObj.parent
-        while obj:
-            ancestors.append(obj)
-            obj = obj.parent
-
-        match, wrapped = None, False
-        while not match:
-            results = collection.getMatchesFrom(\
-                currentObj,
-                matchRule,
-                collection.SORT_ORDER_CANONICAL,
-                collection.TREE_INORDER,
-                1,
-                True)
-            if len(results) > 0 and not results[0] in ancestors:
-                result = results[0]
-
-                # This can occur with anonymous blocks.
-                if result.parent == currentObj:
-                    o = self._script.utilities.characterOffsetInParent(result)
-                    isBefore = o < offset
-                else:
-                    isBefore = False
-
-                currentObj = result
-                if not (isBefore and not wrapped) \
-                   and not self._script.utilities.isHidden(currentObj) \
-                   and (not predicate or predicate(currentObj)):
-                    match = currentObj
-            elif wrap and not wrapped:
-                wrapped = True
-                ancestors = [currentObj]
-                currentObj = self._getDocument()
-            else:
-                break
-
-        return [match, wrapped]
-
-    def _findPreviousObject(self, obj, stopAncestor):
-        """Finds the object prior to this one, where the tree we're
-        dealing with is a DOM and 'prior' means the previous object
-        in a linear presentation sense.
-
-        Arguments:
-        -obj: the object where to start.
-        -stopAncestor: the ancestor at which the search should stop
-        """
-
-        # NOTE: This method is based on some intial experimentation
-        # with OOo structural navigation.  It might need refining
-        # or fixing and is being overridden by the Gecko method
-        # regardless, so this one can be modified as appropriate.
-        #
-        prevObj = None
-
-        index = obj.getIndexInParent() - 1
-        if index >= 0:
-            prevObj = obj.parent[index]
-            if not prevObj:
-                debug.println(debug.LEVEL_FINE, 'Error: Dead Accessible')
-            elif prevObj.childCount:
-                prevObj = prevObj[prevObj.childCount - 1]
-        elif not self._script.utilities.isSameObject(obj.parent, stopAncestor):
-            prevObj = obj.parent
-
-        return prevObj
-
-    def _findNextObject(self, obj, stopAncestor):
-        """Finds the object after to this one, where the tree we're
-        dealing with is a DOM and 'next' means the next object
-        in a linear presentation sense.
+            return None, -1
 
-        Arguments:
-        -obj: the object where to start.
-        -stopAncestor: the ancestor at which the search should stop
-        """
+        if not obj:
+            obj, offset = self._script.utilities.getCaretContext()
+        thisObj, index = _getMatchingObjAndIndex(obj or currentObject)
+        if thisObj:
+            matches = matches[index:]
+            obj = thisObj
+
+        currentPath = pyatspi.utils.getPath(obj)
+        for i, match in enumerate(matches):
+            if not _isValidMatch(match):
+                continue
 
-        # NOTE: This method is based on some intial experimentation
-        # with OOo structural navigation.  It might need refining
-        # or fixing and is being overridden by the Gecko method
-        # regardless, so this one can be modified as appropriate.
-        #
-        nextObj = None
-
-        if obj and obj.childCount:
-            nextObj = obj[0]
-
-        while obj and obj.parent != obj and not nextObj:
-            index = obj.getIndexInParent() + 1
-            if 0 < index < obj.parent.childCount:
-                nextObj = obj.parent[index]
-                if not nextObj:
-                    debug.println(debug.LEVEL_FINE, 'Error: Dead Accessible')
-                    break
-            elif not self._script.utilities.isSameObject(
-                    obj.parent, stopAncestor):
-                obj = obj.parent
+            if match.parent == obj:
+                comparison = self._script.utilities.characterOffsetInParent(match) - offset
             else:
-                break
-
-        return nextObj
-
-    def _findLastObject(self, ancestor):
-        """Returns the last object in ancestor.
-
-        Arguments:
-        - ancestor: the accessible object whose last (child) object
-          is sought.
-        """
+                path = pyatspi.utils.getPath(match)
+                comparison = self._script.utilities.pathComparison(path, currentPath)
+            if (comparison > 0 and isNext) or (comparison < 0 and not isNext):
+                structuralNavigationObject.present(match, arg)
+                return
 
-        # NOTE: This method is based on some intial experimentation
-        # with OOo structural navigation.  It might need refining
-        # or fixing and is being overridden by the Gecko method
-        # regardless, so this one can be modified as appropriate.
-        #
-        if not ancestor or not ancestor.childCount:
-            return ancestor
-
-        lastChild = ancestor[ancestor.childCount - 1]
-        while lastChild:
-            lastObj = self._findNextObject(lastChild, ancestor)
-            if lastObj:
-                lastChild = lastObj
-            else:
-                break
+        if not settings.wrappedStructuralNavigation:
+            structuralNavigationObject.present(None, arg)
+            return
 
-        return lastChild
+        if not isNext:
+            self._script.presentMessage(messages.WRAPPING_TO_BOTTOM)
+        else:
+            self._script.presentMessage(messages.WRAPPING_TO_TOP)
 
-    def _getDocument(self):
-        """Returns the document or other object in which the object of
-        interest is contained.
-        """
+        matches, criteria = list(self._getAll(structuralNavigationObject, arg))
+        if not isNext:
+            matches.reverse()
 
-        obj, offset = self._script.utilities.getCaretContext()
-        docRoles = [pyatspi.ROLE_DOCUMENT_EMAIL,
-                    pyatspi.ROLE_DOCUMENT_FRAME,
-                    pyatspi.ROLE_DOCUMENT_PRESENTATION,
-                    pyatspi.ROLE_DOCUMENT_SPREADSHEET,
-                    pyatspi.ROLE_DOCUMENT_TEXT,
-                    pyatspi.ROLE_DOCUMENT_WEB]
-        stopRoles = [pyatspi.ROLE_FRAME, pyatspi.ROLE_SCROLL_PANE]
-        document = self._script.utilities.ancestorWithRole(obj, docRoles, stopRoles)
-        if not document and orca_state.locusOfFocus:
-            if orca_state.locusOfFocus.getRole() in docRoles:
-                return orca_state.locusOfFocus
+        for match in matches:
+            if _isValidMatch(match):
+                structuralNavigationObject.present(match, arg)
+                return
 
-        return document
+        structuralNavigationObject.present(None, arg)
 
     #########################################################################
     #                                                                       #
@@ -1258,7 +956,7 @@ class StructuralNavigation:
         """Returns a string which describes the table."""
 
         nonUniformString = ""
-        nonUniform = self._isNonUniformTable(obj)
+        nonUniform = self._script.utilities.isNonUniformTable(obj)
         if nonUniform:
             nonUniformString = messages.TABLE_NON_UNIFORM + " "
 
@@ -1266,27 +964,6 @@ class StructuralNavigation:
         sizeString = messages.tableSize(table.nRows, table.nColumns)
         return (nonUniformString + sizeString)
 
-    def _isNonUniformTable(self, obj):
-        """Returns True if the obj is a non-uniform table (i.e. a table
-        where at least one cell spans multiple rows and/or columns).
-
-        Arguments:
-        - obj: the table to examine
-        """
-
-        try:
-            table = obj.queryTable()
-        except:
-            pass
-        else:
-            for i in range(obj.childCount):
-                [isCell, row, col, rowExtents, colExtents, isSelected] = \
-                                       table.getRowColumnExtentsAtIndex(i)
-                if (rowExtents > 1) or (colExtents > 1):
-                    return True
-
-        return False
-
     def getCellForObj(self, obj):
         """Looks for a table cell in the ancestry of obj, if obj is not a
         table cell.
@@ -1298,10 +975,10 @@ class StructuralNavigation:
         cellRoles = [pyatspi.ROLE_TABLE_CELL,
                      pyatspi.ROLE_COLUMN_HEADER,
                      pyatspi.ROLE_ROW_HEADER]
-        if obj and not obj.getRole() in cellRoles:
-            document = self._getDocument()
-            obj = self._script.utilities.ancestorWithRole(
-                obj, cellRoles, [document.getRole()])
+        isCell = lambda x: x and x.getRole() in cellRoles
+        if obj and not isCell(obj):
+            obj = pyatspi.utils.findAncestor(obj, isCell)
+
         return obj
 
     def getTableForCell(self, obj):
@@ -1311,10 +988,10 @@ class StructuralNavigation:
         - obj: the accessible object of interest.
         """
 
-        if obj and obj.getRole() != pyatspi.ROLE_TABLE:
-            document = self._getDocument()
-            obj = self._script.utilities.ancestorWithRole(
-                obj, [pyatspi.ROLE_TABLE], [document.getRole()])
+        isTable = lambda x: x and x.getRole() == pyatspi.ROLE_TABLE
+        if obj and not isTable(obj):
+            obj = pyatspi.utils.findAncestor(obj, isTable)
+
         return obj
 
     def _isBlankCell(self, obj):
@@ -1370,43 +1047,20 @@ class StructuralNavigation:
         if not (oldRowHeaders or oldColHeaders):
             return
 
-        if rowDiff and not self._isHeader(cell):
-            rowHeaders = self._getRowHeaders(cell)
+        if rowDiff:
+            rowHeaders = self._script.utilities.rowHeadersForCell(cell)
             for header in rowHeaders:
                 if not header in oldRowHeaders:
                     text = self._getCellText(header)
                     speech.speak(text)
 
-        if colDiff and not self._isHeader(cell):
-            colHeaders = self._getColumnHeaders(cell)
+        if colDiff:
+            colHeaders = self._script.utilities.columnHeadersForCell(cell)
             for header in colHeaders:
                 if not header in oldColHeaders:
                     text = self._getCellText(header)
                     speech.speak(text)
 
-    def _getCellSpanInfo(self, obj):
-        """Returns a string reflecting the number of rows and/or columns
-        spanned by a table cell when multiple rows and/or columns are
-        spanned.
-
-        Arguments:
-        - obj: the accessible table cell whose cell span we want.
-        """
-
-        if not obj or (obj.getRole() != pyatspi.ROLE_TABLE_CELL):
-            return
-
-        parentTable = self.getTableForCell(obj)
-        try:
-            table = parentTable.queryTable()
-        except:
-            return
-
-        [row, col] = self.getCellCoordinates(obj)
-        rowspan = table.getRowExtentAt(row, col)
-        colspan = table.getColumnExtentAt(row, col)
-        return messages.cellSpan(rowspan, colspan)
-
     def getCellCoordinates(self, obj):
         """Returns the [row, col] of a ROLE_TABLE_CELL or [-1, -1]
         if the coordinates cannot be found.
@@ -1415,162 +1069,22 @@ class StructuralNavigation:
         - obj: the accessible table cell whose coordinates we want.
         """
 
-        obj = self.getCellForObj(obj)
-        parent = self.getTableForCell(obj)
-        try:
-            table = parent.queryTable()
-        except:
-            pass
-        else:
-            # If we're in a cell that spans multiple rows and/or columns,
-            # thisRow and thisCol will refer to the upper left cell in
-            # the spanned range(s).  We're storing the lastTableCell that
-            # we're aware of in order to facilitate more linear movement.
-            # Therefore, if the lastTableCell and this table cell are the
-            # same cell, we'll go with the stored coordinates.
-            #
-            lastRow, lastCol = self.lastTableCell
-            lastKnownCell = table.getAccessibleAt(lastRow, lastCol)
-            if self._script.utilities.isSameObject(lastKnownCell, obj):
-                return [lastRow, lastCol]
-            else:
-                index = self._script.utilities.cellIndex(obj)
-                thisRow = table.getRowAtIndex(index)
-                thisCol = table.getColumnAtIndex(index)
-                return [thisRow, thisCol]
-
-        return [-1, -1]
-
-    def _getRowHeaders(self, obj):
-        """Returns a list of table cells that serve as a row header for
-        the specified TABLE_CELL.
-
-        Arguments:
-        - obj: the accessible table cell whose header(s) we want.
-        """
-
-        rowHeaders = []
-        if not obj:
-            return rowHeaders
-
-        parentTable = self.getTableForCell(obj)
-        try:
-            table = parentTable.queryTable()
-        except:
-            pass
-        else:
-            [row, col] = self.getCellCoordinates(obj)
-            # Theoretically, we should be able to quickly get the text
-            # of a {row, column}Header via get{Row,Column}Description().
-            # Gecko doesn't expose the information that way, however.
-            # get{Row,Column}Header seems to work sometimes.
-            #
-            header = table.getRowHeader(row)
-            if header:
-                rowHeaders.append(header)
-
-            # Headers that are strictly marked up with <th> do not seem
-            # to be exposed through get{Row, Column}Header.
-            #
-            else:
-                # If our cell spans multiple rows, we want to get all of
-                # the headers that apply.
-                #
-                rowspan = table.getRowExtentAt(row, col)
-                for r in range(row, row+rowspan):
-                    # We could have multiple headers for a given row, one
-                    # header per column.  Presumably all of the headers are
-                    # prior to our present location.
-                    #
-                    for c in range(0, col):
-                        cell = table.getAccessibleAt(r, c)
-                        if self._isHeader(cell) and not cell in rowHeaders:
-                            rowHeaders.append(cell)
-
-        return rowHeaders
-
-    def _getColumnHeaders(self, obj):
-        """Returns a list of table cells that serve as a column header for
-        the specified TABLE_CELL.
-
-        Arguments:
-        - obj: the accessible table cell whose header(s) we want.
-        """
-
-        columnHeaders = []
-        if not obj:
-            return columnHeaders
-
-        parentTable = self.getTableForCell(obj)
-        try:
-            table = parentTable.queryTable()
-        except:
-            pass
-        else:
-            [row, col] = self.getCellCoordinates(obj)
-            # Theoretically, we should be able to quickly get the text
-            # of a {row, column}Header via get{Row,Column}Description().
-            # Gecko doesn't expose the information that way, however.
-            # get{Row,Column}Header seems to work sometimes.
-            #
-            header = table.getColumnHeader(col)
-            if header:
-                columnHeaders.append(header)
-
-            # Headers that are strictly marked up with <th> do not seem
-            # to be exposed through get{Row, Column}Header.
-            #
-            else:
-                # If our cell spans multiple columns, we want to get all of
-                # the headers that apply.
-                #
-                colspan = table.getColumnExtentAt(row, col)
-                for c in range(col, col+colspan):
-                    # We could have multiple headers for a given column, one
-                    # header per row.  Presumably all of the headers are
-                    # prior to our present location.
-                    #
-                    for r in range(0, row):
-                        cell = table.getAccessibleAt(r, c)
-                        if self._isHeader(cell) and not cell in columnHeaders:
-                            columnHeaders.append(cell)
-
-        return columnHeaders
-
-    def _isHeader(self, obj):
-        """Returns True if the table cell is a header.
-
-        Arguments:
-        - obj: the accessible table cell to examine.
-        """
-
-        if not obj:
-            return False
-
-        elif obj.getRole() in [pyatspi.ROLE_TABLE_COLUMN_HEADER,
-                               pyatspi.ROLE_TABLE_ROW_HEADER,
-                               pyatspi.ROLE_COLUMN_HEADER,
-                               pyatspi.ROLE_ROW_HEADER]:
-            return True
-
-        else:
-            attributes = obj.getAttributes()
-            if attributes:
-                for attribute in attributes:
-                    if attribute == "tag:TH":
-                        return True
+        cell = self.getCellForObj(obj)
+        table = self.getTableForCell(cell)
+        thisRow, thisCol = self._script.utilities.coordinatesForCell(cell)
 
-        return False
+        # If we're in a cell that spans multiple rows and/or columns,
+        # thisRow and thisCol will refer to the upper left cell in
+        # the spanned range(s).  We're storing the lastTableCell that
+        # we're aware of in order to facilitate more linear movement.
+        # Therefore, if the lastTableCell and this table cell are the
+        # same cell, we'll go with the stored coordinates.
+        lastRow, lastCol = self.lastTableCell
+        lastCell = self._script.utilities.cellForCoordinates(table, lastRow, lastCol)
+        if lastCell == cell:
+            return lastRow, lastCol
 
-    def _getHeadingLevel(self, obj):
-        """Determines the heading level of the given object.  A value
-        of 0 means there is no heading level.
-
-        Arguments:
-        - obj: the accessible whose heading level we want.
-        """
-
-        return self._script.utilities.headingLevel(obj)
+        return thisRow, thisCol
 
     def _getCaretPosition(self, obj):
         """Returns the [obj, characterOffset] where the caret should be
@@ -1597,6 +1111,9 @@ class StructuralNavigation:
         - offset: the character offset within obj.
         """
 
+        if not obj:
+            return
+
         if self._presentWithSayAll(obj, offset):
             return
 
@@ -1611,18 +1128,13 @@ class StructuralNavigation:
         - offset: the character offset within obj.
         """
 
-        if self._presentWithSayAll(obj, offset):
+        if not obj:
             return
 
-        self._script.updateBraille(obj)
-        voices = self._script.voices
-        if obj.getRole() == pyatspi.ROLE_LINK:
-            voice = voices[settings.HYPERLINK_VOICE]
-        else:
-            voice = voices[settings.DEFAULT_VOICE]
+        if self._presentWithSayAll(obj, offset):
+            return
 
-        utterances = self._script.speechGenerator.generateSpeech(obj)
-        speech.speak(utterances, voice)
+        self._script.presentObject(obj, offset)
 
     def _presentWithSayAll(self, obj, offset):
         if self._script.inSayAll() \
@@ -2457,7 +1969,7 @@ class StructuralNavigation:
         isMatch = False
         if obj and obj.getRole() == pyatspi.ROLE_HEADING:
             if arg:
-                isMatch = (arg == self._getHeadingLevel(obj))
+                isMatch = arg == self._script.utilities.headingLevel(obj)
             else:
                 isMatch = True
 
@@ -2493,7 +2005,8 @@ class StructuralNavigation:
             columnHeaders.append(guilabels.SN_HEADER_LEVEL)
 
             def rowData(obj):
-                return [self._getText(obj), str(self._getHeadingLevel(obj))]
+                return [self._getText(obj),
+                        str(self._script.utilities.headingLevel(obj))]
 
         else:
             title = guilabels.SN_TITLE_HEADING_AT_LEVEL % arg
@@ -2657,7 +2170,7 @@ class StructuralNavigation:
         if obj:
             [obj, characterOffset] = self._getCaretPosition(obj)
             self._setCaretPosition(obj, characterOffset)
-            self._presentLine(obj, characterOffset)
+            self._presentObject(obj, characterOffset)
         else:
             full = messages.NO_LANDMARK_FOUND
             brief = messages.STRUCTURAL_NAVIGATION_NOT_FOUND
@@ -2739,6 +2252,7 @@ class StructuralNavigation:
         """
 
         if obj:
+            speech.speak(self._script.speechGenerator.generateSpeech(obj))
             [obj, characterOffset] = self._getCaretPosition(obj)
             self._setCaretPosition(obj, characterOffset)
             self._presentLine(obj, characterOffset)
@@ -2825,10 +2339,6 @@ class StructuralNavigation:
         if obj:
             [obj, characterOffset] = self._getCaretPosition(obj)
             self._setCaretPosition(obj, characterOffset)
-            # TODO: We currently present the line, so that's kept here.
-            # But we should probably present the object, which would
-            # be consistent with the change made recently for headings.
-            #
             self._presentLine(obj, characterOffset)
         else:
             full = messages.NO_MORE_LIST_ITEMS
@@ -2909,13 +2419,7 @@ class StructuralNavigation:
         """
 
         if obj:
-            # TODO: We don't want to move to a list item.
-            # Is this the best place to handle this?
-            #
-            if obj.getRole() == pyatspi.ROLE_LIST:
-                characterOffset = 0
-            else:
-                [obj, characterOffset] = self._getCaretPosition(obj)
+            [obj, characterOffset] = self._getCaretPosition(obj)
             self._setCaretPosition(obj, characterOffset)
             self._presentObject(obj, characterOffset)
         else:
@@ -3342,7 +2846,8 @@ class StructuralNavigation:
             self._script.presentMessage(messages.TABLE_CELL_COORDINATES \
                                         % {"row" : row + 1, "column" : col + 1})
 
-        spanString = self._getCellSpanInfo(cell)
+        rowspan, colspan = self._script.utilities.rowAndColumnSpan(cell)
+        spanString = messages.cellSpan(rowspan, colspan)
         if spanString and settings.speakCellSpan:
             self._script.presentMessage(spanString)
 
diff --git a/test/html/lists.html b/test/html/lists.html
index 42427fb..5f486c1 100644
--- a/test/html/lists.html
+++ b/test/html/lists.html
@@ -26,28 +26,33 @@
 
   Unordered list:
   <ul>
-    <li>listing item</li>
-    <ul>
-      <li>first sublevel</li>
+    <li>listing item
       <ul>
-        <li>look for the bullet on</li>
-        <ul>
-          <li>each sublevel</li>
-          <li>they should all be different, except here.</li>
-        </ul>
-        <li><font size="-0">second sublevel</font></li>
+       <li>first sublevel
+         <ul>
+            <li>look for the bullet on
+              <ul>
+               <li>each sublevel</li>
+               <li>they should all be different, except here.</li>
+              </ul>
+           </li>
+            <li><font size="-0">second sublevel</font></li>
+         </ul>
+       </li>
+       <li type="square">or you can specify a square
+         <ul>
+            <li type="circle">if your TYPE is circle</li>
+            <li type="disc">or even a disc</li>
+         </ul>
+       </li>
       </ul>
-      <li type="square">or you can specify a square</li>
+    </li>
+    <li type="square">Franz Liszt
       <ul>
-        <li type="circle">if your TYPE is circle</li>
-        <li type="disc">or even a disc</li>
+       <li>was a composer who was not square</li>
+       <li type="disc">would have liked the Who</li>
       </ul>
-    </ul>
-    <li type="square">Franz Liszt</li>
-    <ul>
-      <li>was a composer who was not square</li>
-      <li type="disc">would have liked the Who</li>
-    </ul>
+    </li>
   </ul>
   <ul type="circle">
     <li>feeling listless</li>
diff --git a/test/keystrokes/firefox/aria_landmarks.py b/test/keystrokes/firefox/aria_landmarks.py
index da6f4b6..bd84d06 100644
--- a/test/keystrokes/firefox/aria_landmarks.py
+++ b/test/keystrokes/firefox/aria_landmarks.py
@@ -13,18 +13,16 @@ sequence.append(utils.StartRecordingAction())
 sequence.append(KeyComboAction("m"))
 sequence.append(utils.AssertPresentationAction(
     "1. m to next landmark",
-    ["BRAILLE LINE:  'navigation main'",
-     "     VISIBLE:  'navigation main', cursor=1",
-     "SPEECH OUTPUT: 'navigation'",
-     "SPEECH OUTPUT: 'main'"]))
+    ["BRAILLE LINE:  'navigation'",
+     "     VISIBLE:  'navigation', cursor=1",
+     "SPEECH OUTPUT: 'navigation'"]))
 
 sequence.append(utils.StartRecordingAction())
 sequence.append(KeyComboAction("m"))
 sequence.append(utils.AssertPresentationAction(
     "2. m to next landmark",
-    ["BRAILLE LINE:  'navigation main'",
-     "     VISIBLE:  'navigation main', cursor=12",
-     "SPEECH OUTPUT: 'navigation'",
+    ["BRAILLE LINE:  'main'",
+     "     VISIBLE:  'main', cursor=1",
      "SPEECH OUTPUT: 'main'"]))
 
 sequence.append(utils.StartRecordingAction())
@@ -102,8 +100,23 @@ sequence.append(utils.StartRecordingAction())
 sequence.append(KeyComboAction("<Shift>m"))
 sequence.append(utils.AssertPresentationAction(
     "11. Shift+m to previous landmark",
-    ["KNOWN ISSUE: We are skipping over complementary on the way back",
-     "BRAILLE LINE:  'application embedded'",
+    ["BRAILLE LINE:  'form'",
+     "     VISIBLE:  'form', cursor=1",
+     "SPEECH OUTPUT: 'form'"]))
+
+sequence.append(utils.StartRecordingAction())
+sequence.append(KeyComboAction("<Shift>m"))
+sequence.append(utils.AssertPresentationAction(
+    "12. Shift+m to previous landmark",
+    ["BRAILLE LINE:  'complementary'",
+     "     VISIBLE:  'complementary', cursor=1",
+     "SPEECH OUTPUT: 'complementary'"]))
+
+sequence.append(utils.StartRecordingAction())
+sequence.append(KeyComboAction("<Shift>m"))
+sequence.append(utils.AssertPresentationAction(
+    "13. Shift+m to previous landmark",
+    ["BRAILLE LINE:  'application embedded'",
      "     VISIBLE:  'application embedded', cursor=1",
      "SPEECH OUTPUT: 'application'",
      "SPEECH OUTPUT: 'embedded'"]))
@@ -111,17 +124,23 @@ sequence.append(utils.AssertPresentationAction(
 sequence.append(utils.StartRecordingAction())
 sequence.append(KeyComboAction("<Shift>m"))
 sequence.append(utils.AssertPresentationAction(
-    "12. Shift+m to previous landmark",
-    ["KNOWN ISSUE: We are skipping over navigation on the way back",
-     "BRAILLE LINE:  'navigation main'",
-     "     VISIBLE:  'navigation main', cursor=1",
-     "SPEECH OUTPUT: 'navigation'",
+    "14. Shift+m to previous landmark",
+    ["BRAILLE LINE:  'main'",
+     "     VISIBLE:  'main', cursor=1",
      "SPEECH OUTPUT: 'main'"]))
 
 sequence.append(utils.StartRecordingAction())
 sequence.append(KeyComboAction("<Shift>m"))
 sequence.append(utils.AssertPresentationAction(
-    "13. Shift+m to previous landmark",
+    "15. Shift+m to previous landmark",
+    ["BRAILLE LINE:  'navigation'",
+     "     VISIBLE:  'navigation', cursor=1",
+     "SPEECH OUTPUT: 'navigation'"]))
+
+sequence.append(utils.StartRecordingAction())
+sequence.append(KeyComboAction("<Shift>m"))
+sequence.append(utils.AssertPresentationAction(
+    "16. Shift+m to previous landmark",
     ["BRAILLE LINE:  'banner'",
      "     VISIBLE:  'banner', cursor=1",
      "SPEECH OUTPUT: 'banner'"]))


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]