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