buildscripts/output-distance.py

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