buildscripts/output-distance.py

   1 #!@TARGET_PYTHON@
   2 import sys
   3 import optparse
   4
   5 import safeeval
   6
   7
   8 X_AXIS = 0
   9 Y_AXIS = 1
  10 INFTY = 1e6
  11
  12 OUTPUT_EXPRESSION_PENALTY = 100
  13 ORPHAN_GROB_PENALTY = 1000
  14
  15 def max_distance (x1, x2):
  16     dist = 0.0
  17
  18     for (p,q) in zip (x1, x2):
  19         dist = max (abs (p-q), dist)
  20
  21     return dist
  22
  23
  24 empty_interval = (INFTY, -INFTY)
  25 empty_bbox = (empty_interval, empty_interval)
  26
  27 def interval_length (i):
  28     return max (i[1]-i[0], 0)
  29
  30 def interval_union (i1, i2):
  31     return (min (i1[0], i2[0]),
  32             max (i1[1], i2[1]))
  33
  34 def interval_intersect (i1, i2):
  35     return (max (i1[0], i2[0]),
  36             min (i1[1], i2[1]))
  37
  38 def bbox_union (b1, b2):
  39     return (interval_union (b1[X_AXIS], b2[X_AXIS]),
  40             interval_union (b2[Y_AXIS], b2[Y_AXIS]))
  41
  42 def bbox_intersection (b1, b2):
  43     return (interval_intersect (b1[X_AXIS], b2[X_AXIS]),
  44             interval_intersect (b2[Y_AXIS], b2[Y_AXIS]))
  45
  46 def bbox_area (b):
  47     return interval_length (b[X_AXIS]) * interval_length (b[Y_AXIS])
  48
  49 def bbox_diameter (b):
  50     return max (interval_length (b[X_AXIS]),
  51                 interval_length (b[Y_AXIS]))
  52
  53
  54 def difference_area (a, b):
  55     return bbox_area (a) - bbox_area (bbox_intersection (a,b))
  56
  57 class GrobSignature:
  58     def __init__ (self, exp_list):
  59         (self.name, self.origin, bbox_x,
  60          bbox_y, self.output_expression) = tuple (exp_list)
  61
  62         self.bbox = (bbox_x, bbox_y)
  63         self.centroid = (bbox_x[0] + bbox_x[1], bbox_y[0] + bbox_y[1])
  64
  65     def __repr__ (self):
  66         return '%s: (%.2f,%.2f), (%.2f,%.2f)\n' % (self.name,
  67                                                  self.bbox[0][0],
  68                                                  self.bbox[0][1],
  69                                                  self.bbox[1][0],
  70                                                  self.bbox[1][1])
  71
  72     def axis_centroid (self, axis):
  73         return apply (sum, self.bbox[axis])  / 2
  74
  75     def centroid_distance (self, other, scale):
  76         return max_distance (self.centroid, other.centroid) / scale
  77
  78     def bbox_distance (self, other):
  79         divisor = bbox_area (self.bbox) + bbox_area (other.bbox)
  80
  81         if divisor:
  82             return (difference_area (self.bbox, other.bbox) +
  83                     difference_area (other.bbox, self.bbox)) / divisor
  84         else:
  85             return 0.0
  86
  87     def expression_distance (self, other):
  88         if self.output_expression == other.output_expression:
  89             return 0.0
  90         else:
  91             return OUTPUT_EXPRESSION_PENALTY
  92
  93     def distance(self, other, max_distance):
  94         return (self.expression_distance (other)
  95                 + self.centroid_distance (other, max_distance)
  96                 + self.bbox_distance (other))
  97
  98 class SystemSignature:
  99     def __init__ (self, grob_sigs):
 100         d = {}
 101         for g in grob_sigs:
 102             val = d.setdefault (g.name, [])
 103             val += [g]
 104
 105         self.grob_dict = d
 106         self.set_all_bbox (grob_sigs)
 107
 108     def set_all_bbox (self, grobs):
 109         self.bbox = empty_bbox
 110         for g in grobs:
 111             self.bbox = bbox_union (g.bbox, self.bbox)
 112
 113     def closest (self, grob_name, centroid):
 114         min_d = INFTY
 115         min_g = None
 116         try:
 117             grobs = self.grob_dict[grob_name]
 118
 119             for g in grobs:
 120                 d = max_distance (g.centroid, centroid)
 121                 if d < min_d:
 122                     min_d = d
 123                     min_g = g
 124
 125
 126             return min_g
 127
 128         except KeyError:
 129             return None
 130     def grobs (self):
 131         return reduce (lambda x,y: x+y, self.grob_dict.values(), [])
 132
 133 class SystemLink:
 134     def __init__ (self, system1, system2):
 135         self.system1 = system1
 136         self.system2 = system2
 137
 138         self.link_list_dict = {}
 139         self.back_link_dict = {}
 140
 141         for g in system1.grobs ():
 142             closest = system2.closest (g.name, g.centroid)
 143
 144             self.link_list_dict.setdefault (closest, [])
 145             self.link_list_dict[closest].append (g)
 146             self.back_link_dict[g] = closest
 147
 148     def distance (self):
 149         d = 0.0
 150
 151         scale = max (bbox_diameter (self.system1.bbox),
 152                      bbox_diameter (self.system2.bbox))
 153
 154         for (g1,g2) in self.back_link_dict.items ():
 155             if g2 == None:
 156                 d += ORPHAN_GROB_PENALTY
 157             else:
 158                 d += g1.distance (g2, scale)
 159
 160         for (g1,g2s) in self.link_list_dict.items ():
 161             if len (g2s) != 1:
 162                 d += ORPHAN_GROB_PENALTY
 163
 164         return d
 165
 166 ################################################################
 167 # Files/directories
 168
 169 import glob
 170 import shutil
 171 import re
 172
 173 def read_signature_file (name):
 174     print 'reading', name
 175     exp_str = ("[%s]" % open (name).read ())
 176     entries = safeeval.safe_eval (exp_str)
 177
 178     grob_sigs = [GrobSignature (e) for e in entries]
 179     sig = SystemSignature (grob_sigs)
 180     return sig
 181
 182
 183 def compare_signature_files (f1, f2):
 184     s1 = read_signature_file (f1)
 185     s2 = read_signature_file (f2)
 186
 187     return SystemLink (s1, s2).distance ()
 188
 189 def paired_files (dir1, dir2, pattern):
 190     """
 191     Search DIR1 and DIR2 for PATTERN.
 192
 193     Return (PAIRED, MISSING-FROM-2, MISSING-FROM-1)
 194
 195     """
 196
 197     files1 = dict ((os.path.split (f)[1], 1) for f in glob.glob (dir1 + '/' + pattern))
 198     files2 = dict ((os.path.split (f)[1], 1) for f in glob.glob (dir2 + '/' + pattern))
 199
 200     pairs = []
 201     missing = []
 202     for f in files1.keys ():
 203         try:
 204             files2.pop (f)
 205             pairs.append (f)
 206         except KeyError:
 207             missing.append (f)
 208
 209     return (pairs, files2.keys (), missing)
 210
 211 class ComparisonData:
 212     def __init__ (self):
 213         self.result_dict = {}
 214         self.missing = []
 215         self.added = []
 216
 217     def compare_trees (self, dir1, dir2):
 218         self.compare_directories (dir1, dir2)
 219
 220         (root, dirs, files) = os.walk (dir1).next ()
 221         for d in dirs:
 222             d1 = os.path.join (dir1, d)
 223             d2 = os.path.join (dir2, d)
 224
 225             if os.path.islink (d1) or os.path.islink (d2):
 226                 continue
 227
 228             if os.path.isdir (d2):
 229                 self.compare_trees (d1, d2)
 230
 231     def compare_directories (self, dir1, dir2):
 232
 233         (paired, m1, m2) = paired_files (dir1, dir2, '*.signature')
 234
 235         self.missing += [(dir1, m) for m in m1]
 236         self.added += [(dir2, m) for m in m2]
 237
 238         for p in paired:
 239             f2 = dir2 +  '/' + p
 240             f1 = dir1 +  '/' + p
 241             distance = compare_signature_files (f1, f2)
 242             self.result_dict[f2] = (distance, f1)
 243
 244     def create_text_result_page (self, dir1, dir2):
 245         self.write_text_result_page (dir2 + '/' + os.path.split (dir1)[1] + '.txt')
 246
 247     def write_text_result_page (self, filename):
 248         print 'writing "%s"' % filename
 249         out = None
 250         if filename == '':
 251             out = sys.stdout
 252         else:
 253             out = open (filename, 'w')
 254
 255         results = [(score, oldfile, file) for (file, (score, oldfile)) in self.result_dict.items ()]
 256         results.sort ()
 257         results.reverse ()
 258
 259         for (s, oldfile, f) in results:
 260             out.write ('%-30f %-20s\n' % (s, f))
 261
 262         for (dir, file) in self.missing:
 263             out.write ('%10s%-20s %s\n' % ('', 'missing',os.path.join (dir, file)))
 264         for (dir, file) in self.added:
 265             out.write ('%20s%-10s %s\n' % ('','added', os.path.join (dir, file)))
 266
 267     def print_results (self):
 268         self.write_text_result_page ('')
 269
 270     def create_html_result_page (self, dir1, dir2):
 271         dir1 = dir1.replace ('//', '/')
 272         dir2 = dir2.replace ('//', '/')
 273
 274         threshold = 1.0
 275
 276         results = [(score, oldfile, file) for (file, (score, oldfile)) in self.result_dict.items ()
 277                    if score > threshold]
 278
 279         results.sort ()
 280         results.reverse ()
 281
 282         html = ''
 283         old_prefix = os.path.split (dir1)[1]
 284
 285         dest_dir = os.path.join (dir2, old_prefix)
 286         shutil.rmtree  (dest_dir, ignore_errors=True)
 287         os.mkdir (dest_dir)
 288         for (score, oldfile, newfile) in  results:
 289             old_base = re.sub ("-[0-9]+.signature", '', os.path.split (oldfile)[1])
 290             new_base = re.sub ("-[0-9]+.signature", '', newfile)
 291
 292             for ext in 'png', 'ly':
 293                 shutil.copy2 (old_base + '.' + ext, dest_dir)
 294
 295             img_1 = os.path.join (old_prefix, old_base + '.png')
 296             ly_1 = os.path.join (old_prefix, old_base + '.ly')
 297
 298             img_2 = new_base.replace (dir2, '') + '.png'
 299             img_2 = re.sub ("^/*", '', img_2)
 300
 301             ly_2 = img_2.replace ('.png','.ly')
 302
 303             def img_cell (ly, img):
 304                 return '''
 305 <td align="center">
 306 <a href="%(img)s">
 307 <img src="%(img)s" style="border-style: none; max-width: 500px;">
 308 </a><br>
 309 <font size="-2">(<a href="%(ly)s">source</a>)
 310 </font>
 311 </td>
 312 ''' % locals ()
 313
 314             html_entry = '''
 315 <tr>
 316 <td>
 317 %f
 318 </td>
 319
 320 %s
 321 %s
 322 </tr>
 323 ''' % (score, img_cell (ly_1, img_1), img_cell (ly_2, img_2))
 324
 325
 326             html += html_entry
 327
 328         html = '''<html>
 329 <table>
 330 <tr>
 331 <th>distance</th>
 332 <th>old</th>
 333 <th>new</th>
 334 </tr>
 335 %(html)s
 336 </table>
 337 </html>''' % locals()
 338
 339         open (os.path.join (dir2, old_prefix) + '.html', 'w').write (html)
 340
 341
 342
 343 def compare_trees (dir1, dir2):
 344     data =  ComparisonData ()
 345     data.compare_trees (dir1, dir2)
 346     data.print_results ()
 347     data.create_html_result_page (dir1, dir2)
 348     data.create_text_result_page (dir1, dir2)
 349
 350 ################################################################
 351 # TESTING
 352
 353 import os
 354 def system (x):
 355
 356     print 'invoking', x
 357     stat = os.system (x)
 358     assert stat == 0
 359
 360
 361 def test_paired_files ():
 362     print paired_files (os.environ["HOME"] + "/src/lilypond/scripts/",
 363                         os.environ["HOME"] + "/src/lilypond-stable/buildscripts/", '*.py')
 364
 365
 366 def test_compare_trees ():
 367     system ('rm -rf dir1 dir2')
 368     system ('mkdir dir1 dir2')
 369     system ('cp 20{-0.signature,.ly,.png} dir1')
 370     system ('cp 20{-0.signature,.ly,.png} dir2')
 371     system ('cp 20expr{-0.signature,.ly,.png} dir1')
 372     system ('cp 19{-0.signature,.ly,.png} dir2/')
 373     system ('cp 19{-0.signature,.ly,.png} dir1/')
 374     system ('cp 20grob{-0.signature,.ly,.png} dir2/')
 375
 376     ## introduce difference
 377     system ('cp 19-0.signature dir2/20-0.signature')
 378
 379     compare_trees ('dir1', 'dir2')
 380
 381
 382 def test_basic_compare ():
 383     ly_template = r"""#(set! toplevel-score-handler print-score-with-defaults)
 384 #(set! toplevel-music-handler
 385  (lambda (p m)
 386  (if (not (eq? (ly:music-property m 'void) #t))
 387     (print-score-with-defaults
 388     p (scorify-music m p)))))
 389
 390 %(papermod)s
 391
 392 \relative c {
 393   c^"%(userstring)s" %(extragrob)s
 394   }
 395 """
 396
 397     dicts = [{ 'papermod' : '',
 398                'name' : '20',
 399                'extragrob': '',
 400                'userstring': 'test' },
 401              { 'papermod' : '#(set-global-staff-size 19.5)',
 402                'name' : '19',
 403                'extragrob': '',
 404                'userstring': 'test' },
 405              { 'papermod' : '',
 406                'name' : '20expr',
 407                'extragrob': '',
 408                'userstring': 'blabla' },
 409              { 'papermod' : '',
 410                'name' : '20grob',
 411                'extragrob': 'c4',
 412                'userstring': 'test' }]
 413
 414     for d in dicts:
 415         open (d['name'] + '.ly','w').write (ly_template % d)
 416
 417     names = [d['name'] for d in dicts]
 418
 419     system ('lilypond -ddump-signatures --png -b eps ' + ' '.join (names))
 420
 421     sigs = dict ((n, read_signature_file ('%s-0.signature' % n)) for n in names)
 422     combinations = {}
 423     for (n1, s1) in sigs.items():
 424         for (n2, s2) in sigs.items():
 425             combinations['%s-%s' % (n1, n2)] = SystemLink (s1,s2).distance ()
 426
 427     results = combinations.items ()
 428     results.sort ()
 429     for k,v in results:
 430         print '%-20s' % k, v
 431
 432     assert combinations['20-20'] == 0.0
 433     assert combinations['20-20expr'] > 50.0
 434     assert combinations['20-19'] < 10.0
 435
 436
 437 def test_sigs (a,b):
 438     sa = read_signature_file (a)
 439     sb = read_signature_file (b)
 440     link = SystemLink (sa, sb)
 441     print link.distance()
 442
 443
 444 def run_tests ():
 445     do_clean = 1
 446     dir = 'output-distance-test'
 447
 448     print 'test results in ', dir
 449     if do_clean:
 450         system ('rm -rf ' + dir)
 451         system ('mkdir ' + dir)
 452
 453     os.chdir (dir)
 454
 455     test_basic_compare ()
 456     test_compare_trees ()
 457
 458 ################################################################
 459 #
 460
 461 def main ():
 462     p = optparse.OptionParser ("output-distance - compare LilyPond formatting runs")
 463     p.usage = 'output-distance.py [options] tree1 tree2'
 464
 465     p.add_option ('', '--test',
 466                   dest="run_test",
 467                   action="store_true",
 468                   help='run test method')
 469
 470     (o,a) = p.parse_args ()
 471
 472     if o.run_test:
 473         run_tests ()
 474         sys.exit (0)
 475
 476     if len (a) != 2:
 477         p.print_usage()
 478         sys.exit (2)
 479
 480     compare_trees (a[0], a[1])
 481
 482 if __name__ == '__main__':
 483     main()
 484