PrettyPatch should handle "delta" patch mechanism in git binary patches
[WebKit-https.git] / Websites / bugs.webkit.org / PrettyPatch / PrettyPatch.rb
1 require 'cgi'
2 require 'diff'
3 require 'open3'
4 require 'open-uri'
5 require 'pp'
6 require 'set'
7 require 'tempfile'
8
9 module PrettyPatch
10
11 public
12
13     GIT_PATH = "git"
14
15     def self.prettify(string)
16         $last_prettify_file_count = -1
17         $last_prettify_part_count = { "remove" => 0, "add" => 0, "shared" => 0, "binary" => 0, "extract-error" => 0 }
18         string = normalize_line_ending(string)
19         str = HEADER + "\n"
20
21         # Just look at the first line to see if it is an SVN revision number as added
22         # by webkit-patch for git checkouts.
23         $svn_revision = 0
24         string.each_line do |line|
25             match = /^Subversion\ Revision: (\d*)$/.match(line)
26             unless match.nil?
27                 str += "<span class='revision'>" + match[1] + "</span>\n"
28                 $svn_revision = match[1].to_i;
29             end
30             break
31         end
32
33         fileDiffs = FileDiff.parse(string)
34
35         $last_prettify_file_count = fileDiffs.length
36         str += fileDiffs.collect{ |diff| diff.to_html }.join
37     end
38
39     def self.filename_from_diff_header(line)
40         DIFF_HEADER_FORMATS.each do |format|
41             match = format.match(line)
42             return match[1] unless match.nil?
43         end
44         nil
45     end
46
47     def self.diff_header?(line)
48         RELAXED_DIFF_HEADER_FORMATS.any? { |format| line =~ format }
49     end
50
51 private
52     DIFF_HEADER_FORMATS = [
53         /^Index: (.*)\r?$/,
54         /^diff --git "?a\/.+"? "?b\/(.+)"?\r?$/,
55         /^\+\+\+ ([^\t]+)(\t.*)?\r?$/
56     ]
57
58     RELAXED_DIFF_HEADER_FORMATS = [
59         /^Index:/,
60         /^diff/
61     ]
62
63     BINARY_FILE_MARKER_FORMAT = /^Cannot display: file marked as a binary type.$/
64
65     IMAGE_FILE_MARKER_FORMAT = /^svn:mime-type = image\/png$/
66
67     GIT_INDEX_MARKER_FORMAT = /^index ([0-9a-f]{40})\.\.([0-9a-f]{40})/
68
69     GIT_BINARY_FILE_MARKER_FORMAT = /^GIT binary patch$/
70
71     GIT_BINARY_PATCH_FORMAT = /^(literal|delta) \d+$/
72
73     GIT_LITERAL_FORMAT = /^literal \d+$/
74
75     GIT_DELTA_FORMAT = /^delta \d+$/
76
77     START_OF_BINARY_DATA_FORMAT = /^[0-9a-zA-Z\+\/=]{20,}/ # Assume 20 chars without a space is base64 binary data.
78
79     START_OF_SECTION_FORMAT = /^@@ -(\d+)(?:,(\d+))? \+(\d+)(?:,(\d+))? @@\s*(.*)/
80
81     START_OF_EXTENT_STRING = "%c" % 0
82     END_OF_EXTENT_STRING = "%c" % 1
83
84     # We won't search for intra-line diffs in lines longer than this length, to avoid hangs. See <http://webkit.org/b/56109>.
85     MAXIMUM_INTRALINE_DIFF_LINE_LENGTH = 10000
86
87     SMALLEST_EQUAL_OPERATION = 3
88
89     OPENSOURCE_TRAC_URL = "http://trac.webkit.org/"
90
91     OPENSOURCE_DIRS = Set.new %w[
92         Examples
93         LayoutTests
94         PerformanceTests
95         Source
96         Tools
97         WebKitLibraries
98         Websites
99     ]
100
101     def self.normalize_line_ending(s)
102         s.gsub /\r\n?/, "\n"
103     end
104
105     def self.find_url_and_path(file_path)
106         # Search file_path from the bottom up, at each level checking whether
107         # we've found a directory we know exists in the source tree.
108
109         dirname, basename = File.split(file_path)
110         dirname.split(/\//).reverse.inject(basename) do |path, directory|
111             path = directory + "/" + path
112
113             return [OPENSOURCE_TRAC_URL, path] if OPENSOURCE_DIRS.include?(directory)
114
115             path
116         end
117
118         [nil, file_path]
119     end
120
121     def self.linkifyFilename(filename)
122         url, pathBeneathTrunk = find_url_and_path(filename)
123
124         url.nil? ? filename : "<a href='#{url}browser/trunk/#{pathBeneathTrunk}'>#{filename}</a>"
125     end
126
127
128     HEADER =<<EOF
129 <style>
130 :link, :visited {
131     text-decoration: none;
132     border-bottom: 1px dotted;
133 }
134
135 :link {
136     color: #039;
137 }
138
139 .FileDiff {
140     background-color: #f8f8f8;
141     border: 1px solid #ddd;
142     font-family: monospace;
143     margin: 1em 0;
144 }
145
146 h1 {
147     color: #333;
148     font-family: sans-serif;
149     font-size: 1em;
150     margin-left: 0.5em;
151     display: table-cell;
152     width: 100%;
153     padding: 0.5em;
154 }
155
156 h1 :link, h1 :visited {
157     color: inherit;
158 }
159
160 h1 :hover {
161     color: #555;
162     background-color: #eee;
163 }
164
165 .DiffLinks {
166     float: right;
167 }
168
169 .FileDiffLinkContainer {
170     opacity: 0;
171     display: table-cell;
172     padding-right: 0.5em;
173     white-space: nowrap;
174 }
175
176 .DiffSection {
177     background-color: white;
178     border: solid #ddd;
179     border-width: 1px 0px;
180 }
181
182 .ExpansionLine, .LineContainer {
183     white-space: nowrap;
184 }
185
186 .sidebyside .DiffBlockPart.add:first-child {
187     float: right;
188 }
189
190 .LineSide:last-child {
191     float: right;
192 }
193
194 .LineSide,
195 .sidebyside .DiffBlockPart.remove,
196 .sidebyside .DiffBlockPart.add {
197     display:inline-block;
198     width:50%;
199     vertical-align: top;
200 }
201
202 .sidebyside .DiffBlockPart.remove .to,
203 .sidebyside .DiffBlockPart.add .from {
204     display: none;
205 }
206
207 .lineNumber, .expansionLineNumber {
208     border-bottom: 1px solid #998;
209     border-right: 1px solid #ddd;
210     color: #444;
211     display: inline-block;
212     padding: 1px 5px 0px 0px;
213     text-align: right;
214     vertical-align: bottom;
215     width: 3em;
216 }
217
218 .lineNumber {
219   background-color: #eed;
220 }
221
222 .expansionLineNumber {
223   background-color: #eee;
224 }
225
226 .text {
227     padding-left: 5px;
228     white-space: pre-wrap;
229     word-wrap: break-word;
230 }
231
232 .image {
233     border: 2px solid black;
234 }
235
236 .context, .context .lineNumber {
237     color: #849;
238     background-color: #fef;
239 }
240
241 .Line.add, .FileDiff .add {
242     background-color: #dfd;
243 }
244
245 .Line.add ins {
246     background-color: #9e9;
247     text-decoration: none;
248 }
249
250 .Line.remove, .FileDiff .remove {
251     background-color: #fdd;
252 }
253
254 .Line.remove del {
255     background-color: #e99;
256     text-decoration: none;
257 }
258
259 /* Support for inline comments */
260
261 .author {
262   font-style: italic;
263 }
264
265 .comment {
266   position: relative;
267 }
268
269 .comment textarea {
270   height: 6em;
271 }
272
273 .overallComments textarea {
274   height: 2em;
275 }
276
277 .comment textarea, .overallComments textarea {
278   display: block;
279   width: 100%;
280 }
281
282 .overallComments .open {
283   -webkit-transition: height .2s;
284   height: 4em;
285 }
286
287 #statusBubbleContainer.wrap {
288   display: block;
289 }
290
291 body {
292   margin-bottom: 40px;
293 }
294
295 #toolbar {
296   display: -webkit-box;
297   display: -moz-box;
298   padding: 3px;
299   left: 0;
300   right: 0;
301   border: 1px solid #ddd;
302   background-color: #eee;
303   font-family: sans-serif;
304   position: fixed;
305 }
306
307 #toolbar.anchored {
308   bottom: 0;
309 }
310
311 #toolbar .actions {
312   float: right;
313 }
314
315 .winter {
316   position: fixed;
317   z-index: 5;
318   left: 0;
319   right: 0;
320   top: 0;
321   bottom: 0;
322   background-color: black;
323   opacity: 0.8;
324 }
325
326 .inactive {
327   display: none;
328 }
329
330 .lightbox {
331   position: fixed;
332   z-index: 6;
333   left: 10%;
334   right: 10%;
335   top: 10%;
336   bottom: 10%;
337   background: white;
338 }
339
340 .lightbox iframe {
341   width: 100%;
342   height: 100%;
343 }
344
345 .commentContext .lineNumber {
346   background-color: yellow;
347 }
348
349 .selected .lineNumber {
350   background-color: #69F;
351   border-bottom-color: #69F;
352   border-right-color: #69F;
353 }
354
355 .ExpandLinkContainer {
356   opacity: 0;
357   border-top: 1px solid #ddd;
358   border-bottom: 1px solid #ddd;
359 }
360
361 .ExpandArea {
362   margin: 0;
363 }
364
365 .ExpandText {
366   margin-left: 0.67em;
367 }
368
369 .LinkContainer {
370   font-family: sans-serif;
371   font-size: small;
372   font-style: normal;
373   -webkit-transition: opacity 0.5s;
374 }
375
376 .LinkContainer a {
377   border: 0;
378 }
379
380 .LinkContainer a:after {
381   content: " | ";
382   color: black;
383 }
384
385 .LinkContainer a:last-of-type:after {
386   content: "";
387 }
388
389 .help {
390  color: gray;
391  font-style: italic;
392 }
393
394 #message {
395   font-size: small;
396   font-family: sans-serif;
397 }
398
399 .commentStatus {
400   font-style: italic;
401 }
402
403 .comment, .previousComment, .frozenComment {
404   background-color: #ffd;
405 }
406
407 .overallComments {
408   -webkit-box-flex: 1;
409   -moz-box-flex: 1;
410   margin-right: 3px;
411 }
412
413 .previousComment, .frozenComment {
414   border: inset 1px;
415   padding: 5px;
416   white-space: pre-wrap;
417 }
418
419 .comment button {
420   width: 6em;
421 }
422
423 div:focus {
424   outline: 1px solid blue;
425   outline-offset: -1px;
426 }
427
428 .statusBubble {
429   /* The width/height get set to the bubble contents via postMessage on browsers that support it. */
430   width: 450px;
431   height: 20px;
432   margin: 2px 2px 0 0;
433   border: none;
434   vertical-align: middle;
435 }
436
437 .pseudo_resize_event_iframe {
438   height: 10%;
439   width: 10%;
440   position: absolute;
441   top: -11%;
442 }
443
444 .revision {
445   display: none;
446 }
447
448 .autosave-state {
449   position: absolute;
450   right: 0;
451   top: -1.3em;
452   padding: 0 3px;
453   outline: 1px solid #DDD;
454   color: #8FDF5F;
455   font-size: small;   
456   background-color: #EEE;
457 }
458
459 .autosave-state:empty {
460   outline: 0px;
461 }
462 .autosave-state.saving {
463   color: #E98080;
464 }
465
466 .clear_float {
467     clear: both;
468 }
469 </style>
470 <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js"></script> 
471 <script src="code-review.js?version=42"></script>
472 EOF
473
474     def self.revisionOrDescription(string)
475         case string
476         when /\(revision \d+\)/
477             /\(revision (\d+)\)/.match(string)[1]
478         when /\(.*\)/
479             /\((.*)\)/.match(string)[1]
480         end
481     end
482
483     def self.has_image_suffix(filename)
484         filename =~ /\.(png|jpg|gif)$/
485     end
486
487     class FileDiff
488         def initialize(lines)
489             @filename = PrettyPatch.filename_from_diff_header(lines[0].chomp)
490             startOfSections = 1
491             for i in 0...lines.length
492                 case lines[i]
493                 when /^--- /
494                     @from = PrettyPatch.revisionOrDescription(lines[i])
495                 when /^\+\+\+ /
496                     @filename = PrettyPatch.filename_from_diff_header(lines[i].chomp) if @filename.nil?
497                     @to = PrettyPatch.revisionOrDescription(lines[i])
498                     startOfSections = i + 1
499                     break
500                 when BINARY_FILE_MARKER_FORMAT
501                     @binary = true
502                     if (IMAGE_FILE_MARKER_FORMAT.match(lines[i + 1]) or PrettyPatch.has_image_suffix(@filename)) then
503                         @image = true
504                         startOfSections = i + 2
505                         for x in startOfSections...lines.length
506                             # Binary diffs often have property changes listed before the actual binary data.  Skip them.
507                             if START_OF_BINARY_DATA_FORMAT.match(lines[x]) then
508                                 startOfSections = x
509                                 break
510                             end
511                         end
512                     end
513                     break
514                 when GIT_INDEX_MARKER_FORMAT
515                     @git_indexes = [$1, $2]
516                 when GIT_BINARY_FILE_MARKER_FORMAT
517                     @binary = true
518                     if (GIT_BINARY_PATCH_FORMAT.match(lines[i + 1]) and PrettyPatch.has_image_suffix(@filename)) then
519                         @git_image = true
520                         startOfSections = i + 1
521                     end
522                     break
523                 end
524             end
525             lines_with_contents = lines[startOfSections...lines.length]
526             @sections = DiffSection.parse(lines_with_contents) unless @binary
527             if @image and not lines_with_contents.empty?
528                 @image_url = "data:image/png;base64," + lines_with_contents.join
529                 @image_checksum = FileDiff.read_checksum_from_png(lines_with_contents.join.unpack("m").join)
530             elsif @git_image
531                 begin
532                     raise "index line is missing" unless @git_indexes
533
534                     chunks = nil
535                     for i in 0...lines_with_contents.length
536                         if lines_with_contents[i] =~ /^$/
537                             chunks = [lines_with_contents[i + 1 .. -1], lines_with_contents[0 .. i]]
538                             break
539                         end
540                     end
541
542                     raise "no binary chunks" unless chunks
543
544                     from_filepath = FileDiff.extract_contents_of_from_revision(@filename, chunks[0], @git_indexes[0])
545                     to_filepath = FileDiff.extract_contents_of_to_revision(@filename, chunks[1], @git_indexes[1], from_filepath, @git_indexes[0])
546                     filepaths = from_filepath, to_filepath
547
548                     binary_contents = filepaths.collect { |filepath| File.exists?(filepath) ? File.read(filepath) : nil }
549
550                     @image_urls = binary_contents.collect { |content| (content and not content.empty?) ? "data:image/png;base64," + [content].pack("m") : nil }
551                     @image_checksums = binary_contents.collect { |content| FileDiff.read_checksum_from_png(content) }
552                 rescue
553                     $last_prettify_part_count["extract-error"] += 1
554                     @image_error = "Exception raised during decoding git binary patch:<pre>#{CGI.escapeHTML($!.to_s + "\n" + $!.backtrace.join("\n"))}</pre>"
555                 ensure
556                     File.unlink(from_filepath) if (from_filepath and File.exists?(from_filepath))
557                     File.unlink(to_filepath) if (to_filepath and File.exists?(to_filepath))
558                 end
559             end
560             nil
561         end
562
563         def image_to_html
564             if not @image_url then
565                 return "<span class='text'>Image file removed</span>"
566             end
567             image_snippet = "<img class='image' src='" + @image_url + "' />"
568             if not @image_checksum then
569                 return image_snippet
570             end
571             return "<p>" + @image_checksum + "</p>" + image_snippet
572         end
573
574         def to_html
575             str = "<div class='FileDiff'>\n"
576             str += "<h1>#{PrettyPatch.linkifyFilename(@filename)}</h1>\n"
577             if @image then
578                 str += self.image_to_html
579             elsif @git_image then
580                 if @image_error
581                     str += @image_error
582                 else
583                     for i in (0...2)
584                         image_url = @image_urls[i]
585                         image_checksum = @image_checksums[i]
586
587                         style = ["remove", "add"][i]
588                         str += "<p class=\"#{style}\">"
589
590                         if image_checksum
591                             str += image_checksum + "<br>"
592                         end
593                         if image_url
594                             str += "<img class='image' src='" + image_url + "' />"
595                         else
596                             str += ["</p>Added", "</p>Removed"][i]
597                         end
598                     end
599                 end
600             elsif @binary then
601                 $last_prettify_part_count["binary"] += 1
602                 str += "<span class='text'>Binary file, nothing to see here</span>"
603             else
604                 str += @sections.collect{ |section| section.to_html }.join("<br>\n") unless @sections.nil?
605             end
606
607             if @from then
608                 str += "<span class='revision'>" + @from + "</span>"
609             end
610
611             str += "</div>\n"
612         end
613
614         def self.parse(string)
615             haveSeenDiffHeader = false
616             linesForDiffs = []
617             string.each_line do |line|
618                 if (PrettyPatch.diff_header?(line))
619                     linesForDiffs << []
620                     haveSeenDiffHeader = true
621                 elsif (!haveSeenDiffHeader && line =~ /^--- /)
622                     linesForDiffs << []
623                     haveSeenDiffHeader = false
624                 end
625                 linesForDiffs.last << line unless linesForDiffs.last.nil?
626             end
627
628             linesForDiffs.collect { |lines| FileDiff.new(lines) }
629         end
630
631         def self.read_checksum_from_png(png_bytes)
632             match = png_bytes && png_bytes.match(/tEXtchecksum\0([a-fA-F0-9]{32})/)
633             match ? match[1] : nil
634         end
635
636         def self.git_new_file_binary_patch(filename, encoded_chunk, git_index)
637             return <<END
638 diff --git a/#{filename} b/#{filename}
639 new file mode 100644
640 index 0000000000000000000000000000000000000000..#{git_index}
641 GIT binary patch
642 #{encoded_chunk.join("")}literal 0
643 HcmV?d00001
644
645 END
646         end
647
648         def self.git_changed_file_binary_patch(to_filename, from_filename, encoded_chunk, to_git_index, from_git_index)
649             return <<END
650 diff --git a/#{from_filename} b/#{to_filename}
651 copy from #{from_filename}
652 +++ b/#{to_filename}
653 index #{from_git_index}..#{to_git_index}
654 GIT binary patch
655 #{encoded_chunk.join("")}literal 0
656 HcmV?d00001
657
658 END
659         end
660
661         def self.get_svn_uri(repository_path)
662             "http://svn.webkit.org/repository/webkit/!svn/bc/" + $svn_revision.to_s + "/trunk/" + (repository_path)
663         end
664
665         def self.get_new_temp_filepath_and_name
666             tempfile = Tempfile.new("PrettyPatch")
667             filepath = tempfile.path + '.bin'
668             filename = File.basename(filepath)
669             return filepath, filename
670         end
671
672         def self.download_from_revision_from_svn(repository_path)
673             filepath, filename = get_new_temp_filepath_and_name
674             svn_uri = get_svn_uri(repository_path)
675             open(filepath, 'wb') do |to_file|
676                 to_file << open(svn_uri) { |from_file| from_file.read }
677             end
678             return filepath
679         end
680
681         def self.run_git_apply_on_patch(output_filepath, patch)
682             # Apply the git binary patch using git-apply.
683             cmd = GIT_PATH + " apply --directory=" + File.dirname(output_filepath)
684             stdin, stdout, stderr = *Open3.popen3(cmd)
685             begin
686                 stdin.puts(patch)
687                 stdin.close
688
689                 error = stderr.read
690                 if error != ""
691                     error = "Error running " + cmd + "\n" + "with patch:\n" + patch[0..500] + "...\n" + error
692                 end
693                 raise error if error != ""
694             ensure
695                 stdin.close unless stdin.closed?
696                 stdout.close
697                 stderr.close
698             end
699         end
700
701         def self.extract_contents_from_git_binary_literal_chunk(encoded_chunk, git_index)
702             filepath, filename = get_new_temp_filepath_and_name
703             patch = FileDiff.git_new_file_binary_patch(filename, encoded_chunk, git_index)
704             run_git_apply_on_patch(filepath, patch)
705             return filepath
706         end
707
708         def self.extract_contents_from_git_binary_delta_chunk(from_filepath, from_git_index, encoded_chunk, to_git_index)
709             to_filepath, to_filename = get_new_temp_filepath_and_name
710             from_filename = File.basename(from_filepath)
711             patch = FileDiff.git_changed_file_binary_patch(to_filename, from_filename, encoded_chunk, to_git_index, from_git_index)
712             run_git_apply_on_patch(to_filepath, patch)
713             return to_filepath
714         end
715
716         def self.extract_contents_of_from_revision(repository_path, encoded_chunk, git_index)
717             # For literal encoded, simply reconstruct.
718             if GIT_LITERAL_FORMAT.match(encoded_chunk[0])
719                 return extract_contents_from_git_binary_literal_chunk(encoded_chunk, git_index)
720             end
721             #  For delta encoded, download from svn.
722             if GIT_DELTA_FORMAT.match(encoded_chunk[0])
723                 return download_from_revision_from_svn(repository_path)
724             end
725             raise "Error: unknown git patch encoding"
726         end
727
728         def self.extract_contents_of_to_revision(repository_path, encoded_chunk, git_index, from_filepath, from_git_index)
729             # For literal encoded, simply reconstruct.
730             if GIT_LITERAL_FORMAT.match(encoded_chunk[0])
731                 return extract_contents_from_git_binary_literal_chunk(encoded_chunk, git_index)
732             end
733             # For delta encoded, reconstruct using delta and previously constructed 'from' revision.
734             if GIT_DELTA_FORMAT.match(encoded_chunk[0])
735                 return extract_contents_from_git_binary_delta_chunk(from_filepath, from_git_index, encoded_chunk, git_index)
736             end
737             raise "Error: unknown git patch encoding"
738         end
739     end
740
741     class DiffBlock
742         attr_accessor :parts
743
744         def initialize(container)
745             @parts = []
746             container << self
747         end
748
749         def to_html
750             str = "<div class='DiffBlock'>\n"
751             str += @parts.collect{ |part| part.to_html }.join
752             str += "<div class='clear_float'></div></div>\n"
753         end
754     end
755
756     class DiffBlockPart
757         attr_reader :className
758         attr :lines
759
760         def initialize(className, container)
761             $last_prettify_part_count[className] += 1
762             @className = className
763             @lines = []
764             container.parts << self
765         end
766
767         def to_html
768             str = "<div class='DiffBlockPart %s'>\n" % @className
769             str += @lines.collect{ |line| line.to_html }.join
770             # Don't put white-space after this so adjacent inline-block DiffBlockParts will not wrap.
771             str += "</div>"
772         end
773     end
774
775     class DiffSection
776         def initialize(lines)
777             lines.length >= 1 or raise "DiffSection.parse only received %d lines" % lines.length
778
779             matches = START_OF_SECTION_FORMAT.match(lines[0])
780
781             if matches
782                 from, to = [matches[1].to_i, matches[3].to_i]
783                 if matches[2] and matches[4]
784                     from_end = from + matches[2].to_i
785                     to_end = to + matches[4].to_i
786                 end
787             end
788
789             @blocks = []
790             diff_block = nil
791             diff_block_part = nil
792
793             for line in lines[1...lines.length]
794                 startOfLine = line =~ /^[-\+ ]/ ? 1 : 0
795                 text = line[startOfLine...line.length].chomp
796                 case line[0]
797                 when ?-
798                     if (diff_block_part.nil? or diff_block_part.className != 'remove')
799                         diff_block = DiffBlock.new(@blocks)
800                         diff_block_part = DiffBlockPart.new('remove', diff_block)
801                     end
802
803                     diff_block_part.lines << CodeLine.new(from, nil, text)
804                     from += 1 unless from.nil?
805                 when ?+
806                     if (diff_block_part.nil? or diff_block_part.className != 'add')
807                         # Put add lines that immediately follow remove lines into the same DiffBlock.
808                         if (diff_block.nil? or diff_block_part.className != 'remove')
809                             diff_block = DiffBlock.new(@blocks)
810                         end
811
812                         diff_block_part = DiffBlockPart.new('add', diff_block)
813                     end
814
815                     diff_block_part.lines << CodeLine.new(nil, to, text)
816                     to += 1 unless to.nil?
817                 else
818                     if (diff_block_part.nil? or diff_block_part.className != 'shared')
819                         diff_block = DiffBlock.new(@blocks)
820                         diff_block_part = DiffBlockPart.new('shared', diff_block)
821                     end
822
823                     diff_block_part.lines << CodeLine.new(from, to, text)
824                     from += 1 unless from.nil?
825                     to += 1 unless to.nil?
826                 end
827
828                 break if from_end and to_end and from == from_end and to == to_end
829             end
830
831             changes = [ [ [], [] ] ]
832             for block in @blocks
833                 for block_part in block.parts
834                     for line in block_part.lines
835                         if (!line.fromLineNumber.nil? and !line.toLineNumber.nil?) then
836                             changes << [ [], [] ]
837                             next
838                         end
839                         changes.last.first << line if line.toLineNumber.nil?
840                         changes.last.last << line if line.fromLineNumber.nil?
841                     end
842                 end
843             end
844
845             for change in changes
846                 next unless change.first.length == change.last.length
847                 for i in (0...change.first.length)
848                     from_text = change.first[i].text
849                     to_text = change.last[i].text
850                     next if from_text.length > MAXIMUM_INTRALINE_DIFF_LINE_LENGTH or to_text.length > MAXIMUM_INTRALINE_DIFF_LINE_LENGTH
851                     raw_operations = HTMLDiff::DiffBuilder.new(from_text, to_text).operations
852                     operations = []
853                     back = 0
854                     raw_operations.each_with_index do |operation, j|
855                         if operation.action == :equal and j < raw_operations.length - 1
856                            length = operation.end_in_new - operation.start_in_new
857                            if length < SMALLEST_EQUAL_OPERATION
858                                back = length
859                                next
860                            end
861                         end
862                         operation.start_in_old -= back
863                         operation.start_in_new -= back
864                         back = 0
865                         operations << operation
866                     end
867                     change.first[i].operations = operations
868                     change.last[i].operations = operations
869                 end
870             end
871
872             @blocks.unshift(ContextLine.new(matches[5])) unless matches.nil? || matches[5].empty?
873         end
874
875         def to_html
876             str = "<div class='DiffSection'>\n"
877             str += @blocks.collect{ |block| block.to_html }.join
878             str += "</div>\n"
879         end
880
881         def self.parse(lines)
882             linesForSections = lines.inject([[]]) do |sections, line|
883                 sections << [] if line =~ /^@@/
884                 sections.last << line
885                 sections
886             end
887
888             linesForSections.delete_if { |lines| lines.nil? or lines.empty? }
889             linesForSections.collect { |lines| DiffSection.new(lines) }
890         end
891     end
892
893     class Line
894         attr_reader :fromLineNumber
895         attr_reader :toLineNumber
896         attr_reader :text
897
898         def initialize(from, to, text)
899             @fromLineNumber = from
900             @toLineNumber = to
901             @text = text
902         end
903
904         def text_as_html
905             CGI.escapeHTML(text)
906         end
907
908         def classes
909             lineClasses = ["Line", "LineContainer"]
910             lineClasses << ["add"] unless @toLineNumber.nil? or !@fromLineNumber.nil?
911             lineClasses << ["remove"] unless @fromLineNumber.nil? or !@toLineNumber.nil?
912             lineClasses
913         end
914
915         def to_html
916             markedUpText = self.text_as_html
917             str = "<div class='%s'>\n" % self.classes.join(' ')
918             str += "<span class='from lineNumber'>%s</span><span class='to lineNumber'>%s</span>" %
919                    [@fromLineNumber.nil? ? '&nbsp;' : @fromLineNumber,
920                     @toLineNumber.nil? ? '&nbsp;' : @toLineNumber] unless @fromLineNumber.nil? and @toLineNumber.nil?
921             str += "<span class='text'>%s</span>\n" % markedUpText
922             str += "</div>\n"
923         end
924     end
925
926     class CodeLine < Line
927         attr :operations, true
928
929         def text_as_html
930             html = []
931             tag = @fromLineNumber.nil? ? "ins" : "del"
932             if @operations.nil? or @operations.empty?
933                 return CGI.escapeHTML(@text)
934             end
935             @operations.each do |operation|
936                 start = @fromLineNumber.nil? ? operation.start_in_new : operation.start_in_old
937                 eend = @fromLineNumber.nil? ? operation.end_in_new : operation.end_in_old
938                 escaped_text = CGI.escapeHTML(@text[start...eend])
939                 if eend - start === 0 or operation.action === :equal
940                     html << escaped_text
941                 else
942                     html << "<#{tag}>#{escaped_text}</#{tag}>"
943                 end
944             end
945             html.join
946         end
947     end
948
949     class ContextLine < Line
950         def initialize(context)
951             super("@", "@", context)
952         end
953
954         def classes
955             super << "context"
956         end
957     end
958 end