home *** CD-ROM | disk | FTP | other *** search
/ MacAddict 108 / MacAddict108.iso / Software / Internet & Communication / JunkMatcher 1.5.5.dmg / JunkMatcher.app / Contents / Resources / Engine / comparePatterns.py < prev    next >
Encoding:
Python Source  |  2005-06-01  |  10.0 KB  |  272 lines
  1. #
  2. #  comparePatterns.py
  3. #  JunkMatcher
  4. #
  5. #  Created by Benjamin Han on 5/1/05.
  6. #  Copyright (c) 2005 Benjamin Han. All rights reserved.
  7. #
  8.  
  9. # This program is free software; you can redistribute it and/or
  10. # modify it under the terms of the GNU General Public License
  11. # as published by the Free Software Foundation; either version 2
  12. # of the License, or (at your option) any later version.
  13.  
  14. # This program is distributed in the hope that it will be useful,
  15. # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17. # GNU General Public License for more details.
  18.  
  19. # You should have received a copy of the GNU General Public License
  20. # along with this program; if not, write to the Free Software
  21. # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  22.  
  23. #!/usr/bin/env python
  24.  
  25. import sys, os.path, difflib
  26.  
  27. from consts import *
  28. from Tests import *
  29. from MetaPatterns import *
  30.  
  31.  
  32. DIFF_SCORE_THRESHOLD = 0.6
  33. rangePat = re.compile(r'-(\d+),(\d+) \+(\d+),(\d+)')
  34. _seqMatcher = difflib.SequenceMatcher()
  35.  
  36.  
  37. class PatternChange (object):
  38.     """A single pattern change
  39.        -----------------------
  40.        action: '+' (addition), '-' (deletion), 'n' (name change), 'p' (pattern change)
  41.           'b' (both name and pattern change);
  42.        new: a string or a tuple of strings (when action == 'b': the first is name and the
  43.            second is the pattern);
  44.        opcodes: a list or a tuple of lists describing how to make the old pattern into
  45.            the new one (tuple if action == 'b');
  46.        """
  47.     __slots__ = ('action', 'new', 'opcodes')
  48.     
  49.     def __init__ (self, action, new, opcodes):
  50.         self.action = action
  51.         self.new = new
  52.         self.opcodes = opcodes
  53.  
  54.     def __repr__ (self):
  55.         return '[%s, "%s", %s]' % (self.action, self.new, self.opcodes)
  56.  
  57.  
  58. def _whatKindOfChange (old, new, opcodes):
  59.     """Returns a PatternChange instance describing the changes necessary to make 'old'
  60.     into 'new'.
  61.  
  62.     ASSUMPTION: there must be at least one non-equal opcode in opcodes!"""
  63.     oldPat, oldName = old.split('\n')
  64.     newPat, newName = new.split('\n')
  65.     
  66.     oldPatSize = len(oldPat)
  67.     newPatSize = len(newPat)
  68.  
  69.     patOpcodes = []
  70.     nameOpcodes = []
  71.  
  72.     for op in filter(lambda i: i[0] != 'equal', opcodes):
  73.         oldIdx = op[1]
  74.         if oldIdx < oldPatSize:
  75.             patOpcodes.append(op)
  76.         else:
  77.             nameOpcodes.append((op[0],
  78.                                 op[1] - oldPatSize - 1,
  79.                                 op[2] - oldPatSize - 1,
  80.                                 op[3] - newPatSize - 1,
  81.                                 op[4] - newPatSize - 1))
  82.  
  83.     if patOpcodes and nameOpcodes:
  84.         return PatternChange('b', (newPat, newName), (patOpcodes, nameOpcodes))
  85.     elif patOpcodes:
  86.         return PatternChange('p', newPat, patOpcodes)
  87.     else:
  88.         return PatternChange('n', newName, nameOpcodes)
  89.  
  90.  
  91. def _diffPatterns (origList, newList, idIsPattern = True):
  92.     """Compare two lists of patterns (strings) and return a tuple (changeDelta,
  93.     removeDelta, addDelta) that can change the origList into newList:
  94.  
  95.     changeDelta: a dictionary with pattern IDs as keys and PatternChange instances as values;
  96.     removeDelta: a set of pattern IDs for removal;
  97.     addDelta: a set of tuple pattern IDs for addition.
  98.  
  99.     For the regular patterns the IDs are the regex themselves; for the meta patterns the
  100.     IDs are the meta patterns' names.
  101.  
  102.     When comparing meta patterns, set idIsPattern to False."""
  103.     
  104.     origList.sort()
  105.     newList.sort()
  106.  
  107.     changeDelta = {}
  108.  
  109.     # we need to find the closest matches for the patterns in the origPatterns against the
  110.     # newPatterns
  111.     # NOTE here the term "pattern" refers to a regex/name combo
  112.     origPatterns = sets.Set()
  113.     newPatterns = sets.Set()
  114.  
  115.     for diffLine in map(string.strip,
  116.                         difflib.unified_diff(origList, newList, n = 0))[2:]:
  117.         c = diffLine[0]
  118.         if c == '@':
  119.             mo = rangePat.search(diffLine[3:-3])
  120.             origIdx, newIdx = int(mo.group(1)) - 1, int(mo.group(3)) - 1
  121.         else:
  122.             if c == '+':
  123.                 newPatterns.add(newList[newIdx])
  124.                 newIdx += 1
  125.                 
  126.             elif c == '-':
  127.                 origPatterns.add(origList[origIdx])
  128.                 origIdx += 1
  129.                 
  130.             else:
  131.                 origIdx += 1
  132.                 newIdx += 1
  133.  
  134.     newPatternsToBeRemoved = sets.Set()
  135.     
  136.     # now origPatterns and newPatterns contain only the leftover patterns for alignment
  137.     # p2 is a new pattern (cached by SequenceMatcher)
  138.     for p2 in newPatterns:
  139.         _seqMatcher.set_seq2(p2)   # seq 2 is cached in SequenceMatcher
  140.         matchesForOnePattern = []
  141.         for p1 in origPatterns:
  142.             _seqMatcher.set_seq1(p1)
  143.             opcodes = _seqMatcher.get_opcodes()
  144.             ratio = _seqMatcher.ratio()
  145.             if ratio == 1.0:
  146.                 # identical "change" is found - take p1 and p2 out of changeDelta
  147.                 origPatterns.remove(p1)
  148.                 newPatternsToBeRemoved.add(p2)
  149.                 break
  150.             elif ratio > DIFF_SCORE_THRESHOLD:
  151.                 matchesForOnePattern.append((ratio, p1, opcodes))
  152.  
  153.         if matchesForOnePattern:
  154.             match, maxIdx = max(zip(matchesForOnePattern, range(len(matchesForOnePattern))))
  155.             origPattern = match[1]
  156.             origPatterns.remove(origPattern)
  157.             newPatternsToBeRemoved.add(p2)  # p2 is taken - remove it from newPatterns later
  158.  
  159.             if idIsPattern: pcID = origPattern.split('\n')[0]
  160.             else: pcID = origPattern.split('\n')[1]
  161.  
  162.             pc = _whatKindOfChange(origPattern, p2, match[2])
  163.             changeDelta[pcID] = pc
  164.  
  165.     newPatterns -= newPatternsToBeRemoved
  166.  
  167.     if idIsPattern:
  168.         return (changeDelta,
  169.                 sets.Set(map(lambda i: i.split('\n')[0], origPatterns)),
  170.                 sets.Set(map(lambda i: i.split('\n')[0], newPatterns)))
  171.     else:
  172.         return (changeDelta,
  173.                 sets.Set(map(lambda i: i.split('\n')[1], origPatterns)),
  174.                 sets.Set(map(lambda i: i.split('\n')[1], newPatterns)))
  175.  
  176.  
  177. def compareMetaPatterns (origMetaPatterns, newMetaPatterns):
  178.     """Compare two meta patterns and return a tuple (changeDelta, removeDelta, addDelta) that
  179.     can change the origMetaPatterns into newMetaPatterns; see _diffPatterns() for comments on
  180.     the three deltas.
  181.     """
  182.     # we only compare managed non-reserved meta patterns
  183.     origMetaList = map(lambda i:'%s\n%s' % (i[1][0], i[0]),
  184.                        filter(lambda i:not i[1][1] and i[1][2], origMetaPatterns.items()))
  185.     newMetaList = map(lambda i:'%s\n%s' % (i[1][0], i[0]),
  186.                       filter(lambda i:not i[1][1] and i[1][2], newMetaPatterns.items()))
  187.  
  188.     return _diffPatterns(origMetaList, newMetaList, False)
  189.  
  190.  
  191. def comparePatterns (origPatterns, newPatterns, origTests, newTests):
  192.     """Compare two patterns and return a tuple (changeDelta, removeDelta, addDelta) that
  193.     can change the origPatterns into newPatterns; see _diffPatterns() for comments on
  194.     changeDelta; removeDelta is a dictionary using regexes as keys and test indices as
  195.     values; addDelta is a dictionary using regexes as keys and Test instances as values.
  196.     """
  197.     # we only compare managed patterns
  198.     origList = map(lambda i:'%s\n%s' % (i.origPattern, i.name),
  199.                    filter(lambda i:i.isManaged, origPatterns.values()))
  200.     newList = map(lambda i:'%s\n%s' % (i.origPattern, i.name),
  201.                   filter(lambda i:i.isManaged, newPatterns.values()))
  202.  
  203.     changeDelta, removeDelta, addDelta = _diffPatterns(origList, newList, origTests)
  204.  
  205.     # turn removeDelta into a dictionary, with values being a list of indices into origTests
  206.     # None means the pattern isn't used in origTests (normally this can't happen)
  207.     removeDelta = dict.fromkeys(removeDelta, None)
  208.  
  209.     for idx, t in filter(lambda i: i[1].isPattern, enumerate(origTests)):
  210.         p = t.propertyOrPattern.origPattern
  211.         if p in removeDelta:
  212.             if removeDelta[p] is None: removeDelta[p] = [idx]
  213.             else: removeDelta[p].append(idx)
  214.  
  215.     # turn addDelta into a dictionary, with values being a list of Test instances in newTests
  216.     # None means the pattern isn't used in newTests (normally this can't happen)
  217.     addDelta = dict.fromkeys(addDelta, None)
  218.     
  219.     for t in filter(lambda t: t.isPattern, newTests):
  220.         p = t.propertyOrPattern.origPattern
  221.         if p in addDelta:
  222.             if addDelta[p] is None: addDelta[p] = [t]
  223.             else: addDelta[p].append(t)
  224.  
  225.     return (changeDelta, removeDelta, addDelta)
  226.  
  227.  
  228. if __name__ == '__main__':
  229.     if len(sys.argv) != 3:
  230.         print 'Usage: ./comparePatterns.py <path to the old patterns> <path to the new patterns>'
  231.         sys.exit(1)
  232.  
  233.     import pprint
  234.  
  235.     origPath = sys.argv[1]
  236.     newPath = sys.argv[2]    
  237.  
  238.     # comparing meta patterns
  239.     origMetaPatterns = MetaPatterns(os.path.join(origPath, 'metaPatterns'))
  240.     newMetaPatterns = MetaPatterns(os.path.join(newPath, 'metaPatterns'))
  241.  
  242.     changeDelta, removeDelta, addDelta = compareMetaPatterns(origMetaPatterns, newMetaPatterns)
  243.  
  244.     print '========== meta patterns deltas =========='
  245.     print '* changeDelta:'
  246.     pprint.pprint(changeDelta)
  247.     print '\n* removeDelta:'
  248.     pprint.pprint(removeDelta)
  249.     print '\n* addDelta:'
  250.     pprint.pprint(addDelta)
  251.     print
  252.  
  253.     # comparing patterns
  254.     origPatterns = Patterns(os.path.join(origPath, 'patterns'))
  255.     newPatterns = Patterns(os.path.join(newPath, 'patterns'))
  256.     origTests = Tests(Properties(os.path.join(origPath, 'properties')),
  257.                       origPatterns,
  258.                       os.path.join(origPath, 'tests'))
  259.     newTests = Tests(Properties(os.path.join(newPath, 'properties')),
  260.                      newPatterns,
  261.                      os.path.join(newPath, 'tests'))
  262.  
  263.     changeDelta, removeDelta, addDelta = comparePatterns(origPatterns, newPatterns, origTests, newTests)
  264.  
  265.     print '========== patterns deltas =========='
  266.     print '* changeDelta:'
  267.     pprint.pprint(changeDelta)
  268.     print '\n* removeDelta:'
  269.     pprint.pprint(removeDelta)
  270.     print '\n* addDelta:'
  271.     pprint.pprint(addDelta)
  272.