001 /*
002 * Copyright (c) 2006 Henri Sivonen
003 *
004 * Permission is hereby granted, free of charge, to any person obtaining a
005 * copy of this software and associated documentation files (the "Software"),
006 * to deal in the Software without restriction, including without limitation
007 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
008 * and/or sell copies of the Software, and to permit persons to whom the
009 * Software is furnished to do so, subject to the following conditions:
010 *
011 * The above copyright notice and this permission notice shall be included in
012 * all copies or substantial portions of the Software.
013 *
014 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
015 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
016 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
017 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
018 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
019 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
020 * DEALINGS IN THE SOFTWARE.
021 */
022
023 package org.whattf.checker.table;
024
025 import java.util.HashSet;
026 import java.util.Iterator;
027 import java.util.LinkedList;
028 import java.util.List;
029 import java.util.Set;
030
031 import org.whattf.checker.AttributeUtil;
032 import org.xml.sax.Attributes;
033 import org.xml.sax.Locator;
034 import org.xml.sax.SAXException;
035 import org.xml.sax.SAXParseException;
036 import org.xml.sax.helpers.LocatorImpl;
037
038
039 /**
040 * Represents an XHTML table for table integrity checking. Handles
041 * table-significant parse events and keeps track of columns.
042 *
043 * @version $Id: Table.java 205 2007-10-14 19:43:03Z hsivonen $
044 * @author hsivonen
045 */
046 final class Table {
047
048 /**
049 * An enumeration for keeping track of the parsing state of a table.
050 */
051 private enum State {
052
053 /**
054 * The table element start has been seen. No child elements have been seen.
055 * A start of a column, a column group, a row or a row group or the end of
056 * the table is expected.
057 */
058 IN_TABLE_AT_START,
059
060 /**
061 * The table element is the open element and rows have been seen. A row in
062 * an implicit group, a row group or the end of the table is expected.
063 */
064 IN_TABLE_AT_POTENTIAL_ROW_GROUP_START,
065
066 /**
067 * A column group is open. It can end or a column can start.
068 */
069 IN_COLGROUP,
070
071 /**
072 * A column inside a column group is open. It can end.
073 */
074 IN_COL_IN_COLGROUP,
075
076 /**
077 * A column that is a child of table is open. It can end.
078 */
079 IN_COL_IN_IMPLICIT_GROUP,
080
081 /**
082 * The open element is an explicit row group. It may end or a row may start.
083 */
084 IN_ROW_GROUP,
085
086 /**
087 * A row in a an explicit row group is open. It may end or a cell may start.
088 */
089 IN_ROW_IN_ROW_GROUP,
090
091 /**
092 * A cell inside a row inside an explicit row group is open. It can end.
093 */
094 IN_CELL_IN_ROW_GROUP,
095
096 /**
097 * A row in an implicit row group is open. It may end or a cell may start.
098 */
099 IN_ROW_IN_IMPLICIT_ROW_GROUP,
100
101 /**
102 * The table itself is the currently open element, but an implicit row group
103 * been started by previous rows. A row may start, an explicit row group may
104 * start or the table may end.
105 */
106 IN_IMPLICIT_ROW_GROUP,
107
108 /**
109 * A cell inside an implicit row group is open. It can close.
110 */
111 IN_CELL_IN_IMPLICIT_ROW_GROUP,
112
113 /**
114 * The table itself is the currently open element. Columns and/or column groups
115 * have been seen but rows or row groups have not been seen yet. A column, a
116 * column group, a row or a row group can start. The table can end.
117 */
118 IN_TABLE_COLS_SEEN
119 }
120
121 /**
122 * Keeps track of the handler state between SAX events.
123 */
124 private State state = State.IN_TABLE_AT_START;
125
126 /**
127 * The number of suppressed element starts.
128 */
129 private int suppressedStarts = 0;
130
131 /**
132 * Indicates whether the width of the table was established by column markup.
133 */
134 private boolean hardWidth = false;
135
136 /**
137 * The column count established by column markup or by the first row.
138 */
139 private int columnCount = -1;
140
141 /**
142 * The actual column count as stretched by the widest row.
143 */
144 private int realColumnCount = 0;
145
146 /**
147 * A colgroup span that hasn't been actuated yet in case the element has
148 * col children. The absolute value counts. The negative sign means that
149 * the value was implied.
150 */
151 private int pendingColGroupSpan = 0;
152
153 /**
154 * A set of the IDs of header cells.
155 */
156 private final Set<String> headerIds = new HashSet<String>();
157
158 /**
159 * A list of cells that refer to headers (in the document order).
160 */
161 private final List<Cell> cellsReferringToHeaders = new LinkedList<Cell>();
162
163 /**
164 * The owning checker.
165 */
166 private final TableChecker owner;
167
168 /**
169 * The current row group (also implicit groups have an explicit object).
170 */
171 private RowGroup current;
172
173 /**
174 * The head of the column range list.
175 */
176 private ColumnRange first = null;
177
178 /**
179 * The tail of the column range list.
180 */
181 private ColumnRange last = null;
182
183 /**
184 * The range under inspection.
185 */
186 private ColumnRange currentColRange = null;
187
188 /**
189 * The previous range that was inspected.
190 */
191 private ColumnRange previousColRange = null;
192
193 /**
194 * Constructor.
195 * @param owner reference back to the checker
196 */
197 public Table(TableChecker owner) {
198 super();
199 this.owner = owner;
200 }
201
202 private boolean needSuppressStart() {
203 if (suppressedStarts > 0) {
204 suppressedStarts++;
205 return true;
206 } else {
207 return false;
208 }
209 }
210
211 private boolean needSuppressEnd() {
212 if (suppressedStarts > 0) {
213 suppressedStarts--;
214 return true;
215 } else {
216 return false;
217 }
218 }
219
220 void startRowGroup(String type) throws SAXException {
221 if (needSuppressStart()) {
222 return;
223 }
224 switch (state) {
225 case IN_IMPLICIT_ROW_GROUP:
226 current.end();
227 // fall through
228 case IN_TABLE_AT_START:
229 case IN_TABLE_COLS_SEEN:
230 case IN_TABLE_AT_POTENTIAL_ROW_GROUP_START:
231 current = new RowGroup(this, type);
232 state = State.IN_ROW_GROUP;
233 break;
234 default:
235 suppressedStarts = 1;
236 break;
237 }
238 }
239
240 void endRowGroup() throws SAXException {
241 if (needSuppressEnd()) {
242 return;
243 }
244 switch (state) {
245 case IN_ROW_GROUP:
246 current.end();
247 current = null;
248 state = State.IN_TABLE_AT_POTENTIAL_ROW_GROUP_START;
249 break;
250 default:
251 throw new IllegalStateException("Bug!");
252 }
253 }
254
255 void startRow() {
256 if (needSuppressStart()) {
257 return;
258 }
259 switch (state) {
260 case IN_TABLE_AT_START:
261 case IN_TABLE_COLS_SEEN:
262 case IN_TABLE_AT_POTENTIAL_ROW_GROUP_START:
263 current = new RowGroup(this, null);
264 // fall through
265 case IN_IMPLICIT_ROW_GROUP:
266 state = State.IN_ROW_IN_IMPLICIT_ROW_GROUP;
267 break;
268 case IN_ROW_GROUP:
269 state = State.IN_ROW_IN_ROW_GROUP;
270 break;
271 default:
272 suppressedStarts = 1;
273 return;
274 }
275 currentColRange = first;
276 previousColRange = null;
277 current.startRow();
278 }
279
280 void endRow() throws SAXException {
281 if (needSuppressEnd()) {
282 return;
283 }
284 switch (state) {
285 case IN_ROW_IN_ROW_GROUP:
286 state = State.IN_ROW_GROUP;
287 break;
288 case IN_ROW_IN_IMPLICIT_ROW_GROUP:
289 state = State.IN_IMPLICIT_ROW_GROUP;
290 break;
291 default:
292 throw new IllegalStateException("Bug!");
293 }
294 current.endRow();
295 }
296
297 void startCell(boolean header, Attributes attributes) throws SAXException {
298 if (needSuppressStart()) {
299 return;
300 }
301 switch (state) {
302 case IN_ROW_IN_ROW_GROUP:
303 state = State.IN_CELL_IN_ROW_GROUP;
304 break;
305 case IN_ROW_IN_IMPLICIT_ROW_GROUP:
306 state = State.IN_CELL_IN_IMPLICIT_ROW_GROUP;
307 break;
308 default:
309 suppressedStarts = 1;
310 return;
311 }
312 if (header) {
313 int len = attributes.getLength();
314 for (int i = 0; i < len; i++) {
315 if ("ID".equals(attributes.getType(i))) {
316 String val = attributes.getValue(i);
317 if (!"".equals(val)) {
318 headerIds.add(val);
319 }
320 }
321 }
322 }
323 String[] headers = AttributeUtil.split(attributes.getValue("",
324 "headers"));
325 Cell cell = new Cell(
326 Math.abs(AttributeUtil.parsePositiveInteger(attributes.getValue(
327 "", "colspan"))),
328 Math.abs(AttributeUtil.parseNonNegativeInteger(attributes.getValue(
329 "", "rowspan"))), headers, header,
330 owner.getDocumentLocator(), owner.getErrorHandler());
331 if (headers.length > 0) {
332 cellsReferringToHeaders.add(cell);
333 }
334 current.cell(cell);
335 }
336
337 void endCell() {
338 if (needSuppressEnd()) {
339 return;
340 }
341 switch (state) {
342 case IN_CELL_IN_ROW_GROUP:
343 state = State.IN_ROW_IN_ROW_GROUP;
344 break;
345 case IN_CELL_IN_IMPLICIT_ROW_GROUP:
346 state = State.IN_ROW_IN_IMPLICIT_ROW_GROUP;
347 break;
348 default:
349 throw new IllegalStateException("Bug!");
350 }
351 }
352
353 void startColGroup(int span) {
354 if (needSuppressStart()) {
355 return;
356 }
357 switch (state) {
358 case IN_TABLE_AT_START:
359 hardWidth = true;
360 columnCount = 0;
361 // fall through
362 case IN_TABLE_COLS_SEEN:
363 pendingColGroupSpan = span;
364 state = State.IN_COLGROUP;
365 break;
366 default:
367 suppressedStarts = 1;
368 break;
369 }
370 }
371
372 void endColGroup() {
373 if (needSuppressEnd()) {
374 return;
375 }
376 switch (state) {
377 case IN_COLGROUP:
378 if (pendingColGroupSpan != 0) {
379 int right = columnCount + Math.abs(pendingColGroupSpan);
380 Locator locator = new LocatorImpl(
381 owner.getDocumentLocator());
382 ColumnRange colRange = new ColumnRange("colgroup", locator,
383 columnCount, right);
384 appendColumnRange(colRange);
385 columnCount = right;
386 }
387 realColumnCount = columnCount;
388 state = State.IN_TABLE_COLS_SEEN;
389 break;
390 default:
391 throw new IllegalStateException("Bug!");
392 }
393 }
394
395 void startCol(int span) throws SAXException {
396 if (needSuppressStart()) {
397 return;
398 }
399 switch (state) {
400 case IN_TABLE_AT_START:
401 hardWidth = true;
402 columnCount = 0;
403 // fall through
404 case IN_TABLE_COLS_SEEN:
405 state = State.IN_COL_IN_IMPLICIT_GROUP;
406 break;
407 case IN_COLGROUP:
408 if (pendingColGroupSpan > 0) {
409 warn("A col element causes a span attribute with value "
410 + pendingColGroupSpan
411 + " to be ignored on the parent colgroup.");
412 }
413 pendingColGroupSpan = 0;
414 state = State.IN_COL_IN_COLGROUP;
415 break;
416 default:
417 suppressedStarts = 1;
418 return;
419 }
420 int right = columnCount + Math.abs(span);
421 Locator locator = new LocatorImpl(owner.getDocumentLocator());
422 ColumnRange colRange = new ColumnRange("col", locator,
423 columnCount, right);
424 appendColumnRange(colRange);
425 columnCount = right;
426 realColumnCount = columnCount;
427 }
428
429 /**
430 * Appends a column range to the linked list of column ranges.
431 *
432 * @param colRange the range to append
433 */
434 private void appendColumnRange(ColumnRange colRange) {
435 if (last == null) {
436 first = colRange;
437 last = colRange;
438 } else {
439 last.setNext(colRange);
440 last = colRange;
441 }
442 }
443
444 void warn(String message) throws SAXException {
445 owner.warn(message);
446 }
447
448 void err(String message) throws SAXException {
449 owner.err(message);
450 }
451
452 void endCol() {
453 if (needSuppressEnd()) {
454 return;
455 }
456 switch (state) {
457 case IN_COL_IN_IMPLICIT_GROUP:
458 state = State.IN_TABLE_COLS_SEEN;
459 break;
460 case IN_COL_IN_COLGROUP:
461 state = State.IN_COLGROUP;
462 break;
463 default:
464 throw new IllegalStateException("Bug!");
465 }
466 }
467
468 void end() throws SAXException {
469 switch (state) {
470 case IN_IMPLICIT_ROW_GROUP:
471 current.end();
472 current = null;
473 break;
474 case IN_TABLE_AT_START:
475 case IN_TABLE_AT_POTENTIAL_ROW_GROUP_START:
476 case IN_TABLE_COLS_SEEN:
477 break;
478 default:
479 throw new IllegalStateException("Bug!");
480 }
481
482 // Check referential integrity
483 for (Iterator<Cell> iter = cellsReferringToHeaders.iterator(); iter.hasNext();) {
484 Cell cell = iter.next();
485 String[] headings = cell.getHeadings();
486 for (int i = 0; i < headings.length; i++) {
487 String heading = headings[i];
488 if (!headerIds.contains(heading)) {
489 cell.err("The \u201Cheaders\u201D attribute on the element \u201C"
490 + cell.elementName()
491 + "\u201D refers to the ID \u201C"
492 + heading
493 + "\u201D, but there is no \u201Cth\u201D element with that ID in the same table.");
494 }
495 }
496 }
497
498 // Check that each column has non-extended cells
499 ColumnRange colRange = first;
500 while (colRange != null) {
501 if (colRange.isSingleCol()) {
502 owner.getErrorHandler().error(
503 new SAXParseException("Table column " + colRange
504 + " established by element \u201C"
505 + colRange.getElement()
506 + "\u201D has no cells beginning in it.",
507 colRange.getLocator()));
508 } else {
509 owner.getErrorHandler().error(
510 new SAXParseException("Table columns in range "
511 + colRange + " established by element \u201C"
512 + colRange.getElement()
513 + "\u201D have no cells beginning in them.",
514 colRange.getLocator()));
515 }
516 colRange = colRange.getNext();
517 }
518 }
519
520 /**
521 * Returns the columnCount.
522 *
523 * @return the columnCount
524 */
525 int getColumnCount() {
526 return columnCount;
527 }
528
529 /**
530 * Sets the columnCount.
531 *
532 * @param columnCount
533 * the columnCount to set
534 */
535 void setColumnCount(int columnCount) {
536 this.columnCount = columnCount;
537 }
538
539 /**
540 * Returns the hardWidth.
541 *
542 * @return the hardWidth
543 */
544 boolean isHardWidth() {
545 return hardWidth;
546 }
547
548 /**
549 * Reports a cell whose positioning has been decided back to the table
550 * so that column bookkeeping can be done. (Called from
551 * <code>RowGroup</code>--not <code>TableChecker</code>.)
552 *
553 * @param cell a cell whose position has been calculated
554 */
555 void cell(Cell cell) {
556 int left = cell.getLeft();
557 int right = cell.getRight();
558 // first see if we've got a cell past the last col
559 if (right > realColumnCount) {
560 // are we past last col entirely?
561 if (left == realColumnCount) {
562 // single col?
563 if (left + 1 != right) {
564 appendColumnRange(new ColumnRange(cell.elementName(), cell, left + 1, right));
565 }
566 realColumnCount = right;
567 return;
568 } else {
569 // not past entirely
570 appendColumnRange(new ColumnRange(cell.elementName(), cell, realColumnCount, right));
571 realColumnCount = right;
572 }
573 }
574 while (currentColRange != null) {
575 int hit = currentColRange.hits(left);
576 if (hit == 0) {
577 ColumnRange newRange = currentColRange.removeColumn(left);
578 if (newRange == null) {
579 // zap a list item
580 if (previousColRange != null) {
581 previousColRange.setNext(currentColRange.getNext());
582 }
583 if (first == currentColRange) {
584 first = currentColRange.getNext();
585 }
586 if (last == currentColRange) {
587 last = previousColRange;
588 }
589 currentColRange = currentColRange.getNext();
590 } else {
591 if (last == currentColRange) {
592 last = newRange;
593 }
594 currentColRange = newRange;
595 }
596 return;
597 } else if (hit == -1) {
598 return;
599 } else if (hit == 1) {
600 previousColRange = currentColRange;
601 currentColRange = currentColRange.getNext();
602 }
603 }
604 }
605 }