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