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