whatpm/Whatpm/HTMLTable.pm

package Whatpm::HTMLTable;
use strict;

## An implementation of "Forming a table" algorithm in HTML5
sub form_table ($$$;$) {
  my (undef, $table_el, $onerror, $must_level) = @_;
  $onerror ||= sub { };
  $must_level ||= 'm';
  
  ## Step 1
  my $x_width = 0;

  ## Step 2
  my $y_height = 0;
  my $y_max_node;

  ## Step 3
  my $pending_tfoot = [];
  
  ## Step 4
  my $table = {
    #caption
    column => [],
    column_group => [],
    row => [], ## NOTE: HTML5 algorithm doesn't associate rows with <tr>s.
    row_group => [],
    cell => [],
    height => 0,
    width => 0,
    element => $table_el,
  };
  
  my @column_has_anchored_cell;
  my @row_has_anchored_cell;
  my @column_generated_by;
  my @row_generated_by;
  
  ## Step 5
  my @table_child = @{$table_el->child_nodes};
  return $table unless @table_child;

  ## Step 6
  for (0..$#table_child) {
    my $el = $table_child[$_];
    next unless $el->node_type == 1; # ELEMENT_NODE
    next unless $el->manakai_local_name eq 'caption';
    my $nsuri = $el->namespace_uri;
    next unless defined $nsuri;
    next unless $nsuri eq q<http://www.w3.org/1999/xhtml>;
    $table->{caption} = {element => $el};
    splice @table_child, $_, 1, ();
    last;
  }

  my $process_row_group;
  my $end = sub {
    ## Step 19 (End)
    for (@$pending_tfoot) {
      $process_row_group->($_);
    }
    
    ## Step 20
    for (0 .. $x_width - 1) {
      unless ($column_has_anchored_cell[$_]) {
        if ($table->{column}->[$_]) {
          $onerror->(type => 'column with no anchored cell',
                     node => $table->{column}->[$_]->{element},
                     level => $must_level);
        } else {
          $onerror->(type => 'colspan creates column with no anchored cell',
                     node => $column_generated_by[$_],
                    level => $must_level);
        }
        last; # only one error.
      }
    }
    for (0 .. $y_height - 1) {
      unless ($row_has_anchored_cell[$_]) {
        if ($table->{row}->[$_]) {
          $onerror->(type => 'row with no anchored cell',
                     node => $table->{row}->[$_]->{element},
                     level => $must_level);
        } else {
          $onerror->(type => 'rowspan creates row with no anchored cell',
                     node => $row_generated_by[$_],
                     level => $must_level);
        }
        last; # only one error.
      }
    }
    
    ## Step 21
    #return $table;
  }; # $end

  ## Step 7, 8
  my $current_element;
  my $current_ln;
  NEXT_CHILD: {
    $current_element = shift @table_child;
    if (defined $current_element) {
      redo NEXT_CHILD unless $current_element->node_type == 1;
      my $nsuri = $current_element->namespace_uri;
      redo NEXT_CHILD unless defined $nsuri and
        $nsuri eq q<http://www.w3.org/1999/xhtml>;
      $current_ln = $current_element->manakai_local_name;

      redo NEXT_CHILD unless {
        colgroup => 1,
        thead => 1,
        tbody => 1,
        tfoot => 1,
        tr => 1,
      }->{$current_ln};
    } else {
      ## Step 6 2nd paragraph
      $end->();
      $table->{width} = $x_width;
      $table->{height} = $y_height;
      return $table;
    }
  } # NEXT_CHILD

  ## Step 9
  while ($current_ln eq 'colgroup') { # Step 9, Step 9.4
    ## Step 9.1: column groups
    my @col = grep {
      $_->node_type == 1 and
      defined $_->namespace_uri and
      $_->namespace_uri eq q<http://www.w3.org/1999/xhtml> and
      $_->manakai_local_name eq 'col'
    } @{$current_element->child_nodes};
    if (@col) {
      ## Step 1
      my $x_start = $x_width;
      
      ## Step 2, 6
      while (@col) {
        my $current_column = shift @col;
        
        ## Step 3: columns
        my $span = 1;
        my $col_span = $current_column->get_attribute_ns (undef, 'span');
        ## Parse non-negative integer
        if (defined $col_span and $col_span =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
          $span = $1 || 1;
        }
        
        ## Step 4, 5
        $table->{column}->[$x_width++] = {element => $current_column}
            for 1..$span;
      }
      
      ## Step 7
      my $cg = {element => $current_element,
                x => $x_start, y => 0,
                width => $x_width - $x_start};
      $table->{column_group}->[$_] = $cg for $x_start .. $x_width - 1;
    } else { # no <col> children
      ## Step 1
      my $span = 1;
      my $col_span = $current_element->get_attribute_ns (undef, 'span');
      ## Parse non-negative integer
      if (defined $col_span and $col_span =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
        $span = $1 || 1;
      }
      
      ## Step 2
      $x_width += $span;
      
      ## Step 3
      my $cg = {element => $current_element,
                x => $x_width - $span, y => 0,
                width => $span};
      $table->{column_group}->[$_] = $cg for $cg->{x} .. $x_width - 1;
    }
    
    ## Step 9.2, 9.3
    NEXT_CHILD: {
      $current_element = shift @table_child;
      if (defined $current_element) {
        redo NEXT_CHILD unless $current_element->node_type == 1;
        my $nsuri = $current_element->namespace_uri;
        redo NEXT_CHILD unless defined $nsuri and
          $nsuri eq q<http://www.w3.org/1999/xhtml>;
        $current_ln = $current_element->manakai_local_name;
        
        redo NEXT_CHILD unless {
          colgroup => 1,
          thead => 1,
          tbody => 1,
          tfoot => 1,
          tr => 1,
        }->{$current_ln};
      } else {
        ## End of subsection
        
        ## Step 5 of overall steps 2nd paragraph
        $end->();
        $table->{width} = $x_width;
        $table->{height} = $y_height;
        return $table;
      }
    } # NEXT_CHILD
  }

  ## Step 10
  my $y_current = 0;

  ## Step 11
  my @downward_growing_cells;

  my $growing_downward_growing_cells = sub {
    for (@downward_growing_cells) {
      for my $x ($_->[1] .. ($_->[1] + $_->[2] - 1)) {
        $table->{cell}->[$x]->[$y_current] = [$_->[0]];
        $_->[0]->{height}++;
      }
    }
  }; # $growing_downward_growing_cells

  my $process_row = sub {
    ## Step 1
    $y_height++ if $y_height == $y_current;
    
    ## Step 2
    my $x_current = 0;

    ## Step 3
    my $tr = shift;
    $table->{row}->[$y_current] = {element => $tr};
    my @tdth = grep {
      $_->node_type == 1 and
      defined $_->namespace_uri and
      $_->namespace_uri eq q<http://www.w3.org/1999/xhtml> and
      {td => 1, th => 1}->{$_->manakai_local_name}
    } @{$tr->child_nodes};
    my $current_cell = shift @tdth;

    ## Step 4
    $growing_downward_growing_cells->();

return unless $current_cell;
## ISSUE: Support for empty <tr></tr> (removed at revision 1376).

    CELL: while (1) {
      ## Step 5: cells
      $x_current++
        while ($x_current < $x_width and
               $table->{cell}->[$x_current]->[$y_current]);

      ## Step 6
      $x_width++ if $x_current == $x_width;

      ## Step 7
      my $colspan = 1;
      my $attr_value = $current_cell->get_attribute_ns (undef, 'colspan');
      if (defined $attr_value and $attr_value =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
        $colspan = $1 || 1;
      }
      
      ## Step 8
      my $rowspan = 1;
      my $attr_value = $current_cell->get_attribute_ns (undef, 'rowspan');
      if (defined $attr_value and $attr_value =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
        $rowspan = $1;
      }
      
      ## Step 9
      my $cell_grows_downward;
      if ($rowspan == 0) {
        $cell_grows_downward = 1;
        $rowspan = 1;
      }
      
      ## Step 10
      if ($x_width < $x_current + $colspan) { 
        @column_generated_by[$_] = $current_cell
          for $x_width .. $x_current + $colspan - 1;
        $x_width = $x_current + $colspan;
      }
      
      ## Step 11
      if ($y_height < $y_current + $rowspan) {
        @row_generated_by[$_] = $current_cell
            for $y_height .. $y_current + $rowspan - 1;
        $y_height = $y_current + $rowspan;
        $y_max_node = $current_cell;
      }
      
      ## Step 12
      my $cell = {
                  is_header => ($current_cell->manakai_local_name eq 'th'),
                  element => $current_cell,
                  x => $x_current, y => $y_current,
                  width => $colspan, height => $rowspan,
                 };
      $column_has_anchored_cell[$x_current] = 1;
      $row_has_anchored_cell[$y_current] = 1;
      for my $x ($x_current .. ($x_current + $colspan - 1)) {
        for my $y ($y_current .. ($y_current + $rowspan - 1)) {
          unless ($table->{cell}->[$x]->[$y]) {
            $table->{cell}->[$x]->[$y] = [$cell];
          } else {
            $onerror->(type => "cell overlapping:$x:$y", node => $current_cell,
                       level => $must_level);
            push @{$table->{cell}->[$x]->[$y]}, $cell;
          }
        }
      }

      ## Whether the cell is an empty data cell or not
      if (not $cell->{is_header}) {
        $cell->{is_empty} = 1;
        for my $node (@{$current_cell->child_nodes}) {
          my $nt = $node->node_type;
          if ($nt == 3 or $nt == 4) { # TEXT_NODE / CDATA_SECTION_NODE
            if ($node->data =~ /\P{Zs}/) { ## TOOD: non-Zs class
              delete $cell->{is_empty};
              last;
            }
          } elsif ($nt == 1) { # ELEMENT_NODE
            delete $cell->{is_empty};
            last;
          }
        }
        ## NOTE: Entity references are not supported
      }
      
      ## Step 13
      if ($cell_grows_downward) {
        push @downward_growing_cells, [$cell, $x_current, $colspan];
      }
      
      ## Step 14
      $x_current += $colspan;

      ## Step 15-17
      $current_cell = shift @tdth;
      if (defined $current_cell) {
        ## Step 16-17
        #
      } else {
        ## Step 15
        $y_current++;
        last CELL;
      }
    } # CELL
  }; # $process_row

  $process_row_group = sub ($) {
    ## Step 1
    my $y_start = $y_height;

    ## Step 2
    for (grep {
      $_->node_type == 1 and
      defined $_->namespace_uri and
      $_->namespace_uri eq q<http://www.w3.org/1999/xhtml> and
      $_->manakai_local_name eq 'tr'
    } @{$_[0]->child_nodes}) {
      $process_row->($_);
    }

    ## Step 3
    if ($y_height > $y_start) {
      my $rg = {element => $current_element, ## ISSUE: "element being processed"?  Otherwise, $current_element may be a thead element while the element being processed is a tfoot element, for example.
                x => 0, y => $y_start,
                height => $y_height - $y_start};
      $table->{row_group}->[$_] = $rg for $y_start .. $y_height - 1;
    }

    ## Step 4
    ## Ending a row group
      ## Step 1
      while ($y_current < $y_height) {
        ## Step 1
        $growing_downward_growing_cells->();

        ## Step 2
        $y_current++;
      }
      ## Step 2
      @downward_growing_cells = ();
  }; # $process_row_group

  ## Step 12: rows
  unshift @table_child, $current_element;
  ROWS: {
    NEXT_CHILD: {
      $current_element = shift @table_child;
      if (defined $current_element) {
        redo NEXT_CHILD unless $current_element->node_type == 1;
        my $nsuri = $current_element->namespace_uri;
        redo NEXT_CHILD unless defined $nsuri and
          $nsuri eq q<http://www.w3.org/1999/xhtml>;
        $current_ln = $current_element->manakai_local_name;
      
        redo NEXT_CHILD unless {
          thead => 1,
          tbody => 1,
          tfoot => 1,
          tr => 1,
        }->{$current_ln};
      } else {
        ## Step 6 2nd paragraph
        $end->();
        $table->{width} = $x_width;
        $table->{height} = $y_height;
        return $table;
      }
    } # NEXT_CHILD

    ## Step 13
    if ($current_ln eq 'tr') {
      $process_row->($current_element);
      # advance (done at the first of ROWS)
      redo ROWS;
    }

    ## Step 14
    ## Ending a row group
      ## Step 1
      while ($y_current < $y_height) {
        ## Step 1
        $growing_downward_growing_cells->();

        ## Step 2
        $y_current++;
      }
      ## Step 2
      @downward_growing_cells = ();

    ## Step 15
    if ($current_ln eq 'tfoot') {
      push @$pending_tfoot, $current_element;
      # advance (done at the top of ROWS)
      redo ROWS;
    }

    ## Step 16
    # thead or tbody
    $process_row_group->($current_element);

    ## Step 17
    # Advance (done at the top of ROWS).

    ## Step 18
    redo ROWS;
  } # ROWS

  $end->();
  $table->{width} = $x_width;
  $table->{height} = $y_height;
  return $table;
} # form_table

