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 fi.iki.hsivonen.xml.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.xml.sax.Attributes;
032 import org.xml.sax.Locator;
033 import org.xml.sax.SAXException;
034 import org.xml.sax.SAXParseException;
035 import org.xml.sax.helpers.LocatorImpl;
036
037 import fi.iki.hsivonen.xml.AttributeUtil;
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,v 1.7 2006/12/01 12:34:30 hsivonen Exp $
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 headerIds.add(attributes.getValue(i));
317 }
318 }
319 }
320 String[] headers = AttributeUtil.split(attributes.getValue("",
321 "headers"));
322 Cell cell = new Cell(
323 Math.abs(AttributeUtil.parsePositiveInteger(attributes.getValue(
324 "", "colspan"))),
325 Math.abs(AttributeUtil.parseNonNegativeInteger(attributes.getValue(
326 "", "rowspan"))), headers, header,
327 owner.getDocumentLocator(), owner.getErrorHandler());
328 if (headers.length > 0) {
329 cellsReferringToHeaders.add(cell);
330 }
331 current.cell(cell);
332 }
333
334 void endCell() {
335 if (needSuppressEnd()) {
336 return;
337 }
338 switch (state) {
339 case IN_CELL_IN_ROW_GROUP:
340 state = State.IN_ROW_IN_ROW_GROUP;
341 break;
342 case IN_CELL_IN_IMPLICIT_ROW_GROUP:
343 state = State.IN_ROW_IN_IMPLICIT_ROW_GROUP;
344 break;
345 default:
346 throw new IllegalStateException("Bug!");
347 }
348 }
349
350 void startColGroup(int span) {
351 if (needSuppressStart()) {
352 return;
353 }
354 switch (state) {
355 case IN_TABLE_AT_START:
356 hardWidth = true;
357 columnCount = 0;
358 // fall through
359 case IN_TABLE_COLS_SEEN:
360 pendingColGroupSpan = span;
361 state = State.IN_COLGROUP;
362 break;
363 default:
364 suppressedStarts = 1;
365 break;
366 }
367 }
368
369 void endColGroup() {
370 if (needSuppressEnd()) {
371 return;
372 }
373 switch (state) {
374 case IN_COLGROUP:
375 int right = columnCount + Math.abs(pendingColGroupSpan);
376 Locator locator = new LocatorImpl(owner.getDocumentLocator());
377 ColumnRange colRange = new ColumnRange("colgroup", locator,
378 columnCount, right);
379 appendColumnRange(colRange);
380 columnCount = right;
381 realColumnCount = columnCount;
382 state = State.IN_TABLE_COLS_SEEN;
383 break;
384 default:
385 throw new IllegalStateException("Bug!");
386 }
387 }
388
389 void startCol(int span) throws SAXException {
390 if (needSuppressStart()) {
391 return;
392 }
393 switch (state) {
394 case IN_TABLE_AT_START:
395 hardWidth = true;
396 columnCount = 0;
397 // fall through
398 case IN_TABLE_COLS_SEEN:
399 state = State.IN_COL_IN_IMPLICIT_GROUP;
400 break;
401 case IN_COLGROUP:
402 if (pendingColGroupSpan > 0) {
403 warn("A col element causes a span attribute with value "
404 + pendingColGroupSpan
405 + " to be ignored on the parent colgroup.");
406 }
407 pendingColGroupSpan = 0;
408 state = State.IN_COL_IN_COLGROUP;
409 break;
410 default:
411 suppressedStarts = 1;
412 return;
413 }
414 int right = columnCount + Math.abs(span);
415 Locator locator = new LocatorImpl(owner.getDocumentLocator());
416 ColumnRange colRange = new ColumnRange("col", locator,
417 columnCount, right);
418 appendColumnRange(colRange);
419 columnCount = right;
420 realColumnCount = columnCount;
421 }
422
423 /**
424 * Appends a column range to the linked list of column ranges.
425 *
426 * @param colRange the range to append
427 */
428 private void appendColumnRange(ColumnRange colRange) {
429 if (last == null) {
430 first = colRange;
431 last = colRange;
432 } else {
433 last.setNext(colRange);
434 last = colRange;
435 }
436 }
437
438 void warn(String message) throws SAXException {
439 owner.warn(message);
440 }
441
442 void err(String message) throws SAXException {
443 owner.err(message);
444 }
445
446 void endCol() {
447 if (needSuppressEnd()) {
448 return;
449 }
450 switch (state) {
451 case IN_COL_IN_IMPLICIT_GROUP:
452 state = State.IN_TABLE_COLS_SEEN;
453 break;
454 case IN_COL_IN_COLGROUP:
455 state = State.IN_COLGROUP;
456 break;
457 default:
458 throw new IllegalStateException("Bug!");
459 }
460 }
461
462 void end() throws SAXException {
463 switch (state) {
464 case IN_IMPLICIT_ROW_GROUP:
465 current.end();
466 current = null;
467 break;
468 case IN_TABLE_AT_START:
469 case IN_TABLE_AT_POTENTIAL_ROW_GROUP_START:
470 case IN_TABLE_COLS_SEEN:
471 break;
472 default:
473 throw new IllegalStateException("Bug!");
474 }
475
476 // Check referential integrity
477 for (Iterator<Cell> iter = cellsReferringToHeaders.iterator(); iter.hasNext();) {
478 Cell cell = iter.next();
479 String[] headings = cell.getHeadings();
480 for (int i = 0; i < headings.length; i++) {
481 String heading = headings[i];
482 if (!headerIds.contains(heading)) {
483 cell.err("The \u201Cheaders\u201D attribute on the element \u201C"
484 + cell.elementName()
485 + "\u201D refers to the ID \u201C"
486 + heading
487 + "\u201D, but there is no \u201Cth\u201D element with that ID in the same table.");
488 }
489 }
490 }
491
492 // Check that each column has non-extended cells
493 ColumnRange colRange = first;
494 while (colRange != null) {
495 if (colRange.isSingleCol()) {
496 owner.getErrorHandler().error(
497 new SAXParseException("Table column " + colRange
498 + " established by element \u201C"
499 + colRange.getElement()
500 + "\u201D has no cells beginning in it.",
501 colRange.getLocator()));
502 } else {
503 owner.getErrorHandler().error(
504 new SAXParseException("Table columns in range "
505 + colRange + " established by element \u201C"
506 + colRange.getElement()
507 + "\u201D have no cells beginning in them.",
508 colRange.getLocator()));
509 }
510 colRange = colRange.getNext();
511 }
512 }
513
514 /**
515 * Returns the columnCount.
516 *
517 * @return the columnCount
518 */
519 int getColumnCount() {
520 return columnCount;
521 }
522
523 /**
524 * Sets the columnCount.
525 *
526 * @param columnCount
527 * the columnCount to set
528 */
529 void setColumnCount(int columnCount) {
530 this.columnCount = columnCount;
531 }
532
533 /**
534 * Returns the hardWidth.
535 *
536 * @return the hardWidth
537 */
538 boolean isHardWidth() {
539 return hardWidth;
540 }
541
542 /**
543 * Reports a cell whose positioning has been decided back to the table
544 * so that column bookkeeping can be done. (Called from
545 * <code>RowGroup</code>--not <code>TableChecker</code>.)
546 *
547 * @param cell a cell whose position has been calculated
548 */
549 void cell(Cell cell) {
550 int left = cell.getLeft();
551 int right = cell.getRight();
552 // first see if we've got a cell past the last col
553 if (right > realColumnCount) {
554 // are we past last col entirely?
555 if (left == realColumnCount) {
556 // single col?
557 if (left + 1 != right) {
558 appendColumnRange(new ColumnRange(cell.elementName(), cell, left + 1, right));
559 }
560 realColumnCount = right;
561 return;
562 } else {
563 // not past entirely
564 appendColumnRange(new ColumnRange(cell.elementName(), cell, realColumnCount, right));
565 realColumnCount = right;
566 }
567 }
568 while (currentColRange != null) {
569 int hit = currentColRange.hits(left);
570 if (hit == 0) {
571 ColumnRange newRange = currentColRange.removeColumn(left);
572 if (newRange == null) {
573 // zap a list item
574 if (previousColRange != null) {
575 previousColRange.setNext(currentColRange.getNext());
576 }
577 if (first == currentColRange) {
578 first = currentColRange.getNext();
579 }
580 if (last == currentColRange) {
581 last = previousColRange;
582 }
583 currentColRange = currentColRange.getNext();
584 } else {
585 if (last == currentColRange) {
586 last = newRange;
587 }
588 currentColRange = newRange;
589 }
590 return;
591 } else if (hit == -1) {
592 return;
593 } else if (hit == 1) {
594 previousColRange = currentColRange;
595 currentColRange = currentColRange.getNext();
596 }
597 }
598 }
599 }