buildscripts/output-distance.py

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