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