sub assign_header ($$;$$) {
  my (undef, $table, $onerror, $must_level) = @_;
  $onerror ||= sub { };
  $must_level ||= 'm';

  my $assign_header = sub ($$$) {
    my $_cell = shift;
    my ($x, $y) = @_;

    for my $__cell (@{$_cell or []}) {
      if ($__cell and $__cell->{element} and
          not $__cell->{is_header} and
          not $__cell->{element}->has_attribute_ns (undef, 'headers')) {
        $__cell->{header}->{$x}->{$y} = 1;
      }
    }
  }; # $assign_header

  my @headers_cell;
  my $id_to_cell = {};
  ## ISSUE: ID duplication, non-TH reference

  for my $x (0 .. $table->{width} - 1) {
    for my $y (0 .. $table->{height} - 1) {
      my $cell = $table->{cell}->[$x]->[$y];
      $cell = $cell->[0] if $cell; # anchored cell is always ->{cell}[][][0].
      next if $cell->{x} != $x;
      next if $cell->{y} != $y;
      if ($cell) {
        if ($cell->{is_header}) {
          my $id = $cell->{element}->get_attribute_ns (undef, 'id');
          if (defined $id and not $id_to_cell->{$id}) {
            $id_to_cell->{$id} = $cell;
          }

          my $scope = $cell->{element}->get_attribute_ns (undef, 'scope');
          $scope = $scope ? lc $scope : ''; ## TODO: case
          if ($scope eq 'row') {
            for my $_x ($x + $cell->{width} .. $table->{width} - 1) {
              for my $_y ($y .. $y + $cell->{height} - 1) {
                $assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
              }
            }
          } elsif ($scope eq 'col') {
            for my $_x ($x .. $x + $cell->{width} - 1) {
              for my $_y ($y .. $table->{height} - 1) {
                $assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
              }
            }
          } elsif ($scope eq 'rowgroup') {
            ## NOTE: A cell cannot exceed across a row group boundary.
            if ($table->{row_group}->[$y] and
                $table->{row_group}->[$y]->{height}) {
              for my $_x ($x .. $table->{width} - 1) {
                for my $_y ($y ..
                            $table->{row_group}->[$y]->{y} +
                            $table->{row_group}->[$y]->{height} - 1) {
                  $assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
                }
              }
            }
            ## TODO: Should we raise a warning?
          } elsif ($scope eq 'colgroup') {
            if ($table->{column_group}->[$x] and
                $table->{column_group}->{width} and
                $table->{column_group}->[$x]->{x} == $x) { # anchored
              for my $_x ($x .. 
                          $table->{column_group}->[$x]->{x} + 
                          $table->{column_group}->[$x]->{width} - 1) {
                for my $_y ($y .. $table->{height} - 1) {
                  $assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
                }
              }
            }
            ## TODO: Warning?
          } else { # auto
            ## 1.
            my $header_width = $cell->{width};
            W: for ($x + $cell->{width} .. $table->{width} - 1) {
              my $_cell = $table->{cell}->[$_]->[$y];
              for (@{$_cell or []}) {
                if ($_->{element} and not $_->{is_empty}) {
                  last W; # not empty
                }
              }
              $header_width++;
            } # W

            ## 2.
            my $_x = $x + $header_width;

            ## 3.
            HORIZONTAL: {
              last HORIZONTAL if $_x == $table->{width}; # goto Vertical

              ## 4. # goto Vertical
              last HORIZONTAL
                  if $table->{cell}->[$_x]->[$y] and
                      $table->{cell}->[$_x]->[$y]->[0] and # anchored
                      $table->{cell}->[$_x]->[$y]->[0]->{is_header};

              ## 5.
              for my $_y ($y .. $y + $cell->{height} - 1) {
                $assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
              }

              ## 6.
              $_x++;

              ## 7.
              redo HORIZONTAL;
            } # HORIZONTAL

            ## 8. Vertical
            my $_y = $y + $cell->{height};

            VERTICAL: {
              ## 9. # goto END
              last VERTICAL if $_y == $table->{height};

              ## 10.
              if ($table->{cell}->[$x]->[$_y]) {
                my $h_cell = $table->{cell}->[$x]->[$_y]->[0]; # anchored cell
                if ($h_cell and $h_cell->{is_header}) {
                  ## 10.1.
                  my $width = $h_cell->{width};
                  W: for ($h_cell->{x} + $width .. $table->{width} - 1) {
                    my $_cell = $table->{cell}->[$_]->[$y];
                    for (@{$_cell or []}) {
                      if ($_->{element} and not $_->{is_empty}) {
                        last W; # not empty
                      }
                    }
                    $width++;
                  } # W
                    
                  ## 10.2. # goto end
                  last VERTICAL if $width == $header_width;
                } # 10.
              }

              ## 11.
              for my $_x ($x .. $x + $header_width - 1) {
                $assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
              }

              ## 12.
              $_y++;

              ## 13. # goto vertical (wrong)
              redo VERTICAL;
            } # VERTICAL

            ## 14. End
            # (we have already done)
          }
        } else { # data cell
          if ($cell->{element} and
              $cell->{element}->has_attribute_ns (undef, 'headers')) {
            push @headers_cell, $cell;
          }
        }
      }
    }
  }

  for my $headers_cell (@headers_cell) {
    my @headers = split /[\x09-\x0D\x20]+/,
        $headers_cell->{element}->get_attribute_ns (undef, 'headers');
    my %headers;
    for my $header_id (@headers) {
      next unless length $header_id;
      if ($headers{$header_id}) {
        $onerror->(type => 'duplicate token', value => $header_id,
                   node => $headers_cell->{element}->get_attribute_node_ns
                       (undef, 'headers'),
                   level => $must_level);
        next;
      }
      $headers{$header_id} = 1;

      if ($id_to_cell->{$header_id}) {
        my $header_cell = $id_to_cell->{$header_id};
        $headers_cell->{header}->{$header_cell->{x}}->{$header_cell->{y}} = 1;
      } else {
        $onerror->(type => 'no header cell', value => $header_id,
                   node => $headers_cell->{element}->get_attribute_node_ns
                       (undef, 'headers'),
                   level => $must_level);
      }
    }
  }

  ## NOTE: The "tree order" constraints in the spec algorithm are irrelevant
  ## in fact.

  ## NOTE: We does not support ID attributes other than HTML "id" attribute.
} # assign_header

