Use ElementTraversal some more
[WebKit-https.git] / Source / WebCore / accessibility / AccessibilityTable.cpp
1 /*
2  * Copyright (C) 2008 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "config.h"
30 #include "AccessibilityTable.h"
31
32 #include "AXObjectCache.h"
33 #include "AccessibilityTableCell.h"
34 #include "AccessibilityTableColumn.h"
35 #include "AccessibilityTableHeaderContainer.h"
36 #include "AccessibilityTableRow.h"
37 #include "ElementTraversal.h"
38 #include "HTMLNames.h"
39 #include "HTMLTableCaptionElement.h"
40 #include "HTMLTableCellElement.h"
41 #include "HTMLTableElement.h"
42 #include "RenderObject.h"
43 #include "RenderTable.h"
44 #include "RenderTableCell.h"
45 #include "RenderTableSection.h"
46
47 namespace WebCore {
48
49 using namespace HTMLNames;
50
51 AccessibilityTable::AccessibilityTable(RenderObject* renderer)
52     : AccessibilityRenderObject(renderer)
53     , m_headerContainer(0)
54     , m_isAccessibilityTable(true)
55 {
56 }
57
58 AccessibilityTable::~AccessibilityTable()
59 {
60 }
61
62 void AccessibilityTable::init()
63 {
64     AccessibilityRenderObject::init();
65     m_isAccessibilityTable = isTableExposableThroughAccessibility();
66 }
67
68 PassRefPtr<AccessibilityTable> AccessibilityTable::create(RenderObject* renderer)
69 {
70     return adoptRef(new AccessibilityTable(renderer));
71 }
72
73 bool AccessibilityTable::hasARIARole() const
74 {
75     if (!m_renderer)
76         return false;
77     
78     AccessibilityRole ariaRole = ariaRoleAttribute();
79     if (ariaRole != UnknownRole)
80         return true;
81
82     return false;
83 }
84
85 bool AccessibilityTable::isAccessibilityTable() const
86 {
87     if (!m_renderer)
88         return false;
89     
90     return m_isAccessibilityTable;
91 }
92
93 bool AccessibilityTable::isDataTable() const
94 {
95     if (!m_renderer)
96         return false;
97
98     // Do not consider it a data table is it has an ARIA role.
99     if (hasARIARole())
100         return false;
101
102     // When a section of the document is contentEditable, all tables should be
103     // treated as data tables, otherwise users may not be able to work with rich
104     // text editors that allow creating and editing tables.
105     if (node() && node()->rendererIsEditable())
106         return true;
107
108     // This employs a heuristic to determine if this table should appear.
109     // Only "data" tables should be exposed as tables.
110     // Unfortunately, there is no good way to determine the difference
111     // between a "layout" table and a "data" table.
112     
113     RenderTable* table = toRenderTable(m_renderer);
114     Node* tableNode = table->node();
115     if (!tableNode || !isHTMLTableElement(tableNode))
116         return false;
117
118     // if there is a caption element, summary, THEAD, or TFOOT section, it's most certainly a data table
119     HTMLTableElement* tableElement = toHTMLTableElement(tableNode);
120     if (!tableElement->summary().isEmpty() || tableElement->tHead() || tableElement->tFoot() || tableElement->caption())
121         return true;
122     
123     // if someone used "rules" attribute than the table should appear
124     if (!tableElement->rules().isEmpty())
125         return true;    
126
127     // if there's a colgroup or col element, it's probably a data table.
128     for (Element* child = ElementTraversal::firstChild(tableElement); child; child = ElementTraversal::nextSibling(child)) {
129         if (child->hasTagName(colTag) || child->hasTagName(colgroupTag))
130             return true;
131     }
132     
133     // go through the cell's and check for tell-tale signs of "data" table status
134     // cells have borders, or use attributes like headers, abbr, scope or axis
135     table->recalcSectionsIfNeeded();
136     RenderTableSection* firstBody = table->firstBody();
137     if (!firstBody)
138         return false;
139     
140     int numCols = firstBody->numColumns();
141     int numRows = firstBody->numRows();
142     
143     // If there's only one cell, it's not a good AXTable candidate.
144     if (numRows == 1 && numCols == 1)
145         return false;
146
147     // If there are at least 20 rows, we'll call it a data table.
148     if (numRows >= 20)
149         return true;
150     
151     // Store the background color of the table to check against cell's background colors.
152     RenderStyle* tableStyle = table->style();
153     if (!tableStyle)
154         return false;
155     Color tableBGColor = tableStyle->visitedDependentColor(CSSPropertyBackgroundColor);
156     
157     // check enough of the cells to find if the table matches our criteria
158     // Criteria: 
159     //   1) must have at least one valid cell (and)
160     //   2) at least half of cells have borders (or)
161     //   3) at least half of cells have different bg colors than the table, and there is cell spacing
162     unsigned validCellCount = 0;
163     unsigned borderedCellCount = 0;
164     unsigned backgroundDifferenceCellCount = 0;
165     unsigned cellsWithTopBorder = 0;
166     unsigned cellsWithBottomBorder = 0;
167     unsigned cellsWithLeftBorder = 0;
168     unsigned cellsWithRightBorder = 0;
169     
170     Color alternatingRowColors[5];
171     int alternatingRowColorCount = 0;
172     
173     int headersInFirstColumnCount = 0;
174     for (int row = 0; row < numRows; ++row) {
175     
176         int headersInFirstRowCount = 0;
177         for (int col = 0; col < numCols; ++col) {    
178             RenderTableCell* cell = firstBody->primaryCellAt(row, col);
179             if (!cell)
180                 continue;
181             Node* cellNode = cell->node();
182             if (!cellNode)
183                 continue;
184             
185             if (cell->width() < 1 || cell->height() < 1)
186                 continue;
187             
188             validCellCount++;
189             
190             HTMLTableCellElement* cellElement = static_cast<HTMLTableCellElement*>(cellNode);
191             
192             bool isTHCell = cellElement->hasTagName(thTag);
193             // If the first row is comprised of all <th> tags, assume it is a data table.
194             if (!row && isTHCell)
195                 headersInFirstRowCount++;
196
197             // If the first column is comprised of all <th> tags, assume it is a data table.
198             if (!col && isTHCell)
199                 headersInFirstColumnCount++;
200             
201             // in this case, the developer explicitly assigned a "data" table attribute
202             if (!cellElement->headers().isEmpty() || !cellElement->abbr().isEmpty()
203                 || !cellElement->axis().isEmpty() || !cellElement->scope().isEmpty())
204                 return true;
205             
206             RenderStyle* renderStyle = cell->style();
207             if (!renderStyle)
208                 continue;
209
210             // If the empty-cells style is set, we'll call it a data table.
211             if (renderStyle->emptyCells() == HIDE)
212                 return true;
213
214             // If a cell has matching bordered sides, call it a (fully) bordered cell.
215             if ((cell->borderTop() > 0 && cell->borderBottom() > 0)
216                 || (cell->borderLeft() > 0 && cell->borderRight() > 0))
217                 borderedCellCount++;
218
219             // Also keep track of each individual border, so we can catch tables where most
220             // cells have a bottom border, for example.
221             if (cell->borderTop() > 0)
222                 cellsWithTopBorder++;
223             if (cell->borderBottom() > 0)
224                 cellsWithBottomBorder++;
225             if (cell->borderLeft() > 0)
226                 cellsWithLeftBorder++;
227             if (cell->borderRight() > 0)
228                 cellsWithRightBorder++;
229             
230             // If the cell has a different color from the table and there is cell spacing,
231             // then it is probably a data table cell (spacing and colors take the place of borders).
232             Color cellColor = renderStyle->visitedDependentColor(CSSPropertyBackgroundColor);
233             if (table->hBorderSpacing() > 0 && table->vBorderSpacing() > 0
234                 && tableBGColor != cellColor && cellColor.alpha() != 1)
235                 backgroundDifferenceCellCount++;
236             
237             // If we've found 10 "good" cells, we don't need to keep searching.
238             if (borderedCellCount >= 10 || backgroundDifferenceCellCount >= 10)
239                 return true;
240             
241             // For the first 5 rows, cache the background color so we can check if this table has zebra-striped rows.
242             if (row < 5 && row == alternatingRowColorCount) {
243                 RenderObject* renderRow = cell->parent();
244                 if (!renderRow || !renderRow->isBoxModelObject() || !toRenderBoxModelObject(renderRow)->isTableRow())
245                     continue;
246                 RenderStyle* rowRenderStyle = renderRow->style();
247                 if (!rowRenderStyle)
248                     continue;
249                 Color rowColor = rowRenderStyle->visitedDependentColor(CSSPropertyBackgroundColor);
250                 alternatingRowColors[alternatingRowColorCount] = rowColor;
251                 alternatingRowColorCount++;
252             }
253         }
254         
255         if (!row && headersInFirstRowCount == numCols && numCols > 1)
256             return true;
257     }
258
259     if (headersInFirstColumnCount == numRows && numRows > 1)
260         return true;
261     
262     // if there is less than two valid cells, it's not a data table
263     if (validCellCount <= 1)
264         return false;
265     
266     // half of the cells had borders, it's a data table
267     unsigned neededCellCount = validCellCount / 2;
268     if (borderedCellCount >= neededCellCount
269         || cellsWithTopBorder >= neededCellCount
270         || cellsWithBottomBorder >= neededCellCount
271         || cellsWithLeftBorder >= neededCellCount
272         || cellsWithRightBorder >= neededCellCount)
273         return true;
274     
275     // half had different background colors, it's a data table
276     if (backgroundDifferenceCellCount >= neededCellCount)
277         return true;
278
279     // Check if there is an alternating row background color indicating a zebra striped style pattern.
280     if (alternatingRowColorCount > 2) {
281         Color firstColor = alternatingRowColors[0];
282         for (int k = 1; k < alternatingRowColorCount; k++) {
283             // If an odd row was the same color as the first row, its not alternating.
284             if (k % 2 == 1 && alternatingRowColors[k] == firstColor)
285                 return false;
286             // If an even row is not the same as the first row, its not alternating.
287             if (!(k % 2) && alternatingRowColors[k] != firstColor)
288                 return false;
289         }
290         return true;
291     }
292     
293     return false;
294 }
295     
296 bool AccessibilityTable::isTableExposableThroughAccessibility() const
297 {
298     // The following is a heuristic used to determine if a
299     // <table> should be exposed as an AXTable. The goal
300     // is to only show "data" tables.
301
302     if (!m_renderer)
303         return false;
304
305     // If the developer assigned an aria role to this, then we
306     // shouldn't expose it as a table, unless, of course, the aria
307     // role is a table.
308     if (hasARIARole())
309         return false;
310
311     // Gtk+ ATs expect all tables to be exposed as tables.
312 #if PLATFORM(GTK)
313     Node* tableNode = toRenderTable(m_renderer)->node();
314     return tableNode && isHTMLTableElement(tableNode);
315 #endif
316
317     return isDataTable();
318 }
319
320 void AccessibilityTable::clearChildren()
321 {
322     AccessibilityRenderObject::clearChildren();
323     m_rows.clear();
324     m_columns.clear();
325
326     if (m_headerContainer) {
327         m_headerContainer->detachFromParent();
328         m_headerContainer = 0;
329     }
330 }
331
332 void AccessibilityTable::addChildren()
333 {
334     if (!isAccessibilityTable()) {
335         AccessibilityRenderObject::addChildren();
336         return;
337     }
338     
339     ASSERT(!m_haveChildren); 
340     
341     m_haveChildren = true;
342     if (!m_renderer || !m_renderer->isTable())
343         return;
344     
345     RenderTable* table = toRenderTable(m_renderer);
346     AXObjectCache* axCache = m_renderer->document()->axObjectCache();
347
348     // Go through all the available sections to pull out the rows and add them as children.
349     table->recalcSectionsIfNeeded();
350     RenderTableSection* tableSection = table->topSection();
351     if (!tableSection)
352         return;
353     
354     unsigned maxColumnCount = 0;
355     while (tableSection) {
356         
357         HashSet<AccessibilityObject*> appendedRows;
358         unsigned numRows = tableSection->numRows();
359         for (unsigned rowIndex = 0; rowIndex < numRows; ++rowIndex) {
360             
361             RenderTableRow* renderRow = tableSection->rowRendererAt(rowIndex);
362             if (!renderRow)
363                 continue;
364             
365             AccessibilityObject* rowObject = axCache->getOrCreate(renderRow);
366             if (!rowObject->isTableRow())
367                 continue;
368             
369             AccessibilityTableRow* row = static_cast<AccessibilityTableRow*>(rowObject);
370             // We need to check every cell for a new row, because cell spans
371             // can cause us to miss rows if we just check the first column.
372             if (appendedRows.contains(row))
373                 continue;
374             
375             row->setRowIndex(static_cast<int>(m_rows.size()));
376             m_rows.append(row);
377             if (!row->accessibilityIsIgnored())
378                 m_children.append(row);
379 #if PLATFORM(GTK)
380             else
381                 m_children.appendVector(row->children());
382 #endif
383             appendedRows.add(row);
384         }
385     
386         maxColumnCount = max(tableSection->numColumns(), maxColumnCount);
387         tableSection = table->sectionBelow(tableSection, SkipEmptySections);
388     }
389     
390     // make the columns based on the number of columns in the first body
391     unsigned length = maxColumnCount;
392     for (unsigned i = 0; i < length; ++i) {
393         AccessibilityTableColumn* column = static_cast<AccessibilityTableColumn*>(axCache->getOrCreate(ColumnRole));
394         column->setColumnIndex((int)i);
395         column->setParent(this);
396         m_columns.append(column);
397         if (!column->accessibilityIsIgnored())
398             m_children.append(column);
399     }
400     
401     AccessibilityObject* headerContainerObject = headerContainer();
402     if (headerContainerObject && !headerContainerObject->accessibilityIsIgnored())
403         m_children.append(headerContainerObject);
404 }
405     
406 AccessibilityObject* AccessibilityTable::headerContainer()
407 {
408     if (m_headerContainer)
409         return m_headerContainer.get();
410     
411     AccessibilityMockObject* tableHeader = toAccessibilityMockObject(axObjectCache()->getOrCreate(TableHeaderContainerRole));
412     tableHeader->setParent(this);
413
414     m_headerContainer = tableHeader;
415     return m_headerContainer.get();
416 }
417
418 AccessibilityObject::AccessibilityChildrenVector& AccessibilityTable::columns()
419 {
420     updateChildrenIfNecessary();
421         
422     return m_columns;
423 }
424
425 AccessibilityObject::AccessibilityChildrenVector& AccessibilityTable::rows()
426 {
427     updateChildrenIfNecessary();
428     
429     return m_rows;
430 }
431     
432 void AccessibilityTable::rowHeaders(AccessibilityChildrenVector& headers)
433 {
434     if (!m_renderer)
435         return;
436     
437     updateChildrenIfNecessary();
438     
439     unsigned rowCount = m_rows.size();
440     for (unsigned k = 0; k < rowCount; ++k) {
441         AccessibilityObject* header = static_cast<AccessibilityTableRow*>(m_rows[k].get())->headerObject();
442         if (!header)
443             continue;
444         headers.append(header);
445     }
446 }
447
448 void AccessibilityTable::columnHeaders(AccessibilityChildrenVector& headers)
449 {
450     if (!m_renderer)
451         return;
452     
453     updateChildrenIfNecessary();
454     
455     unsigned colCount = m_columns.size();
456     for (unsigned k = 0; k < colCount; ++k) {
457         AccessibilityObject* header = static_cast<AccessibilityTableColumn*>(m_columns[k].get())->headerObject();
458         if (!header)
459             continue;
460         headers.append(header);
461     }
462 }
463     
464 void AccessibilityTable::cells(AccessibilityObject::AccessibilityChildrenVector& cells)
465 {
466     if (!m_renderer)
467         return;
468     
469     updateChildrenIfNecessary();
470     
471     for (size_t row = 0; row < m_rows.size(); ++row)
472         cells.appendVector(m_rows[row]->children());
473 }
474     
475 unsigned AccessibilityTable::columnCount()
476 {
477     updateChildrenIfNecessary();
478     
479     return m_columns.size();    
480 }
481     
482 unsigned AccessibilityTable::rowCount()
483 {
484     updateChildrenIfNecessary();
485     
486     return m_rows.size();
487 }
488
489 int AccessibilityTable::tableLevel() const
490 {
491     int level = 0;
492     for (AccessibilityObject* obj = static_cast<AccessibilityObject*>(const_cast<AccessibilityTable*>(this)); obj; obj = obj->parentObject()) {
493         if (obj->isAccessibilityTable())
494             ++level;
495     }
496     
497     return level;
498 }
499
500 AccessibilityTableCell* AccessibilityTable::cellForColumnAndRow(unsigned column, unsigned row)
501 {
502     updateChildrenIfNecessary();
503     if (column >= columnCount() || row >= rowCount())
504         return 0;
505     
506     // Iterate backwards through the rows in case the desired cell has a rowspan and exists in a previous row.
507     for (unsigned rowIndexCounter = row + 1; rowIndexCounter > 0; --rowIndexCounter) {
508         unsigned rowIndex = rowIndexCounter - 1;
509         AccessibilityChildrenVector children = m_rows[rowIndex]->children();
510         // Since some cells may have colspans, we have to check the actual range of each
511         // cell to determine which is the right one.
512         for (unsigned colIndexCounter = std::min(static_cast<unsigned>(children.size()), column + 1); colIndexCounter > 0; --colIndexCounter) {
513             unsigned colIndex = colIndexCounter - 1;
514             AccessibilityObject* child = children[colIndex].get();
515             ASSERT(child->isTableCell());
516             if (!child->isTableCell())
517                 continue;
518             
519             pair<unsigned, unsigned> columnRange;
520             pair<unsigned, unsigned> rowRange;
521             AccessibilityTableCell* tableCellChild = static_cast<AccessibilityTableCell*>(child);
522             tableCellChild->columnIndexRange(columnRange);
523             tableCellChild->rowIndexRange(rowRange);
524             
525             if ((column >= columnRange.first && column < (columnRange.first + columnRange.second))
526                 && (row >= rowRange.first && row < (rowRange.first + rowRange.second)))
527                 return tableCellChild;
528         }
529     }
530     
531     return 0;
532 }
533
534 AccessibilityRole AccessibilityTable::roleValue() const
535 {
536     if (!isAccessibilityTable())
537         return AccessibilityRenderObject::roleValue();
538
539     return TableRole;
540 }
541     
542 bool AccessibilityTable::computeAccessibilityIsIgnored() const
543 {
544     AccessibilityObjectInclusion decision = defaultObjectInclusion();
545     if (decision == IncludeObject)
546         return false;
547     if (decision == IgnoreObject)
548         return true;
549     
550     if (!isAccessibilityTable())
551         return AccessibilityRenderObject::computeAccessibilityIsIgnored();
552         
553     return false;
554 }
555     
556 String AccessibilityTable::title() const
557 {
558     if (!isAccessibilityTable())
559         return AccessibilityRenderObject::title();
560     
561     String title;
562     if (!m_renderer)
563         return title;
564     
565     // see if there is a caption
566     Node* tableElement = m_renderer->node();
567     if (tableElement && isHTMLTableElement(tableElement)) {
568         HTMLTableCaptionElement* caption = toHTMLTableElement(tableElement)->caption();
569         if (caption)
570             title = caption->innerText();
571     }
572     
573     // try the standard 
574     if (title.isEmpty())
575         title = AccessibilityRenderObject::title();
576     
577     return title;
578 }
579
580 } // namespace WebCore