1# 2# re_graph.pl -- Graph a regular expression 3# 4=pod 5 6=head1 NAME 7 8re_graph.pl - Graph regular expression 9 10=head1 SYNOPSIS 11 12B<re_graph.pl> 13[B<-d>] 14[B<-o> I<out_file>] 15[B<-x> I<min-x>] 16[B<-y> I<min-y>] 17I<regular-expression> 18[I<string>] 19 20=head1 DESCRIPTION 21 22The I<re_graph.pl> program graphs regular expressions. The guts of the 23regular expression engine is a simple state machine. The various states 24and operations in the regular expression parser can be displayed using a 25surprisingly simple diagram. 26 27A few notes on what you are looking at: 28 29The nodes B<Start> and B<Stop> denote the beginning and end of the regular 30expression. 31 32The solid squares denote atoms. Lines indicate the next state. 33When a line splits, the state machine will take the top line first. 34If it's path is blocked it will backup and take the next lower line. 35This is repeated until it finds a path to the end or all paths are exhausted. 36 37Brown boxes indicate a grouping operation, i.e. (). 38 39Green boxes indicate a zero with test. The state machine will perform the 40test inside the box before moving ahead. 41 42For more information, see the tutorial below. 43 44=head1 OPTIONS 45 46=over 4 47 48=item B<-d> 49 50Turn on debugging. The debugging output is printed on the console as regular 51expressions are compiled. 52 53=item B<-o> I<out_file> 54 55Specify the output file for the images. Default = I<re_graph_%02d.png>. 56If only a regular expresion is specified, the output will be written 57to the given file. 58 59If the system is used in graph / execution mode, a series of files will 60be written using the printf style file name specified. 61 62=item B<-x> I<min-x> 63 64Specify the minimum size of the image in pixels in the X direction. 65 66=item B<-y> I<min-y> 67 68Specify the minimum size of the image in pixels in the Y direction. 69 70=back 71 72=head1 TUTORIAL 73 74This tutorial shows what happens when a set of sample regular expressions 75are graphed. This set of regular expressions closely follows the 76Chapter 4 of "Perl for C Programmers" by Steve Oualline. 77 78The set of regular expressions used for this tutorial is: 79 80 test 81 ^Test 82 ^ *# 83 ^[ \t]*# 84 ^\s*# 85 ([^#]*)(#.*) 86 a|b 87 ^(([^#"]*|".*")*)(#.*) 88 ^((?:[^#"]*|".*?")*)(#.*) 89 ^((?:[^#"]*|".*?(?<!\\)")*)(#.*) 90 91Let's take a look at the graphs produced by these expressions. 92 93=over 4 94 95=begin html 96 97<p><img src="tut_01_00.png"></p> 98 99=end html 100 101=item B</test/> 102 103This is a very simple expression. It matches "test" anywhere on the line. 104If you look at the graph of this expression, it consists of three nodes "Start", 105"EXACT <test>" and "END". 106 107The "Start" node indicates the start of the regular expression. 108 109The "EXACT <test>" node tells the engine that the text must match the 110text "test" exactly. 111 112The "END" node indicates the end of the regular expression. If you reach 113the "END" node, a successful match was found. 114 115Flow is a straight line from "Start", through the "EXACT" check, to end. 116 117=begin html 118 119<p><img src="tut_02_00.png"></p> 120 121=end html 122 123=item B</^Test/> 124 125A new item was added with this expression, an anchor. It's named BOL 126(Beginning of line) and shows up as an additional node. 127 128=begin html 129 130<p><img src="tut_03_00.png"></p> 131 132=end html 133 134=item B</^ *#/> 135 136Now we start having fun. This expression matches anything that consists 137of a start of line (^), a bunch of spaces ( *), and a sharp (#). 138 139The way the state machine works it that it starts at "Start" and works 140it's way through the nodes. You'll notice that between "BOL" and 141"EXACT < >" there's a fork in the road. 142 143The state machine will take the top branch if possible. So if the next 144character is a space, the system will take the top branch and match the 145"EXACT < >" node. If not, the bottom branch is taken and we wind up 146at the "EXACT <#>" node. 147 148If there's no path to the "END", then we don't have a match. 149 150=begin html 151 152<p><img src="tut_04_00.png"></p> 153 154=end html 155 156=item B</^[ \t]*#/> 157 158This is the same as the previous example, except the space was replaced 159by a character set. We call the set "space and tab". The system translates 160this into "\11\40". It's the same thing, suitable obfuscated for computer 161work. 162 163=begin html 164 165<p><img src="tut_05_00.png"></p> 166 167=end html 168 169=item B</^\s*#/> 170 171Again, the middle as been replace by another token. In this case it's 172the SPACE token which matches any whitespace. 173 174=begin html 175 176<p><img src="tut_06_0.png"></p> 177 178=end html 179 180=item B</([^#]*)(#.*)/> 181 182This expression introduces us to the grouping operators. They show as the 183big brown boxes. 184 185The other change is that we use the expression [^#], which matches anything 186except a hash mark. Perl changes this to a "ANYOF" clauses which matches 187all characters except the single one we don't want. 188 189Note: This ANYOF node overflows the size of the box. This is a know bug. 190 191The graphing program can show how the regular expression excution 192process. Let's see what happens when we run the command: 193 194 perl re_graph.pl -o tut_06_%d.png '([^#]*)(#.*)' 'text # Comment' 195 196=begin html 197 198<p><img src="tut_06_1.png"></p> 199 200=end html 201 202The first image show a yellow arrow pointing to the first set of 203(), indicating that the system is about to go into $1. 204 205=begin html 206 207<p><img src="tut_06_2.png"></p> 208 209=end html 210 211The next yellow arrow points at the B<ANYOF> operator indicating that 212the regular expression engine is about to look at the C<[^#]> part 213of the expression. 214 215=begin html 216 217<p><img src="tut_06_3.png"></p> 218 219=end html 220 221In the next screen, the yellow arrow has moved to the box 222representing the second set of (). That means that the first 223part of matching process is done. The string C<text> is highlighted 224yellowing, indicating that that much of the string has be matched 225so far. 226 227=begin html 228 229<p><img src="tut_06_4.png"></p> 230 231=end html 232 233Next the yellow arrow points to the "#" node. The string is highlighted 234up to the just before the "#". This tells us that engine is about to 235match the "#" in the string against the "#" in the regular expression. 236 237The next few images (not shown) show the engine matching the rest of 238the string. 239 240=begin html 241 242<p><img src="tut_07_0.png"></p> 243 244=end html 245 246=item B</a|b/> 247 248Now we introduce the concept of a selection of two different atoms. Note that 249the branch arrows are drawn smaller to make them stand out. 250 251=begin html 252 253<p><img src="tut_08_00.png"></p> 254 255=end html 256 257=item B</^(([^#"]*|".*")*)(#.*)/> 258 259See the book for what this regular expression tries to match. 260 261This expression adds nested grouping, and some additional stuff that we've seen 262before. 263 264=begin html 265 266<p><img src="tut_09_00.png"></p> 267 268=end html 269 270=item B</^((?:[^#"]*|".*?")*)(#.*)/> 271 272This is like the previous example, except what was the $2 grouping has been 273replaced by the "Group no $" operator (?:...). Notice that the line around 274the second group has disappeared and what was $3 is now $2. 275 276(In future versions of this graphing tool we will graph the invisible group 277operator. We just did figure out how to do it yet.) 278 279Also notice the use of the "*?" operator. Remember when going through 280the nodes, when a branch is encountered, the system will try and take 281the top one first. 282 283=begin html 284 285<p><img src="tut_10_00.png"></p> 286 287=end html 288 289=item B</^((?:[^#"]*|".*?(?<!\\)")*)(#.*)/> 290 291The grand finale. One new type of node has been introduced: (?<!\\). This is 292the negative look-behind. It's the red box on the screen. When the state machine 293sees this, it matches the text behind the current location marker against the 294indicated text and if it fails then a match against the next node is possible. 295(Boy does this not translate into English well.) 296 297Basically the clause in question looks for a double quoted string ("xxx"), but 298will ignore a double quote it's escaped ("xxx\"yyy"). 299 300=back 301 302=head1 BUGS / LIMITATIONS 303 304This will not graph all the regular expressions. Some of the more advanced 305features of the engine are just not handled. 306 307We currently "graph" the "group, no $1" (?:..) operator by displaying nothing. 308A box should be put around the expression. 309 310The boxes drawn by the program are a fixed with not related to the size of 311the text they contain. Text can easily overflow the box. 312 313The system is UNIX/Linux specific. This is caused by only one small 314section of code should anyone want to port this to a braindamaged 315operating system. 316 317Better use of color can be made. Specifically all the nodes do not 318have to be green. Come to think of it they call don't have to be 319rectangles either. 320 321Sometimes the lines connecting one section to another take some strange 322twists. 323 324=head1 LICENSE 325 326Licensed under the GPL. (See the end of the source file for a copy). 327 328=head1 AUTHOR 329 330Steve Oualline (oualline@www.oualline.com) 331 332=cut 333use strict; 334use warnings; 335 336use IO::Handle; 337use English; 338use GD; 339use GD::Arrow; 340 341# 342# Constants that control th layout 343 344# Size of a node (X Space) 345use constant X_NODE_SIZE => 60; 346 347# Size of a node (Y Space) 348use constant Y_NODE_SIZE => 40; 349 350# Space text over this far 351use constant X_TEXT_OFFSET => 3; 352use constant Y_TEXT_OFFSET => 3; 353 354# Space between nodes (X) 355use constant X_MARGIN => 50; 356 357# Vertical spacing 358use constant Y_MARGIN => 10; 359 360# Offset for line 2 of a 2 line text field 361use constant X_LINE2_OFFSET => 10; 362 363# Offset for line 2 of a 2 line text field 364use constant Y_LINE2_OFFSET => 15; 365 366# Padding for PLUS style nodes (left, right) 367use constant PLUS_PAD => 10; 368 369# Space between branches (x) 370use constant X_BRANCH_MARGIN => 20; 371 372# Space between branches (y) 373use constant Y_BRANCH_MARGIN => 20; 374 375# Thickness of the lines 376use constant THICKNESS => 3; 377 378# Margin around the graph 379use constant MARGIN => 100; 380 381# Label location 382use constant LABEL_LOC_X => 50; 383use constant LABEL_LOC_Y => 50; 384 385# Location of progress msg 386use constant PROGRESS_X => 50; 387use constant PROGRESS_Y => 70; 388 389# Length of the yellow arrow 390use constant YELLOW_ARROW_SIZE => 25; 391use constant YELLOW_ARROW_WIDTH => 5; 392 393use Getopt::Std; 394 395use vars qw/$opt_d $opt_o $opt_x $opt_y/; 396 397STDOUT->autoflush(1); 398 399# Configuration items 400my $x_margin = 16; # Space between items 401my $y_margin = 16; # Space between items 402 403# 404# Fields 405# node -- Node number 406# type -- Node type (from re debug) 407# arg -- Argument (optional) 408# next -- Next node 409# 410 411# Regular expression debugging information 412my @re_debug; 413 414# 415# Fields 416# x_size - Size of the node in X 417# y_size - Size of the node in Y 418# x_loc - X Location of the node 419# y_loc - Y Location of the node 420# node - Reference to the 421# node in @re_debug 422# child - Array of child 423# nodes for this node 424# 425 426# Formatted version of the regular expression 427my @format_re; 428 429# Re we are displaying now 430my $current_re; 431 432my $re_to_add = ""; # Re we are adding 433 434# 435# Image variables 436# 437my $image; # The image 438my $color_white; # White color 439my $color_black; # The black color 440my $color_green; # The green color 441my $color_blue; # Blue color 442my $color_light_green; # Light green color 443 444# Forward declarations 445sub draw_node_array($); 446sub size_array(\@); 447sub layout_array($$$\@); 448 449################################################ 450# filled_rectangle -- Draw a filled rectangle at 451# the given location 452################################################ 453sub filled_rectangle($$$$$) 454{ 455 # Corners of the rectangle 456 my $x1 = shift; 457 my $y1 = shift; 458 my $x2 = shift; 459 my $y2 = shift; 460 461 my $color = shift; # Color for drawing 462 463 if ($opt_d) { 464 print 465 "Rectangle($x1, $y1, $x2, $y2, $color)\n"; 466 } 467 $image->filledRectangle( 468 $x1, $y1, $x2, $y2, 469 $color); 470 $image->setThickness(1); 471 $image->rectangle( 472 $x1, $y1, $x2, $y2, 473 $color_black); 474} 475 476################################################ 477# arrow -- Draw an arrow from x1,y1 -> x2,y2 478# 479# All arrows are black 480################################################ 481sub arrow($$$$) { 482 my $x1 = shift; # Start of arrow 483 my $y1 = shift; 484 my $x2 = shift; # End of arrow 485 my $y2 = shift; 486 487 if ($opt_d) { 488 print "Arrow($x1, $y1, $x2, $y2)\n"; 489 } 490 # For some reason arrows 491 # tend to point backwards 492 my $arrow = GD::Arrow::Full->new( 493 -X1 => $x2, 494 -Y1 => $y2, 495 -X2 => $x1, 496 -Y2 => $y1, 497 -WIDTH => THICKNESS-1); 498 $image->setThickness(1); 499 $image->filledPolygon($arrow, $color_black); 500} 501 502############################################ 503# The "PLUS" node 504# 505# 506# 0 1 2 1p 2p 3p (p = +size of child) 507# v v v L3 v v v 508# . --------- . . 509# . /. . .\ . . 510# ./ . . . \ . 511# a2 < . . . > a1. 512# .\ . . . /. . 513# . \+-------+/ . 514# L1--->| child |----->+ L2 515# . +-------+ . . 516# 517# Arc start, end, centers 518# 519# a1 / 270 - 180 / (ap*2, y-a) 520# a2 / 90 - 180 / (a0, y-2a), (a2, y-2a) 521# 522# L1 (a3, y+2a) (a3p, y+2a) 523############################################ 524 525#------------------------------------------ 526# size_plus -- Compute the size of 527# a plus/star type node 528#------------------------------------------ 529sub size_plus($) 530{ 531 # Node we want layout information for 532 my $node = shift; 533 534 # Compute the size of the children 535 my ($x_size, $y_size) = 536 size_array(@{$node->{children}}); 537 538 # Arc size is based on the 539 # Y dimension of the children 540 $node->{arc_size} = 541 int($y_size/4) + PLUS_PAD; 542 543 $node->{child_x} = $x_size - X_MARGIN; 544 545 $node->{x_size} = 546 $node->{child_x} + 547 $node->{arc_size} * 2 + X_MARGIN; 548 549 $node->{y_size} = 550 $y_size + $node->{arc_size} * 2; 551} 552#------------------------------------------ 553# Draw the plus type node 554#------------------------------------------ 555sub draw_plus($) 556{ 557 # The node we are drawing 558 my $cur_node = shift; 559 560 layout_array( 561 $cur_node->{x_loc} + 562 $cur_node->{arc_size} * 1, 563 $cur_node->{y_loc}, 564 $cur_node->{y_size}, 565 @{$cur_node->{children}}); 566 567 draw_node_array($cur_node->{children}); 568 569 # The place we start drawing from (X) 570 my $from_x = $cur_node->{x_loc}; 571 572 # The current middle of the item (Y) 573 my $y = $cur_node->{y_loc} + 574 int($cur_node->{y_size}/2); 575 576 # Size of an arc 577 my $arc_size = $cur_node->{arc_size}; 578 579 # Size of the child 580 my $child_x = $cur_node->{child_x}; 581 582 # Debugging 583 if (0) { 584 for (my $debug_x = 0; 585 $debug_x < 5; 586 $debug_x++) { 587 $image->line( 588 $from_x + 589 $arc_size * $debug_x, 590 $y - $arc_size*2, 591 $from_x + 592 $arc_size * $debug_x, 593 $y + $arc_size*2, 594 $color_black 595 ); 596 } 597 598 for (my $debug_x = 3; 599 $debug_x < 7; 600 $debug_x++) { 601 $image->line( 602 $from_x + $child_x + 603 $arc_size * $debug_x, 604 $y - $arc_size*2, 605 $from_x + $child_x + 606 $arc_size * $debug_x, 607 $y + $arc_size*2, 608 $color_green 609 ); 610 } 611 } 612 613 my $flip = 1; # Flipping factor 614 if ($cur_node->{min_flag}) { 615 $flip = -1; 616 } 617 618 $image->setThickness(THICKNESS); 619 # First arc (a1) 620 $image->arc( 621 $from_x + $child_x + $arc_size, 622 $y - $arc_size * $flip, 623 $arc_size *2, $arc_size *2, 624 270, 90, 625 $color_black); 626 627 $image->arc( 628 $from_x + $arc_size * 1, 629 $y - $arc_size * $flip, 630 $arc_size *2, $arc_size *2, 631 90, 270, 632 $color_black); 633 634 # Draw (L1) 635 arrow( 636 $from_x, $y, 637 $from_x + $arc_size * 1, $y 638 ); 639 640 # Draw (L2) 641 arrow( 642 $from_x + $child_x + $arc_size * 1, 643 $y, 644 $from_x + $child_x + $arc_size * 2, 645 $y 646 ); 647 648 # Draw (L3) 649 arrow( 650 $from_x + $child_x + $arc_size * 1, 651 $y - $arc_size * 2, 652 $from_x + $arc_size * 1, 653 $y - $arc_size * 2 654 ); 655 656 657 # Text to display for the current node 658 my $text = $cur_node->{node}->{text_label}; 659 if ($cur_node->{min_flag}) { 660 $text .= "?"; 661 } 662 663 $image->string( 664 gdMediumBoldFont, 665 $from_x + $child_x + $arc_size * 2, 666 $y - $arc_size * 2, 667 $text, 668 $color_blue); 669 670 $cur_node->{left_x} = $from_x; 671 $cur_node->{left_y} = $y; 672 673 $cur_node->{right_x} = 674 $from_x + $cur_node->{child_x} + 675 $cur_node->{arc_size} * 2; 676 677 $cur_node->{right_y} = $y; 678} 679############################################ 680# The "STAR" node 681# 682# 683# (p = +size of child) 684# 0 1 2 3 p3 p4 p5 685# v v v v L2 v v v 686# . ----------------- . . 687# . /. . . .\ . . 688# ./ . . . . \ . 689# a6 < . . . a5 . > . 690# .\ . . . . /. . 691# . \. . . +-------+/ . 692# L3----------->| child |- . + 693# . .\ . j +-------+ .a4/. 694# . . \a1 . . . / . 695# . . \ . . ./ . 696# . . | . . | . 697# . . .\ . . / . 698# . . a2\ . ./a3 . 699# . . . \--------- 700# ^ ^ L1 701# 2 3 702# 703# Arc / swing / center 704# a1 / 270 - 0 / (a1, y + a) 705# a2 / 90 - 180 / (a3, y + a) 706# a3 / 0 - 90 / (p3, y + a) 707# a4 / 180 - 270 / (a4p, y) 708# 709# a5 / 270 - 90 / (p3, y-a) 710# a6 / 90 - 270 / (a1, y-a) 711# 712# L1 (a3, y+2a) (a3p, y+2a) 713############################################ 714 715#----------------------------------------- 716# size_star -- Compute the size of 717# a star type node 718#----------------------------------------- 719sub size_star($) 720{ 721 # Node we want layout information for 722 my $node = shift; 723 724 # Compute the size of the children 725 my ($x_size, $y_size) = 726 size_array(@{$node->{children}}); 727 728 # Arc size is based on the 729 # Y dimension of the children 730 $node->{arc_size} = 731 int($y_size/4) + PLUS_PAD; 732 733 $node->{child_x} = $x_size - X_MARGIN; 734 735 $node->{x_size} = $node->{child_x} + 736 $node->{arc_size} * 5 + X_MARGIN; 737 738 $node->{y_size} = $y_size + 739 $node->{arc_size} * 2 + Y_MARGIN; 740} 741#----------------------------------------- 742# Draw the star type node 743#----------------------------------------- 744sub draw_star($) 745{ 746 # The node we are drawing 747 my $cur_node = shift; 748 749 layout_array( 750 $cur_node->{x_loc} + 751 $cur_node->{arc_size} * 3, 752 $cur_node->{y_loc}, 753 $cur_node->{y_size}, 754 @{$cur_node->{children}}); 755 756 # The place we start drawing from (X) 757 my $from_x = $cur_node->{x_loc}; 758 759 # The current middle of the item (Y) 760 my $y = int($cur_node->{y_loc} + 761 $cur_node->{y_size}/2); 762 763 # Size of an arc 764 my $arc_size = $cur_node->{arc_size}; 765 766 # Size of the child 767 my $child_x = $cur_node->{child_x}; 768 769 # Debugging 770 if (0) { 771 for (my $debug_x = 0; 772 $debug_x < 5; 773 $debug_x++) { 774 $image->line( 775 $from_x + 776 $arc_size * $debug_x, 777 $y - $arc_size*2, 778 $from_x + 779 $arc_size * $debug_x, 780 $y + $arc_size*2, 781 $color_black 782 ); 783 } 784 785 for (my $debug_x = 3; 786 $debug_x < 7; 787 $debug_x++) { 788 $image->line( 789 $from_x + $child_x + 790 $arc_size * $debug_x, 791 $y - $arc_size*2, 792 $from_x + $child_x + 793 $arc_size * $debug_x, 794 $y + $arc_size*2, 795 $color_green 796 ); 797 } 798 } 799 800 my $flip = 1; # Flipping factor 801 if ($cur_node->{min_flag}) { 802 $flip = -1; 803 } 804 805 $image->setThickness(THICKNESS); 806 if ($flip == 1) { 807 # First arc (a1) 808 $image->arc( 809 $from_x + $arc_size, 810 $y + $arc_size, 811 $arc_size * 2, $arc_size * 2, 812 270, 0, 813 $color_black); 814 815 # Second arc (a2) 816 $image->arc( 817 $from_x + $arc_size * 3, 818 $y + $arc_size, 819 $arc_size * 2, $arc_size * 2, 820 90, 180, 821 $color_black); 822 } else { 823 # First arc (a1) 824 $image->arc( 825 $from_x + $arc_size, 826 $y - $arc_size, 827 $arc_size * 2, $arc_size * 2, 828 0, 90, 829 $color_black); 830 831 # Second arc (a2) 832 $image->arc( 833 $from_x + $arc_size * 3, 834 $y - $arc_size, 835 $arc_size * 2, $arc_size * 2, 836 180, 270, 837 $color_black); 838 } 839 840 if ($flip > 0) { 841 # Third arc (a3) 842 $image->arc( 843 $from_x + $child_x + 844 $arc_size * 3, 845 $y + $arc_size, 846 $arc_size * 2, $arc_size * 2, 847 0, 90, 848 $color_black); 849 850 # Fourth arc (a4) 851 $image->arc( 852 $from_x + $child_x + 853 $arc_size * 5, 854 $y + $arc_size, 855 $arc_size * 2, $arc_size * 2, 856 180, 270, 857 $color_black); 858 } else { 859 # Third arc (a3) 860 $image->arc( 861 $from_x + $child_x + 862 $arc_size * 3, 863 $y - $arc_size, 864 $arc_size * 2, $arc_size * 2, 865 270, 0, 866 $color_black); 867 868 # Fourth arc (a4) 869 $image->arc( 870 $from_x + $child_x + 871 $arc_size * 5, 872 $y - $arc_size, 873 $arc_size * 2, $arc_size * 2, 874 90, 180, 875 $color_black); 876 } 877 878 # Fifth arc (a5) 879 $image->arc( 880 $from_x + $child_x + $arc_size * 3, 881 $y - $arc_size * $flip, 882 $arc_size * 2, $arc_size * 2, 883 270, 90, 884 $color_black); 885 886 # Sixth arc (a6) 887 $image->arc( 888 $from_x + $arc_size, 889 $y - $arc_size * $flip, 890 $arc_size * 2, $arc_size * 2, 891 90, 270, 892 $color_black); 893 894 # L1 895 arrow( 896 $from_x + $arc_size * 3, 897 $y + $arc_size * 2 * $flip, 898 $from_x + $arc_size * 3 + $child_x, 899 $y + $arc_size * 2 * $flip); 900 901 # L2 902 arrow( 903 $from_x + $arc_size * 3 + $child_x, 904 $y - $arc_size * 2 * $flip, 905 $from_x + $arc_size * 1, 906 $y - $arc_size * 2 * $flip); 907 908 # Draw (L3) 909 arrow( 910 $from_x, $y, 911 $from_x + $arc_size * 3, $y); 912 913 914 $image->string( 915 gdMediumBoldFont, 916 $from_x + $child_x + $arc_size * 4, 917 $y - $arc_size * 2, 918 ($cur_node->{min_flag}) ? "*?" : "*", 919 $color_black); 920 921 922 draw_node_array($cur_node->{children}); 923 924 $cur_node->{left_x} = $from_x; 925 $cur_node->{left_y} = $y; 926 927 $cur_node->{right_x} = 928 $from_x + $cur_node->{child_x} + 929 $cur_node->{arc_size} * 5; 930 931 $cur_node->{right_y} = $y; 932} 933 934############################################ 935# Branch nodes 936############################################ 937#------------------------------------------- 938# layout a branch node 939#------------------------------------------- 940sub size_branch($) 941{ 942 # Node we want layout information for 943 my $node = shift; 944 945 my $x_size = 0; # Current X size 946 my $y_size = 0; # Current Y size 947 948 foreach my $cur_choice ( 949 @{$node->{choices}}) { 950 951 # The size of the current choice 952 my ($x_choice, $y_choice) = 953 size_array(@{$cur_choice}); 954 955 if ($x_size < $x_choice) { 956 $x_size = $x_choice; 957 } 958 if ($y_size != 0) { 959 $y_size += Y_BRANCH_MARGIN; 960 } 961 $cur_choice->[0]->{row_y_size} = 962 $y_choice; 963 964 $y_size += $y_choice; 965 } 966 $x_size += 2 * X_BRANCH_MARGIN + X_MARGIN; 967 $node->{x_size} = $x_size; 968 $node->{y_size} = $y_size; 969} 970#------------------------------------------- 971# draw_branch -- Draw a branch structure 972#------------------------------------------- 973sub draw_branch($) 974{ 975 # Node we want layout information for 976 my $cur_node = shift; 977 978 # Location where we draw the branches 979 my $x_loc = $cur_node->{x_loc} + 980 X_BRANCH_MARGIN; 981 982 my $y_loc = $cur_node->{y_loc}; 983 984 foreach my $cur_child ( 985 @{$cur_node->{choices}} 986 ) { 987 layout_array( 988 $x_loc + X_BRANCH_MARGIN, 989 $y_loc, 990 $cur_child->[0]->{row_y_size}, 991 @{$cur_child}); 992 993 $y_loc += $cur_child->[0]->{row_y_size} + 994 Y_BRANCH_MARGIN; 995 draw_node_array($cur_child); 996 } 997 998 # Largest right x of any node 999 my $max_x = 0; 1000 1001 foreach my $cur_child ( 1002 @{$cur_node->{choices}}) { 1003 1004 # Last node on the string of children 1005 my $last_node = 1006 $cur_child->[$#{$cur_child}]; 1007 1008 if ($last_node->{right_x} > $max_x) { 1009 $max_x = $last_node->{right_x}; 1010 } 1011 } 1012 foreach my $cur_child ( 1013 @{$cur_node->{choices}} 1014 ) { 1015 # Last node on the 1016 # string of children 1017 my $last_node = 1018 $cur_child->[$#{$cur_child}]; 1019 1020 if ($last_node->{right_x} < $max_x) { 1021 $image->line( 1022 $last_node->{right_x}, 1023 $last_node->{right_y}, 1024 $max_x, 1025 $last_node->{right_y}, 1026 $color_black); 1027 } 1028 } 1029 1030 my $left_x = $cur_node->{x_loc}; 1031 my $right_x = $cur_node->{x_loc} + 1032 $cur_node->{x_size} - X_MARGIN; 1033 1034 my $y = $cur_node->{y_loc} + 1035 ($cur_node->{y_size} / 2); 1036 1037 foreach my $cur_child ( 1038 @{$cur_node->{choices}} 1039 ) { 1040 # Create a branch line to the item 1041 # in the list of nodes 1042 $image->line( 1043 $left_x, $y, 1044 $cur_child->[0]->{left_x}, 1045 $cur_child->[0]->{left_y}, 1046 $color_black); 1047 1048 # The last node on the list 1049 my $last_child = 1050 $cur_child->[$#$cur_child]; 1051 1052 # Line from the last node 1053 # to the collection point 1054 $image->line( 1055 $max_x, $last_child->{right_y}, 1056 $right_x, $y, 1057 $color_black); 1058 } 1059 1060 $cur_node->{left_x} = $left_x; 1061 $cur_node->{left_y} = $y; 1062 1063 $cur_node->{right_x} = $right_x; 1064 $cur_node->{right_y} = $y; 1065} 1066############################################ 1067# Functions to compute the size of various nodes 1068############################################ 1069#------------------------------------------- 1070# layout the start node 1071#------------------------------------------- 1072sub size_start($) 1073{ 1074 # Node we want layout information for 1075 my $node = shift; 1076 1077 $node->{x_size} = X_NODE_SIZE + X_MARGIN; 1078 $node->{y_size} = Y_NODE_SIZE; 1079} 1080#------------------------------------------- 1081# layout the end node 1082#------------------------------------------- 1083sub size_end($) 1084{ 1085 # Node we want layout information for 1086 my $node = shift; 1087 1088 $node->{x_size} = X_NODE_SIZE; 1089 $node->{y_size} = Y_NODE_SIZE; 1090} 1091#------------------------------------------- 1092# layout the "EXACT" node (EXACT + text) 1093#------------------------------------------- 1094sub size_exact($) 1095{ 1096 # Node we want layout information for 1097 my $node = shift; 1098 1099 $node->{x_size} = X_NODE_SIZE + X_MARGIN; 1100 $node->{y_size} = Y_NODE_SIZE; 1101} 1102#------------------------------------------- 1103# layout the "ANYOF" node (ANYOF + text) 1104#------------------------------------------- 1105# Size of a character in X dimensions 1106use constant X_CHAR_SIZE => 7; 1107 1108sub size_text($) 1109{ 1110 # Node we want layout information for 1111 my $node = shift; 1112 1113 # Get the size of the string argument 1114 my $length = length($node->{node}->{arg}); 1115 if ($length < 10) { 1116 $length = 10; 1117 } 1118 $node->{x_size} = 1119 $length * X_CHAR_SIZE + X_MARGIN; 1120 1121 $node->{y_size} = Y_NODE_SIZE; 1122} 1123#------------------------------------------- 1124# OPEN the open ( 1125#------------------------------------------- 1126# Size of the box around a group 1127use constant BOX_MARGIN => 50; 1128 1129# Height of the font used to label boxes 1130use constant BOX_FONT_SIZE => 15; 1131 1132sub size_open($) 1133{ 1134 # The node we want to size 1135 my $node = shift; 1136 1137 # Compute the size of the children 1138 my ($x_size, $y_size) = 1139 size_array(@{$node->{children}}); 1140 1141 # We add X_MARGIN because we 1142 # must for all nodes 1143 # 1144 # We subtract X_MARGIN because one too many 1145 # is added in our children 1146 # 1147 # Result is nothing 1148 1149 $node->{x_size} = $x_size + BOX_MARGIN; 1150 1151 $node->{y_size} = 1152 $y_size + BOX_MARGIN + BOX_FONT_SIZE; 1153} 1154 1155 1156# Functions used to compute the sizes 1157# of various elements 1158my %compute_size = ( 1159 "ANYOF" => \&size_text, 1160 "BOL" => \&size_exact, 1161 "SPACE" => \&size_exact, 1162 "NSPACE" => \&size_exact, 1163 "DIGIT" => \&size_exact, 1164 "BRANCH"=> \&size_branch, 1165 "END" => \&size_end, 1166 "EOL" => \&size_exact, 1167 "EXACT" => \&size_exact, 1168 "IFMATCH" => \&size_open, 1169 "OPEN" => \&size_open, 1170 "PLUS" => \&size_plus, 1171 "REF" => \&size_exact, 1172 "REG_ANY" => \&size_exact, 1173 "STAR" => \&size_star, 1174 "Start" => \&size_start, 1175 "UNLESSM" => \&size_open 1176); 1177 1178############################################ 1179# draw functions 1180############################################ 1181sub draw_start_end($) 1182{ 1183 my $cur_node = shift; 1184 my $node_number = $cur_node->{node}->{node}; 1185 1186 filled_rectangle( 1187 $cur_node->{x_loc}, 1188 $cur_node->{y_loc}, 1189 $cur_node->{x_loc} + X_NODE_SIZE, 1190 $cur_node->{y_loc} + Y_NODE_SIZE, 1191 $color_green); 1192 1193 $cur_node->{text} = $image->string( 1194 gdSmallFont, 1195 $cur_node->{x_loc} + X_TEXT_OFFSET, 1196 $cur_node->{y_loc} + Y_TEXT_OFFSET, 1197 1198 $cur_node->{node}->{type}, 1199 $color_black); 1200 1201 $cur_node->{left_x} = $cur_node->{x_loc}; 1202 1203 $cur_node->{left_y} = 1204 $cur_node->{y_loc} + Y_NODE_SIZE / 2; 1205 1206 $cur_node->{right_x} = 1207 $cur_node->{x_loc} + X_NODE_SIZE; 1208 1209 $cur_node->{right_y} = 1210 $cur_node->{y_loc} + Y_NODE_SIZE / 2; 1211} 1212 1213#------------------------------------------- 1214# draw_exact($node) -- Draw a "EXACT" re node 1215#------------------------------------------- 1216sub draw_exact($) 1217{ 1218 my $cur_node = shift; # The node 1219 my $node_number = $cur_node->{node}->{node}; 1220 1221 filled_rectangle( 1222 $cur_node->{x_loc}, 1223 $cur_node->{y_loc}, 1224 $cur_node->{x_loc} + 1225 $cur_node->{x_size} - 1226 X_MARGIN, 1227 $cur_node->{y_loc} + Y_NODE_SIZE, 1228 $color_green); 1229 1230 $image->string( 1231 gdSmallFont, 1232 $cur_node->{x_loc} + X_TEXT_OFFSET, 1233 $cur_node->{y_loc} + Y_TEXT_OFFSET, 1234 "$cur_node->{node}->{type}", 1235 $color_black); 1236 1237 $image->string( 1238 gdSmallFont, 1239 $cur_node->{x_loc} + 1240 X_TEXT_OFFSET + X_LINE2_OFFSET, 1241 $cur_node->{y_loc} + 1242 Y_TEXT_OFFSET + Y_LINE2_OFFSET, 1243 "$cur_node->{node}->{arg}", 1244 $color_black); 1245 1246 $cur_node->{left_x} = $cur_node->{x_loc}; 1247 1248 $cur_node->{left_y} = 1249 $cur_node->{y_loc} + Y_NODE_SIZE / 2; 1250 1251 $cur_node->{right_x} = 1252 $cur_node->{x_loc} + X_NODE_SIZE; 1253 1254 $cur_node->{right_y} = 1255 $cur_node->{y_loc} + Y_NODE_SIZE / 2; 1256} 1257#------------------------------------------- 1258# draw_ref($node) -- Draw a "REF" re node 1259#------------------------------------------- 1260sub draw_ref($) 1261{ 1262 my $cur_node = shift; # The node 1263 my $node_number = $cur_node->{node}->{node}; 1264 1265 filled_rectangle( 1266 $cur_node->{x_loc}, 1267 $cur_node->{y_loc}, 1268 $cur_node->{x_loc} + X_NODE_SIZE, 1269 $cur_node->{y_loc} + Y_NODE_SIZE, 1270 $color_light_green); 1271 1272 $cur_node->{text} = $image->String( 1273 gdSmallFont, 1274 $cur_node->{x_loc} + X_TEXT_OFFSET, 1275 $cur_node->{y_loc} + Y_TEXT_OFFSET, 1276 "Back Reference:\n". 1277 " $cur_node->{node}->{ref}", 1278 $color_black); 1279 1280 $cur_node->{left_x} = $cur_node->{x_loc}; 1281 1282 $cur_node->{left_y} = 1283 $cur_node->{y_loc} + Y_NODE_SIZE / 2; 1284 1285 $cur_node->{right_x} = 1286 $cur_node->{x_loc} + X_NODE_SIZE; 1287 1288 $cur_node->{right_y} = 1289 $cur_node->{y_loc} + Y_NODE_SIZE; 1290} 1291#------------------------------------------- 1292# draw the () stuff 1293#------------------------------------------- 1294sub draw_open($$) 1295{ 1296 my $cur_node = shift; # The node 1297 1298 $image->setStyle( 1299 $color_black, $color_black, 1300 $color_black, $color_black, 1301 $color_black, 1302 $color_white, $color_white, 1303 $color_white, $color_white, 1304 $color_white 1305 ); 1306 $image->rectangle( 1307 $cur_node->{x_loc}, 1308 $cur_node->{y_loc} + 1309 BOX_FONT_SIZE, 1310 $cur_node->{x_loc} + 1311 $cur_node->{x_size} - 1312 X_MARGIN, 1313 $cur_node->{y_loc} + 1314 $cur_node->{y_size}, 1315 gdStyled); 1316 1317 $image->string( 1318 gdSmallFont, 1319 $cur_node->{x_loc}, 1320 $cur_node->{y_loc}, 1321 $cur_node->{text}, 1322 $color_black); 1323 1324 layout_array( 1325 $cur_node->{x_loc} + 1326 BOX_MARGIN/2, 1327 $cur_node->{y_loc} + 1328 BOX_MARGIN/2 + BOX_FONT_SIZE, 1329 $cur_node->{y_size} - 1330 BOX_MARGIN - BOX_FONT_SIZE, 1331 @{$cur_node->{children}}); 1332 1333 draw_node_array($cur_node->{children}); 1334 1335 $cur_node->{left_x} = $cur_node->{x_loc}; 1336 $cur_node->{left_y} = $cur_node->{y_loc} + 1337 ($cur_node->{y_size} + BOX_FONT_SIZE)/2; 1338 1339 $cur_node->{right_x} = $cur_node->{x_loc} + 1340 $cur_node->{x_size} - X_MARGIN; 1341 1342 $cur_node->{right_y} = $cur_node->{left_y}; 1343 1344 # Child we are drawing arrows to / from 1345 my $child = $cur_node->{children}->[0]; 1346 $image->line( 1347 $cur_node->{left_x}, 1348 $cur_node->{left_y}, 1349 $child->{left_x}, 1350 $child->{left_y}, 1351 $color_black 1352 ); 1353 $child = 1354 $cur_node->{children}->[ 1355 $#{$cur_node->{children}} 1356 ]; 1357 1358 $image->line( 1359 $child->{right_x}, 1360 $child->{right_y}, 1361 $cur_node->{right_x}, 1362 $cur_node->{right_y}, 1363 $color_black 1364 ); 1365} 1366 1367my %draw_node = ( 1368 "ANYOF" => \&draw_exact, 1369 "BOL" => \&draw_start_end, 1370 "EOL" => \&draw_start_end, 1371 "SPACE" => \&draw_start_end, 1372 "NSPACE" => \&draw_start_end, 1373 "DIGIT" => \&draw_start_end, 1374 "BRANCH"=> \&draw_branch, 1375 "END" => \&draw_start_end, 1376 "EXACT" => \&draw_exact, 1377 "IFMATCH" => \&draw_open, 1378 "OPEN" => \&draw_open, 1379 "PLUS" => \&draw_plus, 1380 "REF" => \&draw_ref, 1381 "REG_ANY" => \&draw_start_end, 1382 "STAR" => \&draw_star, 1383 "Start" => \&draw_start_end, 1384 "UNLESSM" => \&draw_open 1385); 1386 1387 1388################################################ 1389# usage -- Tell the user how to use us 1390################################################ 1391sub usage() 1392{ 1393 print STDERR <<EOF; 1394Usage is $0 [options] [-o <file>] <re> [<str>] 1395Options: 1396 -d -- Debug 1397 -o <out_file> -- Output file (%d = sequence number) 1398 -x <size> -- Minimum size in X 1399 -y <size> -- Minimum size in Y 1400EOF 1401 exit (8); 1402} 1403################################################ 1404# parse_re -- Parse a regular expression 1405# and leave the results in the array @re 1406################################################ 1407sub parse_re() 1408{ 1409 my $quote_re = $current_re; 1410 $quote_re =~ s/\\/\\\\/g; 1411 my $cmd = <<EOF ; 1412perl 2>&1 <<SHELL_EOF 1413use re 'debug'; 1414/$quote_re/; 1415SHELL_EOF 1416EOF 1417 1418 # The raw debug output 1419 my @raw_debug = `$cmd`; 1420 1421 if ($opt_d) { 1422 print @raw_debug; 1423 } 1424 1425 if ($CHILD_ERROR != 0) { 1426 my $cmd = <<EOF ; 1427perl 2>&1 <<SHELL_EOF 1428use re 'debug'; 1429/ERROR/; 1430SHELL_EOF 1431EOF 1432 @raw_debug = `$cmd`; 1433 if ($CHILD_ERROR != 0) { 1434 die("Could not run perl"); 1435 } 1436 } 1437 1438 @re_debug = (); # Clear out old junk 1439 push(@re_debug, { 1440 node => 0, 1441 type => "Start", 1442 next => 1 1443 }); 1444 foreach my $cur_line (@raw_debug) { 1445 if ($cur_line =~ /^Compiling/) { 1446 next; 1447 } 1448 if ($cur_line =~ /^\s*size/) { 1449 next; 1450 } 1451 # +++---------------------------------- Spaces 1452 # ||| +++------------------------------ Digits 1453 # |||+|||+----------------------------- Group $1 1454 # |||||||| (Node) 1455 # |||||||| 1456 # ||||||||+---------------------------- Colon 1457 # |||||||||+++------------------------- Spaces 1458 # |||||||||||| 1459 # |||||||||||| +++--------------------- Word chars 1460 # ||||||||||||+|||+-------------------- Group $2 1461 # ||||||||||||||||| (Type) 1462 # ||||||||||||||||| 1463 # |||||||||||||||||+++----------------- Spaces 1464 # |||||||||||||||||||| 1465 # |||||||||||||||||||| ++--------------- Any char str 1466 # ||||||||||||||||||||+||+-------------- Group $3 1467 # |||||||||||||||||||||||| (arg) 1468 # ||||||||||||||||||||||||------------- Lit <> 1469 # |||||||||||||||||||||||| 1470 # ||||||||||||||||||||||||+++---------- Spaces 1471 # ||||||||||||||||||||||||||| 1472 # ||||||||||||||||||||||||||| ++----- Any char str 1473 # |||||||||||||||||||||||||||++ || ++-- Lit () 1474 # ||||||||||||||||||||||||||||| || || (next state) 1475 # |||||||||||||||||||||||||||||+||+||-- Group $4 1476 if ($cur_line =~ /\s*(\d+):\s*(\w+)\s*(.*)\s*\((.*)\)/) { 1477 push(@re_debug, { 1478 node => $1, 1479 type => $2, 1480 raw_type => $2, 1481 arg => $3, 1482 next => $4 1483 }); 1484 next; 1485 } 1486 if ($cur_line =~ /^anchored/) { 1487 next; 1488 } 1489 if ($cur_line =~ /^Freeing/) { 1490 last; 1491 } 1492 } 1493} 1494################################################ 1495# $new_index = parse_node($index, 1496# $array, $next, $close) 1497# 1498# -- Parse a single regular expression node 1499# -- Stop when next (or end) is found 1500# -- Or when a close ")" is found 1501################################################ 1502sub parse_node($$$$); 1503sub parse_node($$$$) 1504{ 1505 # Index into the array 1506 my $index = shift; 1507 1508 # Array to put things on 1509 my $array = shift; 1510 1511 my $next = shift; # Next node 1512 1513 # Looking for a close? 1514 my $close = shift; 1515 1516 my $min_flag = 0; # Minimize flag 1517 while (1) { 1518 if (not defined($re_debug[$index])) { 1519 return ($index); 1520 } 1521 if (defined($next)) { 1522 if ($next <= 1523 $re_debug[$index]->{node}) { 1524 1525 return ($index); 1526 } 1527 } 1528 if ($re_debug[$index]->{type} =~ 1529 /CLOSE(\d+)/) { 1530 if (defined($close)) { 1531 if ($1 == $close) { 1532 return ($index + 1); 1533 } 1534 } 1535 } 1536 if ($re_debug[$index]->{type} eq 1537 "MINMOD") { 1538 $min_flag = 1; 1539 $index++; 1540 next; 1541 } 1542#-------------------------------------------- 1543 if (($re_debug[$index]->{type} eq 1544 "IFMATCH") || 1545 ($re_debug[$index]->{type} eq 1546 "UNLESSM")) { 1547 if ($re_debug[$index]->{arg} !~ 1548 /\[(.*?)\]/) { 1549 die("IFMATCH/UNLESSM funny ". 1550 "argument ". 1551 "$re_debug[$index]->{arg}"); 1552 } 1553 # Ending text (= or !=) 1554 my $equal = "!="; 1555 1556 if ($re_debug[$index]->{type} eq 1557 "IFMATCH") { 1558 $equal = "="; 1559 } 1560 # Flag indicating the next look ahead 1561 my $flag = $1; 1562 1563 # Text to label this box 1564 my $text; 1565 1566 if ($flag eq "-0") { 1567 $text = "$equal ahead"; 1568 } elsif ($flag eq "-0") { 1569 $text = "$equal behind"; 1570 } elsif ($flag eq "-1") { 1571 $text = "$equal behind"; 1572 } else { 1573 die("Unknown IFMATCH/UNLESSM ". 1574 "flag text $flag"); 1575 exit; 1576 } 1577 push(@{$array}, { 1578 node => $re_debug[$index], 1579 text => $text, 1580 children => [] 1581 }); 1582 1583 $index = parse_node($index+1, 1584 $$array[$#$array]->{children}, 1585 $re_debug[$index]->{next}, 1586 undef); 1587 next; 1588 } 1589#----------------------------------------- 1590 if ($re_debug[$index]->{type} =~ 1591 /OPEN(\d+)/) { 1592 1593 my $paren_count = $1; 1594 $re_debug[$index]->{type} = "OPEN"; 1595 push(@{$array}, { 1596 node => $re_debug[$index], 1597 paren_count => $paren_count, 1598 text => "( ) => \$$paren_count", 1599 children => [] 1600 }); 1601 1602 $index = parse_node($index+1, 1603 $$array[$#$array]->{children}, 1604 undef, $paren_count); 1605 next; 1606 } 1607#----------------------------------------- 1608 if ($re_debug[$index]->{type} =~ 1609 /REF(\d+)/) { 1610 1611 my $ref_number = $1; 1612 $re_debug[$index]->{type} = "REF"; 1613 push(@{$array}, { 1614 node => $re_debug[$index], 1615 ref => $ref_number, 1616 children => [] 1617 }); 1618 1619 ++$index; 1620 next; 1621 } 1622#----------------------------------------- 1623 if ($re_debug[$index]->{type} eq 1624 "BRANCH") { 1625 1626 push(@{$array}, { 1627 node => $re_debug[$index], 1628 choices => [] 1629 }); 1630 1631 my $choice_index = 0; 1632 while (1) { 1633 # Next node in this series 1634 my $next = 1635 $re_debug[$index]->{next}; 1636 1637 $$array[$#$array]-> 1638 {choices}[$choice_index] = []; 1639 1640 $index = parse_node($index+1, 1641 $$array[$#$array]-> 1642 {choices}[$choice_index], 1643 $next, undef); 1644 1645 if (not defined( 1646 $re_debug[$index])) { 1647 last; 1648 } 1649 1650 if ($re_debug[$index]->{type} ne 1651 "BRANCH") { 1652 last; 1653 } 1654 $choice_index++; 1655 } 1656 next; 1657 } 1658#-------------------------------------------- 1659 if (($re_debug[$index]->{type} eq 1660 "CURLYX") | 1661 ($re_debug[$index]->{type} eq 1662 "CURLY")) { 1663 1664 # Min number of matches 1665 my $min_number; 1666 1667 # Max number of matches 1668 my $max_number; 1669 1670 if ($re_debug[$index]->{arg} =~ 1671 /{(\d+),(\d+)}/) { 1672 $min_number = $1; 1673 $max_number = $2; 1674 } else { 1675 die("Funny CURLYX args ". 1676 "$re_debug[$index]->{arg}"); 1677 exit; 1678 } 1679 1680 my $star_flag = ($min_number == 0); 1681 1682 my $text = "+"; 1683 if ($min_number == 0) { 1684 $text = "*"; 1685 } 1686 if (($max_number != 32767) || 1687 ($min_number > 1)) { 1688 1689 $text = 1690 "{$min_number, $max_number}"; 1691 if ($max_number == 32767) { 1692 $text = "min($min_number)"; 1693 } 1694 } 1695 # Node that's enclosed 1696 # inside this one 1697 my $child = { 1698 node => { 1699 type => 1700 ($star_flag) ? 1701 "STAR" : "PLUS", 1702 raw_type => 1703 $re_debug[$index]->{type}, 1704 arg => 1705 $re_debug[$index]->{arg}, 1706 next => 1707 $re_debug[$index]->{next}, 1708 text_label => 1709 $text 1710 }, 1711 min_flag => $min_flag, 1712 children => [], 1713 }; 1714 1715 push(@{$array}, $child); 1716 1717 $index = parse_node($index+1, 1718 $child->{children}, 1719 $re_debug[$index]->{next}, 1720 undef); 1721 next; 1722 } 1723#----------------------------------------- 1724 if ($re_debug[$index]->{type} eq 1725 "CURLYM") { 1726 1727 my $paren_count; # () number 1728 1729 # Min number of matches 1730 my $min_number; 1731 1732 # Max number of matches 1733 my $max_number; 1734 1735 if ($re_debug[$index]->{arg} =~ 1736 /\[(\d+)\]\s*{(\d+),(\d+)}/) { 1737 $paren_count = $1; 1738 $min_number = $2; 1739 $max_number = $3; 1740 } else { 1741 die("Funny CURLYM args ". 1742 "$re_debug[$index]->{arg}"); 1743 exit; 1744 } 1745 # Are we doing a * or + 1746 # (anything else is just too hard_ 1747 1748 my $star_flag = ($min_number == 0); 1749 1750 # The text for labeling this node 1751 my $text = "+"; 1752 if ($min_number == 0) { 1753 $text = "*"; 1754 } 1755 if (($max_number != 32767) || 1756 ($min_number > 1)) { 1757 1758 $text = 1759 "{$min_number, $max_number}"; 1760 1761 if ($max_number == 32767) { 1762 $text = "min($min_number)"; 1763 } 1764 } 1765 1766 # Node that's enclosed 1767 # inside this one 1768 my $child = { 1769 node => { 1770 type => 1771 ($star_flag) ? 1772 "STAR" : "PLUS", 1773 raw_type => 1774 $re_debug[$index]->{type}, 1775 arg => 1776 $re_debug[$index]->{arg}, 1777 next => 1778 $re_debug[$index]->{next}, 1779 text_label => 1780 $text 1781 }, 1782 min_flag => $min_flag, 1783 children => [], 1784 }; 1785 $min_flag = 0; 1786 1787 # The text for labeling this node 1788 $text = "( ) => \$$paren_count"; 1789 if ($paren_count == 0) { 1790 $text = '( ) [no $x]'; 1791 } 1792 push(@{$array}, 1793 { 1794 node => { 1795 type => 1796 "OPEN", 1797 raw_type => 1798 $re_debug[$index]->{type}, 1799 arg => 1800 $re_debug[$index]->{arg}, 1801 next => 1802 $re_debug[$index]->{next} 1803 }, 1804 paren_count => $paren_count, 1805 text => $text, 1806 children => [$child] 1807 }); 1808 1809 $index = parse_node($index+1, 1810 $child->{children}, 1811 $re_debug[$index]->{next}, 1812 undef); 1813 next; 1814 } 1815#----------------------------------------- 1816 if ($re_debug[$index]->{type} eq 1817 "STAR") { 1818 push(@{$array}, 1819 { 1820 node => { 1821 %{$re_debug[$index]}, 1822 -text_label => "+" 1823 }, 1824 min_flag => $min_flag, 1825 children => [] 1826 }); 1827 $min_flag = 0; 1828 1829 # Where we go for the next state 1830 my $star_next; 1831 1832 if (defined($next)) { 1833 $star_next = $next; 1834 } else { 1835 $star_next = 1836 $re_debug[$index]->{next}; 1837 } 1838 1839 $index = parse_node($index+1, 1840 $$array[$#$array]->{children}, 1841 $star_next, undef); 1842 next; 1843 } 1844#----------------------------------------- 1845 if ($re_debug[$index]->{type} eq 1846 "PLUS") { 1847 push(@{$array}, 1848 { 1849 node => { 1850 %{$re_debug[$index]}, 1851 text_label => "+" 1852 }, 1853 min_flag => $min_flag, 1854 children => [] 1855 }); 1856 $min_flag = 0; 1857 $index = parse_node($index+1, 1858 $$array[$#$array]->{children}, 1859 $re_debug[$index]->{next}, 1860 undef); 1861 next; 1862 } 1863#----------------------------------------- 1864 # Ignore a couple of nodes 1865 if ($re_debug[$index]->{type} eq 1866 "WHILEM") { 1867 ++$index; 1868 next; 1869 } 1870 if ($re_debug[$index]->{type} eq 1871 "SUCCEED") { 1872 ++$index; 1873 next; 1874 } 1875 if ($re_debug[$index]->{type} eq 1876 "NOTHING") { 1877 ++$index; 1878 next; 1879 } 1880 if ($re_debug[$index]->{type} eq 1881 "TAIL") { 1882 ++$index; 1883 next; 1884 } 1885 push(@$array, { 1886 node => $re_debug[$index]}); 1887 1888 if ($re_debug[$index]->{type} eq "END") { 1889 return ($index+1); 1890 } 1891 $index++; 1892 1893 } 1894} 1895################################################ 1896# do_size($cur_node) -- 1897# Compute the size of a given node 1898################################################ 1899sub do_size($); 1900sub do_size($) 1901{ 1902 my $cur_node = shift; 1903 1904 if (not defined( 1905 $compute_size{ 1906 $cur_node->{node}->{type}})) { 1907 1908 die("No compute function for ". 1909 "$cur_node->{node}->{type}"); 1910 exit; 1911 } 1912 $compute_size{ 1913 $cur_node->{node}->{type}}($cur_node); 1914} 1915################################################ 1916# size_array(\@array) -- Compute the size of 1917# an array of nodes 1918# 1919# Returns 1920# (x_size, y_size) -- Size of the elements 1921# 1922# x_size -- Size of all the elements in X 1923# (We assume they are 1924# laid out in a line) 1925# y_size -- Biggest Y size 1926# (side by side layout) 1927################################################# 1928sub size_array(\@) 1929{ 1930 # The array 1931 my $re_array = shift; 1932 1933 # Size of the array in X 1934 my $x_size = 0; 1935 1936 # Size of the elements in Y 1937 my $y_size = 0; 1938 1939 foreach my $cur_node(@$re_array) { 1940 do_size($cur_node); 1941 $x_size += $cur_node->{x_size}; 1942 if ($y_size < $cur_node->{y_size}) { 1943 $y_size = $cur_node->{y_size}; 1944 } 1945 } 1946 return ($x_size, $y_size); 1947} 1948################################################ 1949# layout_array($x_start, $y_start, 1950# $y_max, \@array) 1951# 1952# Layout an array of nodes 1953################################################ 1954sub layout_array($$$\@) 1955{ 1956 # Starting point in X 1957 my $x_start = shift; 1958 1959 # Starting point in Y 1960 my $y_start = shift; 1961 1962 # largest Y value 1963 my $y_max = shift; 1964 1965 # The data 1966 my $re_array = shift; 1967 1968 foreach my $cur_node(@$re_array) { 1969 $cur_node->{x_loc} = $x_start; 1970 $cur_node->{y_loc} = $y_start + 1971 int(($y_max - 1972 $cur_node->{y_size})/2); 1973 $x_start += $cur_node->{x_size}; 1974 } 1975} 1976################################################ 1977# convert_re -- Convert @re_debug -> @format_re 1978# 1979# The formatted re node contains layout 1980# information as 1981# well as information on nodes contained 1982# inside the current one. 1983################################################ 1984sub convert_re() 1985{ 1986 # Clear out old data 1987 @format_re = (); 1988 1989 parse_node(0, \@format_re, undef, undef); 1990 # 1991 # Compute sizes of each node 1992 # 1993 my ($x_size, $y_size) = 1994 size_array(@format_re); 1995 1996 # 1997 # Compute the location of each node 1998 # 1999 layout_array(MARGIN, 2000 MARGIN, $y_size, 2001 @format_re 2002 ); 2003 return (MARGIN + $x_size, MARGIN + $y_size); 2004} 2005 2006############################################## 2007# draw_node_array -- draw an array of nodes 2008############################################## 2009sub draw_node_array($) 2010{ 2011 my $array = shift; 2012 # 2013 # Draw Nodes 2014 # 2015 foreach my $cur_node (@$array) { 2016 if (not defined( 2017 $draw_node{ 2018 $cur_node->{node}->{type}})) { 2019 2020 die("No draw function for ". 2021 "$cur_node->{node}->{type}"); 2022 } 2023 $draw_node{ 2024 $cur_node->{node}->{type}}( 2025 $cur_node 2026 ); 2027 } 2028 # 2029 # Loop through all the things 2030 # (except the last) and 2031 # draw arrows between them 2032 # 2033 for (my $index = 0; 2034 $index < $#$array; 2035 ++$index) { 2036 2037 my $from_x = $array->[$index]->{right_x}; 2038 my $from_y = $array->[$index]->{right_y}; 2039 2040 my $to_x = $array->[$index+1]->{left_x}; 2041 my $to_y = $array->[$index+1]->{left_y}; 2042 2043 arrow( 2044 $from_x, $from_y, 2045 $to_x, $to_y 2046 ); 2047 } 2048} 2049############################################## 2050# draw_re -- Draw the image 2051############################################## 2052sub draw_re() 2053{ 2054 # Draw the top level array 2055 # (Which recursively draws 2056 # all the enclosed elements) 2057 draw_node_array(\@format_re); 2058 # Make all the canvas visible 2059} 2060 2061############################################## 2062# find_node($state, $node_array) -- Find a node 2063# the parsed node tree 2064# 2065# Returns the location of the node 2066############################################## 2067sub find_node($$); 2068sub find_node($$) 2069{ 2070 # State (node number) to find 2071 my $state = shift; 2072 2073 my $array = shift; # The array to search 2074 2075 foreach my $cur_node (@$array) { 2076 if ($cur_node->{node}->{node} == 2077 $state) { 2078 2079 return ($cur_node->{x_loc}, 2080 $cur_node->{y_loc}); 2081 2082 } 2083 if (defined($cur_node->{children})) { 2084 # Get the x,y to return from 2085 # the children 2086 my ($ret_x, $ret_y) = 2087 find_node( 2088 $state, 2089 $cur_node->{children}); 2090 2091 if (defined($ret_x)) { 2092 return ($ret_x, $ret_y); 2093 } 2094 } 2095 if (defined($cur_node->{choices})) { 2096 my $choices = $cur_node->{choices}; 2097 foreach my $cur_choice (@$choices) { 2098 # Get the x,y to return from the 2099 # choice list 2100 my ($ret_x, $ret_y) = 2101 find_node( 2102 $state, $cur_choice); 2103 2104 if (defined($ret_x)) { 2105 return ($ret_x, $ret_y); 2106 } 2107 } 2108 } 2109 } 2110 return (undef, undef); 2111} 2112############################################## 2113# draw_progress($cur_line, $page) 2114# 2115# Draw a progress page 2116# 2117# Returns true if the page was drawn 2118############################################## 2119sub draw_progress($$$) 2120{ 2121 my $value = shift; # Value to check 2122 my $cur_line = shift;# Line we are processing 2123 my $page = shift; # Page number 2124 2125 # Check to see if this 2126 # is one of the progress lines 2127 if (substr($cur_line, 26, 1) ne '|') { 2128 return (0); # Not a good line 2129 } 2130 # Line containing the progress number 2131 # from the debug output 2132 my $progress_line = substr($cur_line, 0, 24); 2133 2134 # Location of the current state information 2135 my $state_line = substr($cur_line, 27); 2136 2137 # Extract progress number 2138 $progress_line =~ /^\s*(\d+)/; 2139 my $progress = $1; 2140 2141 # Extract state number 2142 $state_line =~ /^\s*(\d+)/; 2143 my $state = $1; 2144 2145 # Find the location of this node 2146 # on the graph 2147 my ($x_location, $y_location) = 2148 find_node($state, \@format_re); 2149 2150 if ($opt_d) { 2151 if (defined($x_location)) { 2152 print 2153 "node $state ". 2154 "($x_location, $y_location)\n"; 2155 } else { 2156 print "node $state not found\n"; 2157 } 2158 } 2159 # If the node is not graphable, 2160 # skip this step 2161 if (not defined($x_location)) { 2162 return (0); 2163 } 2164 # Create a new image with arrow 2165 my $new_image = 2166 GD::Image->newFromPngData( 2167 $image->png(0)); 2168 2169 # Create the arrow 2170 my $arrow = GD::Arrow::Full->new( 2171 -X1 => $x_location, 2172 -Y1 => $y_location, 2173 -X2 => $x_location - YELLOW_ARROW_SIZE, 2174 -Y2 => $y_location - YELLOW_ARROW_SIZE, 2175 -WIDTH => YELLOW_ARROW_WIDTH 2176 ); 2177 2178 $new_image->setThickness(1); 2179 2180 # Create some colors for 2181 # the new image 2182 my $new_color_yellow = 2183 $new_image->colorAllocate(255, 255, 0); 2184 2185 my $new_color_black = 2186 $new_image->colorAllocate(0,0,0); 2187 2188 # Make the arrow point 2189 # to the current step 2190 $new_image->filledPolygon( 2191 $arrow, $new_color_yellow); 2192 2193 $new_image->polygon( 2194 $arrow, $new_color_black); 2195 2196 # Get the size of the font we are using 2197 my $char_width = gdGiantFont->width; 2198 my $char_height = gdGiantFont->height; 2199 2200 $new_image->filledRectangle( 2201 PROGRESS_X, PROGRESS_Y, 2202 PROGRESS_X + 2203 $progress * $char_width, 2204 PROGRESS_Y + $char_height, 2205 $new_color_yellow 2206 ); 2207 2208 $new_image->string(gdGiantFont, 2209 PROGRESS_X, PROGRESS_Y, 2210 $value, $new_color_black); 2211 2212 # Generate the output file name 2213 my $out_file = 2214 sprintf($opt_o, $page); 2215 2216 open OUT_FILE, ">$out_file" or 2217 die("Could not open output". 2218 "file: $out_file"); 2219 2220 binmode OUT_FILE; 2221 print OUT_FILE $new_image->png(0); 2222 close OUT_FILE; 2223 return (1); 2224} 2225############################################## 2226# chart_progress -- Chart the progress of the 2227# execution of the RE 2228############################################## 2229sub chart_progress() 2230{ 2231 my $value = $ARGV[0]; # Value to check 2232 2233 # Value with ' quoted 2234 my $quote_value = $value; 2235 $quote_value =~ s/'/\\'/g; 2236 2237 # Regular expression 2238 my $quote_re = $current_re; 2239 $quote_re =~ s/\\/\\\\/g; 2240 2241 my $cmd = <<EOF ; 2242perl 2>&1 <<SHELL_EOF 2243use re 'debug'; 2244'$quote_value' =~ /$quote_re/; 2245SHELL_EOF 2246EOF 2247 2248 # The raw debug output 2249 my @raw_debug = `$cmd`; 2250 2251 # Go do to the part when the matching starts 2252 while (($#raw_debug > 0) and 2253 ($raw_debug[0] !~ /^Matching/)) { 2254 shift(@raw_debug); 2255 } 2256 shift(@raw_debug); 2257 2258 my $page = 1; # Current output page 2259 2260 foreach my $cur_line (@raw_debug) { 2261 # Skip other lines 2262 if (length($cur_line) < 27) { 2263 next; 2264 } 2265 if (draw_progress($value, 2266 $cur_line, $page)) { 2267 ++$page; 2268 } 2269 } 2270} 2271 2272 2273# -d -- Print RE debug output and draw output 2274# -o file -- specify output file (template) 2275# -x <min-x> 2276# -y <min-y> 2277my $status = getopts("do:x:y:"); 2278if ($status == 0) 2279{ 2280 usage(); 2281} 2282 2283if (not defined($opt_o)) { 2284 $opt_o = "re_graph_%02d.png"; 2285} 2286 2287if ($#ARGV == -1) { 2288 usage(); 2289} 2290$current_re = shift(@ARGV); 2291 2292parse_re(); 2293my ($x_size, $y_size) = convert_re(); 2294$x_size += MARGIN; 2295$y_size += MARGIN; 2296if (defined($opt_x)) { 2297 if ($opt_x > $x_size) { 2298 $x_size = $opt_x; 2299 } 2300} 2301if (defined($opt_y)) { 2302 if ($opt_y > $y_size) { 2303 $y_size = $opt_y; 2304 } 2305} 2306 2307$image = GD::Image->new($x_size, $y_size); 2308# Background color 2309$color_white = 2310 $image->colorAllocate(255,255,255); 2311$color_black = $image->colorAllocate(0,0,0); 2312$color_green = $image->colorAllocate(0, 255, 0); 2313$color_blue = $image->colorAllocate(0, 0, 255); 2314$color_light_green = 2315 $image->colorAllocate(0, 128, 0); 2316 2317draw_re(); 2318 2319$image->string(gdGiantFont, 2320 LABEL_LOC_X, LABEL_LOC_Y, 2321 "Regular Expression: /$current_re/", 2322 $color_black); 2323 2324my $out_file = sprintf($opt_o, 0); 2325open OUT_FILE, ">$out_file" or 2326 die("Could not open output file: $out_file"); 2327 2328binmode OUT_FILE; 2329print OUT_FILE $image->png(0); 2330close OUT_FILE; 2331 2332if ($#ARGV != -1) { 2333 chart_progress(); 2334} 2335 2336__END__ 2337 2338 GNU GENERAL PUBLIC LICENSE 2339 Version 2, June 1991 2340 2341 Copyright (C) 1989, 1991 Free Software Foundation, Inc. 2342 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 2343 Everyone is permitted to copy and distribute verbatim copies 2344 of this license document, but changing it is not allowed. 2345 2346 Preamble 2347 2348 The licenses for most software are designed to take away your 2349freedom to share and change it. By contrast, the GNU General Public 2350License is intended to guarantee your freedom to share and change free 2351software--to make sure the software is free for all its users. This 2352General Public License applies to most of the Free Software 2353Foundation's software and to any other program whose authors commit to 2354using it. (Some other Free Software Foundation software is covered by 2355the GNU Library General Public License instead.) You can apply it to 2356your programs, too. 2357 2358 When we speak of free software, we are referring to freedom, not 2359price. Our General Public Licenses are designed to make sure that you 2360have the freedom to distribute copies of free software (and charge for 2361this service if you wish), that you receive source code or can get it 2362if you want it, that you can change the software or use pieces of it 2363in new free programs; and that you know you can do these things. 2364 2365 To protect your rights, we need to make restrictions that forbid 2366anyone to deny you these rights or to ask you to surrender the rights. 2367These restrictions translate to certain responsibilities for you if you 2368distribute copies of the software, or if you modify it. 2369 2370 For example, if you distribute copies of such a program, whether 2371gratis or for a fee, you must give the recipients all the rights that 2372you have. You must make sure that they, too, receive or can get the 2373source code. And you must show them these terms so they know their 2374rights. 2375 2376 We protect your rights with two steps: (1) copyright the software, and 2377(2) offer you this license which gives you legal permission to copy, 2378distribute and/or modify the software. 2379 2380 Also, for each author's protection and ours, we want to make certain 2381that everyone understands that there is no warranty for this free 2382software. If the software is modified by someone else and passed on, we 2383want its recipients to know that what they have is not the original, so 2384that any problems introduced by others will not reflect on the original 2385authors' reputations. 2386 2387 Finally, any free program is threatened constantly by software 2388patents. We wish to avoid the danger that redistributors of a free 2389program will individually obtain patent licenses, in effect making the 2390program proprietary. To prevent this, we have made it clear that any 2391patent must be licensed for everyone's free use or not licensed at all. 2392 2393 The precise terms and conditions for copying, distribution and 2394modification follow. 2395 2396 GNU GENERAL PUBLIC LICENSE 2397 TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 2398 2399 0. This License applies to any program or other work which contains 2400a notice placed by the copyright holder saying it may be distributed 2401under the terms of this General Public License. The "Program", below, 2402refers to any such program or work, and a "work based on the Program" 2403means either the Program or any derivative work under copyright law: 2404that is to say, a work containing the Program or a portion of it, 2405either verbatim or with modifications and/or translated into another 2406language. (Hereinafter, translation is included without limitation in 2407the term "modification".) Each licensee is addressed as "you". 2408 2409Activities other than copying, distribution and modification are not 2410covered by this License; they are outside its scope. The act of 2411running the Program is not restricted, and the output from the Program 2412is covered only if its contents constitute a work based on the 2413Program (independent of having been made by running the Program). 2414Whether that is true depends on what the Program does. 2415 2416 1. You may copy and distribute verbatim copies of the Program's 2417source code as you receive it, in any medium, provided that you 2418conspicuously and appropriately publish on each copy an appropriate 2419copyright notice and disclaimer of warranty; keep intact all the 2420notices that refer to this License and to the absence of any warranty; 2421and give any other recipients of the Program a copy of this License 2422along with the Program. 2423 2424You may charge a fee for the physical act of transferring a copy, and 2425you may at your option offer warranty protection in exchange for a fee. 2426 2427 2. You may modify your copy or copies of the Program or any portion 2428of it, thus forming a work based on the Program, and copy and 2429distribute such modifications or work under the terms of Section 1 2430above, provided that you also meet all of these conditions: 2431 2432 a) You must cause the modified files to carry prominent notices 2433 stating that you changed the files and the date of any change. 2434 2435 b) You must cause any work that you distribute or publish, that in 2436 whole or in part contains or is derived from the Program or any 2437 part thereof, to be licensed as a whole at no charge to all third 2438 parties under the terms of this License. 2439 2440 c) If the modified program normally reads commands interactively 2441 when run, you must cause it, when started running for such 2442 interactive use in the most ordinary way, to print or display an 2443 announcement including an appropriate copyright notice and a 2444 notice that there is no warranty (or else, saying that you provide 2445 a warranty) and that users may redistribute the program under 2446 these conditions, and telling the user how to view a copy of this 2447 License. (Exception: if the Program itself is interactive but 2448 does not normally print such an announcement, your work based on 2449 the Program is not required to print an announcement.) 2450 2451These requirements apply to the modified work as a whole. If 2452identifiable sections of that work are not derived from the Program, 2453and can be reasonably considered independent and separate works in 2454themselves, then this License, and its terms, do not apply to those 2455sections when you distribute them as separate works. But when you 2456distribute the same sections as part of a whole which is a work based 2457on the Program, the distribution of the whole must be on the terms of 2458this License, whose permissions for other licensees extend to the 2459entire whole, and thus to each and every part regardless of who wrote it. 2460 2461Thus, it is not the intent of this section to claim rights or contest 2462your rights to work written entirely by you; rather, the intent is to 2463exercise the right to control the distribution of derivative or 2464collective works based on the Program. 2465 2466In addition, mere aggregation of another work not based on the Program 2467with the Program (or with a work based on the Program) on a volume of 2468a storage or distribution medium does not bring the other work under 2469the scope of this License. 2470 2471 3. You may copy and distribute the Program (or a work based on it, 2472under Section 2) in object code or executable form under the terms of 2473Sections 1 and 2 above provided that you also do one of the following: 2474 2475 a) Accompany it with the complete corresponding machine-readable 2476 source code, which must be distributed under the terms of Sections 2477 1 and 2 above on a medium customarily used for software interchange; or, 2478 2479 b) Accompany it with a written offer, valid for at least three 2480 years, to give any third party, for a charge no more than your 2481 cost of physically performing source distribution, a complete 2482 machine-readable copy of the corresponding source code, to be 2483 distributed under the terms of Sections 1 and 2 above on a medium 2484 customarily used for software interchange; or, 2485 2486 c) Accompany it with the information you received as to the offer 2487 to distribute corresponding source code. (This alternative is 2488 allowed only for noncommercial distribution and only if you 2489 received the program in object code or executable form with such 2490 an offer, in accord with Subsection b above.) 2491 2492The source code for a work means the preferred form of the work for 2493making modifications to it. For an executable work, complete source 2494code means all the source code for all modules it contains, plus any 2495associated interface definition files, plus the scripts used to 2496control compilation and installation of the executable. However, as a 2497special exception, the source code distributed need not include 2498anything that is normally distributed (in either source or binary 2499form) with the major components (compiler, kernel, and so on) of the 2500operating system on which the executable runs, unless that component 2501itself accompanies the executable. 2502 2503If distribution of executable or object code is made by offering 2504access to copy from a designated place, then offering equivalent 2505access to copy the source code from the same place counts as 2506distribution of the source code, even though third parties are not 2507compelled to copy the source along with the object code. 2508 2509 4. You may not copy, modify, sublicense, or distribute the Program 2510except as expressly provided under this License. Any attempt 2511otherwise to copy, modify, sublicense or distribute the Program is 2512void, and will automatically terminate your rights under this License. 2513However, parties who have received copies, or rights, from you under 2514this License will not have their licenses terminated so long as such 2515parties remain in full compliance. 2516 2517 5. You are not required to accept this License, since you have not 2518signed it. However, nothing else grants you permission to modify or 2519distribute the Program or its derivative works. These actions are 2520prohibited by law if you do not accept this License. Therefore, by 2521modifying or distributing the Program (or any work based on the 2522Program), you indicate your acceptance of this License to do so, and 2523all its terms and conditions for copying, distributing or modifying 2524the Program or works based on it. 2525 2526 6. Each time you redistribute the Program (or any work based on the 2527Program), the recipient automatically receives a license from the 2528original licensor to copy, distribute or modify the Program subject to 2529these terms and conditions. You may not impose any further 2530restrictions on the recipients' exercise of the rights granted herein. 2531You are not responsible for enforcing compliance by third parties to 2532this License. 2533 2534 7. If, as a consequence of a court judgment or allegation of patent 2535infringement or for any other reason (not limited to patent issues), 2536conditions are imposed on you (whether by court order, agreement or 2537otherwise) that contradict the conditions of this License, they do not 2538excuse you from the conditions of this License. If you cannot 2539distribute so as to satisfy simultaneously your obligations under this 2540License and any other pertinent obligations, then as a consequence you 2541may not distribute the Program at all. For example, if a patent 2542license would not permit royalty-free redistribution of the Program by 2543all those who receive copies directly or indirectly through you, then 2544the only way you could satisfy both it and this License would be to 2545refrain entirely from distribution of the Program. 2546 2547If any portion of this section is held invalid or unenforceable under 2548any particular circumstance, the balance of the section is intended to 2549apply and the section as a whole is intended to apply in other 2550circumstances. 2551 2552It is not the purpose of this section to induce you to infringe any 2553patents or other property right claims or to contest validity of any 2554such claims; this section has the sole purpose of protecting the 2555integrity of the free software distribution system, which is 2556implemented by public license practices. Many people have made 2557generous contributions to the wide range of software distributed 2558through that system in reliance on consistent application of that 2559system; it is up to the author/donor to decide if he or she is willing 2560to distribute software through any other system and a licensee cannot 2561impose that choice. 2562 2563This section is intended to make thoroughly clear what is believed to 2564be a consequence of the rest of this License. 2565 2566 8. If the distribution and/or use of the Program is restricted in 2567certain countries either by patents or by copyrighted interfaces, the 2568original copyright holder who places the Program under this License 2569may add an explicit geographical distribution limitation excluding 2570those countries, so that distribution is permitted only in or among 2571countries not thus excluded. In such case, this License incorporates 2572the limitation as if written in the body of this License. 2573 2574 9. The Free Software Foundation may publish revised and/or new versions 2575of the General Public License from time to time. Such new versions will 2576be similar in spirit to the present version, but may differ in detail to 2577address new problems or concerns. 2578 2579Each version is given a distinguishing version number. If the Program 2580specifies a version number of this License which applies to it and "any 2581later version", you have the option of following the terms and conditions 2582either of that version or of any later version published by the Free 2583Software Foundation. If the Program does not specify a version number of 2584this License, you may choose any version ever published by the Free Software 2585Foundation. 2586 2587 10. If you wish to incorporate parts of the Program into other free 2588programs whose distribution conditions are different, write to the author 2589to ask for permission. For software which is copyrighted by the Free 2590Software Foundation, write to the Free Software Foundation; we sometimes 2591make exceptions for this. Our decision will be guided by the two goals 2592of preserving the free status of all derivatives of our free software and 2593of promoting the sharing and reuse of software generally. 2594 2595 NO WARRANTY 2596 2597 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY 2598FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN 2599OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES 2600PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED 2601OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 2602MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS 2603TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE 2604PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, 2605REPAIR OR CORRECTION. 2606 2607 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING 2608WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR 2609REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, 2610INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING 2611OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED 2612TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY 2613YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER 2614PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE 2615POSSIBILITY OF SUCH DAMAGES. 2616 2617 END OF TERMS AND CONDITIONS 2618 2619 How to Apply These Terms to Your New Programs 2620 2621 If you develop a new program, and you want it to be of the greatest 2622possible use to the public, the best way to achieve this is to make it 2623free software which everyone can redistribute and change under these terms. 2624 2625 To do so, attach the following notices to the program. It is safest 2626to attach them to the start of each source file to most effectively 2627convey the exclusion of warranty; and each file should have at least 2628the "copyright" line and a pointer to where the full notice is found. 2629 2630 <one line to give the program's name and a brief idea of what it does.> 2631 Copyright (C) <year> <name of author> 2632 2633 This program is free software; you can redistribute it and/or modify 2634 it under the terms of the GNU General Public License as published by 2635 the Free Software Foundation; either version 2 of the License, or 2636 (at your option) any later version. 2637 2638 This program is distributed in the hope that it will be useful, 2639 but WITHOUT ANY WARRANTY; without even the implied warranty of 2640 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 2641 GNU General Public License for more details. 2642 2643 You should have received a copy of the GNU General Public License 2644 along with this program; if not, write to the Free Software 2645 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 2646 2647 2648Also add information on how to contact you by electronic and paper mail. 2649 2650If the program is interactive, make it output a short notice like this 2651when it starts in an interactive mode: 2652 2653 Gnomovision version 69, Copyright (C) year name of author 2654 Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. 2655 This is free software, and you are welcome to redistribute it 2656 under certain conditions; type `show c' for details. 2657 2658The hypothetical commands `show w' and `show c' should show the appropriate 2659parts of the General Public License. Of course, the commands you use may 2660be called something other than `show w' and `show c'; they could even be 2661mouse-clicks or menu items--whatever suits your program. 2662 2663You should also get your employer (if you work as a programmer) or your 2664school, if any, to sign a "copyright disclaimer" for the program, if 2665necessary. Here is a sample; alter the names: 2666 2667 Yoyodyne, Inc., hereby disclaims all copyright interest in the program 2668 `Gnomovision' (which makes passes at compilers) written by James Hacker. 2669 2670 <signature of Ty Coon>, 1 April 1989 2671 Ty Coon, President of Vice 2672 2673This General Public License does not permit incorporating your program into 2674proprietary programs. If your program is a subroutine library, you may 2675consider it more useful to permit linking proprietary applications with the 2676library. If this is what you want to do, use the GNU Library General 2677Public License instead of this License. 2678