1;
## $Date: 2008/05/10 10:06:49 $
1	wakaba	1.1	package Whatpm::HTMLTable;
2			use strict;
3
4			## An implementation of "Forming a table" algorithm in HTML5
5	wakaba	1.9	sub form_table ($$$;$) {
6			my (undef, $table_el, $onerror, $must_level) = @_;
7	wakaba	1.2	$onerror \|\|= sub { };
8	wakaba	1.9	$must_level \|\|= 'm';
9	wakaba	1.1
10			## Step 1
11	wakaba	1.7	my $x_width = 0;
12	wakaba	1.1
13			## Step 2
14	wakaba	1.7	my $y_height = 0;
15	wakaba	1.1	my $y_max_node;
16	wakaba	1.8
17			## Step 3
18			my $pending_tfoot = [];
19	wakaba	1.1
20	wakaba	1.8	## Step 4
21	wakaba	1.1	my $table = {
22			#caption
23			column => [],
24			column_group => [],
25	wakaba	1.9	row => [], ## NOTE: HTML5 algorithm doesn't associate rows with <tr>s.
26	wakaba	1.1	row_group => [],
27			cell => [],
28	wakaba	1.11	height => 0,
29			width => 0,
30	wakaba	1.12	element => $table_el,
31	wakaba	1.1	};
32
33	wakaba	1.9	my @column_has_anchored_cell;
34			my @row_has_anchored_cell;
35	wakaba	1.1	my @column_generated_by;
36	wakaba	1.9	my @row_generated_by;
37
38			## Step 5
39			my @table_child = @{$table_el->child_nodes};
40			return $table unless @table_child;
41
42	wakaba	1.10	## Step 6
43			for (0..$#table_child) {
44			my $el = $table_child[$_];
45			next unless $el->node_type == 1; # ELEMENT_NODE
46			next unless $el->manakai_local_name eq 'caption';
47			my $nsuri = $el->namespace_uri;
48			next unless defined $nsuri;
49			next unless $nsuri eq q<http://www.w3.org/1999/xhtml>;
50			$table->{caption} = {element => $el};
51			splice @table_child, $_, 1, ();
52			last;
53			}
54
55	wakaba	1.9	my $process_row_group;
56			my $end = sub {
57	wakaba	1.10	## Step 19 (End)
58	wakaba	1.9	for (@$pending_tfoot) {
59			$process_row_group->($_);
60			}
61
62	wakaba	1.10	## Step 20
63	wakaba	1.7	for (0 .. $x_width - 1) {
64	wakaba	1.9	unless ($column_has_anchored_cell[$_]) {
65	wakaba	1.1	if ($table->{column}->[$_]) {
66			$onerror->(type => 'column with no anchored cell',
67	wakaba	1.9	node => $table->{column}->[$_]->{element},
68			level => $must_level);
69	wakaba	1.1	} else {
70	wakaba	1.4	$onerror->(type => 'colspan creates column with no anchored cell',
71	wakaba	1.9	node => $column_generated_by[$_],
72			level => $must_level);
73	wakaba	1.1	}
74	wakaba	1.9	last; # only one error.
75	wakaba	1.1	}
76			}
77	wakaba	1.9	for (0 .. $y_height - 1) {
78			unless ($row_has_anchored_cell[$_]) {
79			if ($table->{row}->[$_]) {
80			$onerror->(type => 'row with no anchored cell',
81			node => $table->{row}->[$_]->{element},
82			level => $must_level);
83			} else {
84			$onerror->(type => 'rowspan creates row with no anchored cell',
85			node => $row_generated_by[$_],
86			level => $must_level);
87			}
88			last; # only one error.
89			}
90			}
91
92	wakaba	1.10	## Step 21
93	wakaba	1.9	#return $table;
94			}; # $end
95	wakaba	1.1
96	wakaba	1.10	## Step 7, 8
97	wakaba	1.1	my $current_element;
98			my $current_ln;
99			NEXT_CHILD: {
100			$current_element = shift @table_child;
101			if (defined $current_element) {
102			redo NEXT_CHILD unless $current_element->node_type == 1;
103			my $nsuri = $current_element->namespace_uri;
104			redo NEXT_CHILD unless defined $nsuri and
105			$nsuri eq q<http://www.w3.org/1999/xhtml>;
106			$current_ln = $current_element->manakai_local_name;
107
108			redo NEXT_CHILD unless {
109			colgroup => 1,
110			thead => 1,
111			tbody => 1,
112			tfoot => 1,
113			tr => 1,
114			}->{$current_ln};
115			} else {
116	wakaba	1.8	## Step 6 2nd paragraph
117	wakaba	1.9	$end->();
118	wakaba	1.11	$table->{width} = $x_width;
119			$table->{height} = $y_height;
120	wakaba	1.9	return $table;
121	wakaba	1.1	}
122			} # NEXT_CHILD
123
124	wakaba	1.10	## Step 9
125			while ($current_ln eq 'colgroup') { # Step 9, Step 9.4
126			## Step 9.1: column groups
127	wakaba	1.1	my @col = grep {
128			$_->node_type == 1 and
129			defined $_->namespace_uri and
130			$_->namespace_uri eq q<http://www.w3.org/1999/xhtml> and
131			$_->manakai_local_name eq 'col'
132			} @{$current_element->child_nodes};
133			if (@col) {
134			## Step 1
135	wakaba	1.7	my $x_start = $x_width;
136	wakaba	1.1
137			## Step 2, 6
138			while (@col) {
139			my $current_column = shift @col;
140
141			## Step 3: columns
142			my $span = 1;
143			my $col_span = $current_column->get_attribute_ns (undef, 'span');
144			## Parse non-negative integer
145			if (defined $col_span and $col_span =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
146			$span = $1 \|\| 1;
147			}
148
149			## Step 4, 5
150	wakaba	1.11	$table->{column}->[$x_width++] = {element => $current_column}
151	wakaba	1.7	for 1..$span;
152	wakaba	1.1	}
153
154			## Step 7
155			my $cg = {element => $current_element,
156	wakaba	1.7	x => $x_start, y => 0,
157			width => $x_width - $x_start};
158			$table->{column_group}->[$_] = $cg for $x_start .. $x_width - 1;
159	wakaba	1.1	} else { # no <col> children
160			## Step 1
161			my $span = 1;
162			my $col_span = $current_element->get_attribute_ns (undef, 'span');
163			## Parse non-negative integer
164			if (defined $col_span and $col_span =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
165			$span = $1 \|\| 1;
166			}
167
168			## Step 2
169	wakaba	1.7	$x_width += $span;
170	wakaba	1.1
171			## Step 3
172			my $cg = {element => $current_element,
173	wakaba	1.7	x => $x_width - $span, y => 0,
174	wakaba	1.1	width => $span};
175	wakaba	1.7	$table->{column_group}->[$_] = $cg for $cg->{x} .. $x_width - 1;
176	wakaba	1.1	}
177
178	wakaba	1.10	## Step 9.2, 9.3
179	wakaba	1.1	NEXT_CHILD: {
180			$current_element = shift @table_child;
181			if (defined $current_element) {
182			redo NEXT_CHILD unless $current_element->node_type == 1;
183			my $nsuri = $current_element->namespace_uri;
184			redo NEXT_CHILD unless defined $nsuri and
185			$nsuri eq q<http://www.w3.org/1999/xhtml>;
186			$current_ln = $current_element->manakai_local_name;
187
188			redo NEXT_CHILD unless {
189			colgroup => 1,
190			thead => 1,
191			tbody => 1,
192			tfoot => 1,
193			tr => 1,
194			}->{$current_ln};
195			} else {
196			## End of subsection
197	wakaba	1.9
198	wakaba	1.1	## Step 5 of overall steps 2nd paragraph
199	wakaba	1.9	$end->();
200	wakaba	1.11	$table->{width} = $x_width;
201			$table->{height} = $y_height;
202	wakaba	1.9	return $table;
203	wakaba	1.1	}
204			} # NEXT_CHILD
205			}
206
207	wakaba	1.10	## Step 10
208	wakaba	1.1	my $y_current = 0;
209
210	wakaba	1.10	## Step 11
211	wakaba	1.1	my @downward_growing_cells;
212
213			my $growing_downward_growing_cells = sub {
214			for (@downward_growing_cells) {
215			for my $x ($_->[1] .. ($_->[1] + $_->[2] - 1)) {
216			$table->{cell}->[$x]->[$y_current] = [$_->[0]];
217			$_->[0]->{height}++;
218			}
219			}
220			}; # $growing_downward_growing_cells
221
222			my $process_row = sub {
223			## Step 1
224	wakaba	1.7	$y_height++ if $y_height == $y_current;
225	wakaba	1.1
226			## Step 2
227	wakaba	1.7	my $x_current = 0;
228
229	wakaba	1.1	## Step 3
230			my $tr = shift;
231	wakaba	1.9	$table->{row}->[$y_current] = {element => $tr};
232	wakaba	1.1	my @tdth = grep {
233			$_->node_type == 1 and
234			defined $_->namespace_uri and
235			$_->namespace_uri eq q<http://www.w3.org/1999/xhtml> and
236			{td => 1, th => 1}->{$_->manakai_local_name}
237			} @{$tr->child_nodes};
238	wakaba	1.7	my $current_cell = shift @tdth;
239
240			## Step 4
241			$growing_downward_growing_cells->();
242	wakaba	1.1
243	wakaba	1.9	return unless $current_cell;
244			## ISSUE: Support for empty <tr></tr> (removed at revision 1376).
245
246	wakaba	1.7	CELL: while (1) {
247			## Step 5: cells
248	wakaba	1.1	$x_current++
249	wakaba	1.7	while ($x_current < $x_width and
250	wakaba	1.1	$table->{cell}->[$x_current]->[$y_current]);
251
252	wakaba	1.7	## Step 6
253			$x_width++ if $x_current == $x_width;
254
255	wakaba	1.1	## Step 7
256			my $colspan = 1;
257			my $attr_value = $current_cell->get_attribute_ns (undef, 'colspan');
258			if (defined $attr_value and $attr_value =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
259			$colspan = $1 \|\| 1;
260			}
261
262	wakaba	1.7	## Step 8
263	wakaba	1.1	my $rowspan = 1;
264			my $attr_value = $current_cell->get_attribute_ns (undef, 'rowspan');
265			if (defined $attr_value and $attr_value =~ /^[\x09-\x0D\x20]*([0-9]+)/) {
266			$rowspan = $1;
267			}
268
269	wakaba	1.7	## Step 9
270	wakaba	1.1	my $cell_grows_downward;
271			if ($rowspan == 0) {
272			$cell_grows_downward = 1;
273			$rowspan = 1;
274			}
275
276	wakaba	1.7	## Step 10
277			if ($x_width < $x_current + $colspan) {
278	wakaba	1.1	@column_generated_by[$_] = $current_cell
279	wakaba	1.7	for $x_width .. $x_current + $colspan - 1;
280			$x_width = $x_current + $colspan;
281	wakaba	1.1	}
282
283	wakaba	1.7	## Step 11
284			if ($y_height < $y_current + $rowspan) {
285	wakaba	1.9	@row_generated_by[$_] = $current_cell
286			for $y_height .. $y_current + $rowspan - 1;
287	wakaba	1.7	$y_height = $y_current + $rowspan;
288	wakaba	1.1	$y_max_node = $current_cell;
289			}
290
291	wakaba	1.7	## Step 12
292	wakaba	1.1	my $cell = {
293	wakaba	1.2	is_header => ($current_cell->manakai_local_name eq 'th'),
294	wakaba	1.1	element => $current_cell,
295			x => $x_current, y => $y_current,
296			width => $colspan, height => $rowspan,
297			};
298	wakaba	1.9	$column_has_anchored_cell[$x_current] = 1;
299			$row_has_anchored_cell[$y_current] = 1;
300	wakaba	1.1	for my $x ($x_current .. ($x_current + $colspan - 1)) {
301			for my $y ($y_current .. ($y_current + $rowspan - 1)) {
302			unless ($table->{cell}->[$x]->[$y]) {
303			$table->{cell}->[$x]->[$y] = [$cell];
304			} else {
305	wakaba	1.9	$onerror->(type => "cell overlapping:$x:$y", node => $current_cell,
306			level => $must_level);
307	wakaba	1.1	push @{$table->{cell}->[$x]->[$y]}, $cell;
308			}
309			}
310			}
311	wakaba	1.11
312			## Whether the cell is an empty data cell or not
313			if (not $cell->{is_header}) {
314			$cell->{is_empty} = 1;
315			for my $node (@{$current_cell->child_nodes}) {
316			my $nt = $node->node_type;
317			if ($nt == 3 or $nt == 4) { # TEXT_NODE / CDATA_SECTION_NODE
318			if ($node->data =~ /\P{Zs}/) { ## TOOD: non-Zs class
319			delete $cell->{is_empty};
320			last;
321			}
322			} elsif ($nt == 1) { # ELEMENT_NODE
323			delete $cell->{is_empty};
324			last;
325			}
326			}
327			## NOTE: Entity references are not supported
328			}
329	wakaba	1.1
330	wakaba	1.7	## Step 13
331	wakaba	1.1	if ($cell_grows_downward) {
332			push @downward_growing_cells, [$cell, $x_current, $colspan];
333			}
334
335	wakaba	1.7	## Step 14
336	wakaba	1.1	$x_current += $colspan;
337	wakaba	1.7
338			## Step 15-17
339			$current_cell = shift @tdth;
340			if (defined $current_cell) {
341			## Step 16-17
342			#
343			} else {
344			## Step 15
345			$y_current++;
346			last CELL;
347			}
348			} # CELL
349	wakaba	1.1	}; # $process_row
350
351	wakaba	1.9	$process_row_group = sub ($) {
352	wakaba	1.8	## Step 1
353			my $y_start = $y_height;
354
355			## Step 2
356			for (grep {
357			$_->node_type == 1 and
358			defined $_->namespace_uri and
359			$_->namespace_uri eq q<http://www.w3.org/1999/xhtml> and
360			$_->manakai_local_name eq 'tr'
361			} @{$_[0]->child_nodes}) {
362			$process_row->($_);
363			}
364
365			## Step 3
366			if ($y_height > $y_start) {
367	wakaba	1.14	my $rg = {element => $current_element, ## ISSUE: "element being processed"? Otherwise, $current_element may be a thead element while the element being processed is a tfoot element, for example.
368	wakaba	1.8	x => 0, y => $y_start,
369			height => $y_height - $y_start};
370			$table->{row_group}->[$_] = $rg for $y_start .. $y_height - 1;
371			}
372
373			## Step 4
374			## Ending a row group
375			## Step 1
376			while ($y_current < $y_height) {
377			## Step 1
378			$growing_downward_growing_cells->();
379
380			## Step 2
381			$y_current++;
382			}
383	wakaba	1.9	## Step 2
384	wakaba	1.8	@downward_growing_cells = ();
385			}; # $process_row_group
386
387	wakaba	1.10	## Step 12: rows
388	wakaba	1.1	unshift @table_child, $current_element;
389			ROWS: {
390			NEXT_CHILD: {
391			$current_element = shift @table_child;
392			if (defined $current_element) {
393			redo NEXT_CHILD unless $current_element->node_type == 1;
394			my $nsuri = $current_element->namespace_uri;
395			redo NEXT_CHILD unless defined $nsuri and
396			$nsuri eq q<http://www.w3.org/1999/xhtml>;
397			$current_ln = $current_element->manakai_local_name;
398
399			redo NEXT_CHILD unless {
400			thead => 1,
401			tbody => 1,
402			tfoot => 1,
403			tr => 1,
404			}->{$current_ln};
405			} else {
406	wakaba	1.8	## Step 6 2nd paragraph
407	wakaba	1.9	$end->();
408	wakaba	1.11	$table->{width} = $x_width;
409			$table->{height} = $y_height;
410	wakaba	1.9	return $table;
411	wakaba	1.1	}
412			} # NEXT_CHILD
413
414	wakaba	1.10	## Step 13
415	wakaba	1.1	if ($current_ln eq 'tr') {
416			$process_row->($current_element);
417	wakaba	1.8	# advance (done at the first of ROWS)
418	wakaba	1.1	redo ROWS;
419			}
420
421	wakaba	1.10	## Step 14
422	wakaba	1.1	## Ending a row group
423			## Step 1
424	wakaba	1.7	while ($y_current < $y_height) {
425	wakaba	1.1	## Step 1
426	wakaba	1.9	$growing_downward_growing_cells->();
427
428			## Step 2
429	wakaba	1.1	$y_current++;
430			}
431	wakaba	1.9	## Step 2
432	wakaba	1.1	@downward_growing_cells = ();
433
434	wakaba	1.10	## Step 15
435	wakaba	1.8	if ($current_ln eq 'tfoot') {
436			push @$pending_tfoot, $current_element;
437			# advance (done at the top of ROWS)
438			redo ROWS;
439	wakaba	1.1	}
440
441	wakaba	1.10	## Step 16
442	wakaba	1.8	# thead or tbody
443			$process_row_group->($current_element);
444	wakaba	1.1
445	wakaba	1.10	## Step 17
446	wakaba	1.8	# Advance (done at the top of ROWS).
447	wakaba	1.1
448	wakaba	1.10	## Step 18
449	wakaba	1.8	redo ROWS;
450	wakaba	1.1	} # ROWS
451	wakaba	1.8
452	wakaba	1.9	$end->();
453	wakaba	1.11	$table->{width} = $x_width;
454			$table->{height} = $y_height;
455	wakaba	1.8	return $table;
456	wakaba	1.1	} # form_table
457
458	wakaba	1.11	sub assign_header ($$;$$) {
459			my (undef, $table, $onerror, $must_level) = @_;
460			$onerror \|\|= sub { };
461			$must_level \|\|= 'm';
462
463			my $assign_header = sub ($$$) {
464			my $_cell = shift;
465			my ($x, $y) = @_;
466
467			for my $__cell (@{$_cell or []}) {
468			if ($__cell and $__cell->{element} and
469			not $__cell->{is_header} and
470			not $__cell->{element}->has_attribute_ns (undef, 'headers')) {
471			$__cell->{header}->{$x}->{$y} = 1;
472			}
473			}
474			}; # $assign_header
475
476	wakaba	1.12	my @headers_cell;
477			my $id_to_cell = {};
478			## ISSUE: ID duplication, non-TH reference
479
480	wakaba	1.11	for my $x (0 .. $table->{width} - 1) {
481			for my $y (0 .. $table->{height} - 1) {
482			my $cell = $table->{cell}->[$x]->[$y];
483			$cell = $cell->[0] if $cell; # anchored cell is always ->{cell}[][][0].
484			next if $cell->{x} != $x;
485			next if $cell->{y} != $y;
486			if ($cell) {
487			if ($cell->{is_header}) {
488	wakaba	1.12	my $id = $cell->{element}->get_attribute_ns (undef, 'id');
489			if (defined $id and not $id_to_cell->{$id}) {
490			$id_to_cell->{$id} = $cell;
491			}
492
493	wakaba	1.11	my $scope = $cell->{element}->get_attribute_ns (undef, 'scope');
494			$scope = $scope ? lc $scope : ''; ## TODO: case
495			if ($scope eq 'row') {
496			for my $_x ($x + $cell->{width} .. $table->{width} - 1) {
497			for my $_y ($y .. $y + $cell->{height} - 1) {
498			$assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
499			}
500			}
501			} elsif ($scope eq 'col') {
502			for my $_x ($x .. $x + $cell->{width} - 1) {
503			for my $_y ($y .. $table->{height} - 1) {
504			$assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
505			}
506			}
507			} elsif ($scope eq 'rowgroup') {
508			## NOTE: A cell cannot exceed across a row group boundary.
509			if ($table->{row_group}->[$y] and
510			$table->{row_group}->[$y]->{height}) {
511			for my $_x ($x .. $table->{width} - 1) {
512			for my $_y ($y ..
513			$table->{row_group}->[$y]->{y} +
514			$table->{row_group}->[$y]->{height} - 1) {
515			$assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
516			}
517			}
518			}
519			## TODO: Should we raise a warning?
520			} elsif ($scope eq 'colgroup') {
521			if ($table->{column_group}->[$x] and
522			$table->{column_group}->{width} and
523			$table->{column_group}->[$x]->{x} == $x) { # anchored
524			for my $_x ($x ..
525			$table->{column_group}->[$x]->{x} +
526			$table->{column_group}->[$x]->{width} - 1) {
527			for my $_y ($y .. $table->{height} - 1) {
528			$assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
529			}
530			}
531			}
532			## TODO: Warning?
533			} else { # auto
534			## 1.
535			my $header_width = $cell->{width};
536			W: for ($x + $cell->{width} .. $table->{width} - 1) {
537			my $_cell = $table->{cell}->[$_]->[$y];
538			for (@{$_cell or []}) {
539			if ($_->{element} and not $_->{is_empty}) {
540			last W; # not empty
541			}
542			}
543			$header_width++;
544			} # W
545
546			## 2.
547			my $_x = $x + $header_width;
548
549			## 3.
550			HORIZONTAL: {
551			last HORIZONTAL if $_x == $table->{width}; # goto Vertical
552
553			## 4. # goto Vertical
554			last HORIZONTAL
555			if $table->{cell}->[$_x]->[$y] and
556			$table->{cell}->[$_x]->[$y]->[0] and # anchored
557			$table->{cell}->[$_x]->[$y]->[0]->{is_header};
558
559			## 5.
560			for my $_y ($y .. $y + $cell->{height} - 1) {
561			$assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
562			}
563
564			## 6.
565			$_x++;
566
567			## 7.
568			redo HORIZONTAL;
569			} # HORIZONTAL
570
571			## 8. Vertical
572			my $_y = $y + $cell->{height};
573
574			VERTICAL: {
575			## 9. # goto END
576			last VERTICAL if $_y == $table->{height};
577
578			## 10.
579			if ($table->{cell}->[$x]->[$_y]) {
580			my $h_cell = $table->{cell}->[$x]->[$_y]->[0]; # anchored cell
581			if ($h_cell and $h_cell->{is_header}) {
582			## 10.1.
583			my $width = $h_cell->{width};
584			W: for ($h_cell->{x} + $width .. $table->{width} - 1) {
585			my $_cell = $table->{cell}->[$_]->[$y];
586			for (@{$_cell or []}) {
587			if ($_->{element} and not $_->{is_empty}) {
588			last W; # not empty
589			}
590			}
591			$width++;
592			} # W
593
594			## 10.2. # goto end
595			last VERTICAL if $width == $header_width;
596			} # 10.
597			}
598
599			## 11.
600			for my $_x ($x .. $x + $header_width - 1) {
601			$assign_header->($table->{cell}->[$_x]->[$_y] => $x, $y);
602			}
603
604			## 12.
605			$_y++;
606
607			## 13. # goto vertical (wrong)
608			redo VERTICAL;
609			} # VERTICAL
610
611			## 14. End
612			# (we have already done)
613			}
614			} else { # data cell
615	wakaba	1.12	if ($cell->{element} and
616			$cell->{element}->has_attribute_ns (undef, 'headers')) {
617			push @headers_cell, $cell;
618			}
619	wakaba	1.11	}
620			}
621			}
622			}
623
624	wakaba	1.12	for my $headers_cell (@headers_cell) {
625			my @headers = split /[\x09-\x0D\x20]+/,
626			$headers_cell->{element}->get_attribute_ns (undef, 'headers');
627			my %headers;
628			for my $header_id (@headers) {
629			next unless length $header_id;
630			if ($headers{$header_id}) {
631			$onerror->(type => 'duplicate token', value => $header_id,
632			node => $headers_cell->{element}->get_attribute_node_ns
633			(undef, 'headers'),
634			level => $must_level);
635			next;
636			}
637			$headers{$header_id} = 1;
638
639			if ($id_to_cell->{$header_id}) {
640			my $header_cell = $id_to_cell->{$header_id};
641			$headers_cell->{header}->{$header_cell->{x}}->{$header_cell->{y}} = 1;
642			} else {
643			$onerror->(type => 'no header cell', value => $header_id,
644			node => $headers_cell->{element}->get_attribute_node_ns
645			(undef, 'headers'),
646			level => $must_level);
647			}
648			}
649			}
650	wakaba	1.11
651			## NOTE: The "tree order" constraints in the spec algorithm are irrelevant
652			## in fact.
653	wakaba	1.12
654			## NOTE: We does not support ID attributes other than HTML "id" attribute.
655	wakaba	1.11	} # assign_header
656	wakaba	1.1
657			1;
658	wakaba	1.14	## $Date: 2008/05/10 10:06:49 $