difflib.py
c:\python23\lib\difflib.py
00008 f 00008
00009Function context_diff(a, b): 00009Function context_diff(a, b):
00010    For two lists of strings, return a delta in context diff format. 00010    For two lists of strings, return a delta in context diff format.
00011  n
00012Function mdiff(a, b):
00013    Returns iterator yielding from/to side by side difference lines.
00014 
00015Function mdiffHtmlCollector(diffs,context,sep,prefix):
00016    Returns from/to side by side difference lines with HTML change links.
00017 00011
00018Function ndiff(a, b): 00012Function ndiff(a, b):
00019    Return a delta: the difference between `a` and `b` (lists of strings). 00013    Return a delta: the difference between `a` and `b` (lists of strings).
00020 00014
00033 00027
00034__all__ = ['get_close_matches', 'ndiff', 'restore', 'SequenceMatcher', 00028__all__ = ['get_close_matches', 'ndiff', 'restore', 'SequenceMatcher',
00035           'Differ','IS_CHARACTER_JUNK', 'IS_LINE_JUNK', 'context_diff', 00029           'Differ','IS_CHARACTER_JUNK', 'IS_LINE_JUNK', 'context_diff',
00036           'unified_diff', 'mdiff', 'mdiffHtmlCollector'] n 00030           'unified_diff']
00037 00031
00038def _calculate_ratio(matches, length): 00032def _calculate_ratio(matches, length):
00039    if length: 00033    if length:
01107 01101
01108    return ch in ws 01102    return ch in ws
01109 01103
n 01104del re
01105 
01110 01106
01111def unified_diff(a, b, fromfile='', tofile='', fromfiledate='', 01107def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
01112                 tofiledate='', n=3, lineterm='\n'): 01108                 tofiledate='', n=3, lineterm='\n'):
01113    r""" 01109    r"""
01280    + emu 01276    + emu
01281    """ 01277    """
01282    return Differ(linejunk, charjunk).compare(a, b) 01278    return Differ(linejunk, charjunk).compare(a, b)
01283  n
01284def mdiff(fromLines, toLines, chgFmt, lineFmt, context=None, sep=None, **kwArgs):
01285    """Returns iterator yielding from/to side by side difference lines.
01286 
01287    fromLines -- text lines which will be iterated over and compared to toLines
01288    toLines -- text lines which will be iterated over and compared to fromLines
01289    chgFmt -- function to markup add/delete/change differences in text lines
01290              (see example below)
01291    lineFmt -- function to format line of text for display (see example below)
01292    context -- number of context lines to display on each side of difference,
01293               if None or less that 1, the all from/to text lines will be
01294               generated.
01295    sep -- separator string to use between context differences.
01296 
01297    kwArgs -- passed on to ndiff (TBD discuss)
01298    
01299    This function/iterator was originally developed to generate side by side
01300    file difference for making HTML pages.  The function requires functions to
01301    be passed in as arguments to allow it to be configurable to generate XML
01302    markup or other types of formats.  The function supports generating a
01303    full file difference report or just contextual differences.
01304 
01305    Below are example functions that are written to do HTML markup and an
01306    example use of the iterator (see /Tools/Scripts/diff.py for full example):
01307 
01308    import xml.sax.saxutils
01309    def htmlLineFmt(text,lineNum,side):
01310        try:
01311            return '<font class="num">%05d</font> %s' % (lineNum,
01312                                                xml.sax.saxutils.escape(text))
01313        except TypeError:
01314            # handle blank lines where lineNum will be None
01315            return '<font class="num">     </font> %s' % text
01316 
01317    def htmlChangeFmt(type,text,side):
01318        if type == '+':
01319            return '<font class="add">%s</font>' % text
01320        if type == '-':
01321            return '<font class="sub">%s</font>' % text
01322        if type == '^':
01323            return '<font class="chg">%s</font>' % text
01324 
01325    for from, to, flag in mdiff(fromLines, toLines, marker, lineFmt):
01326        fromText.write(from)
01327        toText.write(to)
01328    """
01329    import re 
01330 
01331    if context:
01332        context += 1 # xxx added this if
01333 
01334    # regular expression for finding intraline change indices
01335    changeRe = re.compile('(\++|\-+|\^+)')
01336    # regular expression to find hidden markers
01337    markerRe = re.compile('\0([+-^])(.*?)\1',re.DOTALL)
01338 
01339    # create the difference iterator to generate the differences
01340    diffLinesIterator = ndiff(fromLines,toLines,**kwArgs)
01341 
01342    def _mkLine(lines, formatKey, side, numLines=[0,0]):
01343        """Returns line of text with user's change markup and line formatting.
01344 
01345        lines -- list of lines from the ndiff generator to produce a line of
01346                 text from.  When producing the line of text to return, the
01347                 lines used are removed from this list.
01348        formatKey -- '+' return first line in list with "add" markup around
01349                         the entire line.
01350                     '-' return first line in list with "delete" markup around
01351                         the entire line.
01352                     '?' return first line in list with add/delete/change
01353                         intraline markup (indices obtained from second line)
01354                     None return first line in list with no markup
01355        side -- indice into the numLines list (0=from,1=to)
01356        numLines -- from/to current line number.  This is NOT intended to be a
01357                    passed parameter.  It is present as a keyword argument to
01358                    maintain memory of the current line numbers between calls
01359                    of this function.
01360 
01361        Note, this function is purposefully not defined at the module scope so
01362        that data it needs from it's parent function (within whose context it
01363        is defined) does not need to be of module scope.
01364        """
01365        numLines[side] += 1
01366        # Handle case where no user markup is to be added, just return line of
01367        # text with user's line format to allow for usage of the line number.
01368        if formatKey is None:
01369            return lineFmt(side,numLines[side],lines.pop(0)[2:])
01370        # Handle case of intraline changes
01371        if formatKey == '?':
01372            text, markers = lines.pop(0), lines.pop(0)
01373            # find intraline changes (store change type and indices in tuples)
01374            subInfo = []
01375            def recordSubInfo(matchObject,subInfo=subInfo):
01376                subInfo.append([matchObject.group(1)[0],matchObject.span()])
01377                return matchObject.group(1)
01378            changeRe.sub(recordSubInfo,markers)
01379            # process each tuple inserting our special marks that won't be
01380            # noticed by an xml/html escaper.
01381            for key,(begin,end) in subInfo[::-1]:
01382                text = text[0:begin]+'\0'+key+text[begin:end]+'\1'+text[end:]
01383            text = text[2:]
01384        # Handle case of add/delete entire line
01385        else:
01386            text = lines.pop(0)[2:]
01387            # if line of text is just a newline, insert a space so there is
01388            # something for the user to highlight and see.
01389            if len(text) <= 1:
01390                text = ' '+text
01391            # insert marks that won't be noticed by an xml/html escaper.
01392            text = '\0' + formatKey + text + '\1'
01393        # Return line of text, first allow user's line formatter to do it's
01394        # thing (such as adding the line number) then replace the special
01395        # marks with what the user's change markup.
01396        lineNum = numLines[side]
01397        replacer = lambda m : chgFmt(side,lineNum,m.group(2),m.group(1))
01398        return markerRe.sub(replacer,lineFmt(side,lineNum,text))
01399    
01400    def _lineIterator():
01401        """Yields from/to lines of text with a change indication.
01402 
01403        This function is an iterator.  It itself pulls lines from a
01404        differencing iterator, processes them and yields them.  When it can
01405        it yields both a "from" and a "to" line, otherwise it will yield one
01406        or the other.  Processing includes formatting the line with the user's
01407        line formatter (for adding line numbering) and formatting differences
01408        using the user's change format function.  In addition to yielding the
01409        lines of from/to text, a boolean flag is yielded to indicate if the
01410        text line(s) have differences in them.
01411 
01412        Note, this function is purposefully not defined at the module scope so
01413        that data it needs from it's parent function (within whose context it
01414        is defined) does not need to be of module scope.
01415        """
01416        lines = []
01417        numBlanksPending, numBlanksToYield = 0, 0
01418        while True:        
01419            # Load up next 4 lines so we can look ahead, create strings  which
01420            # are a concatenation of the first character of each of the 4 lines
01421            # so we can do some very readable comparisons.
01422            while len(lines) < 4:
01423                try:
01424                    lines.append(diffLinesIterator.next())
01425                except StopIteration:
01426                    lines.append('X')
01427            s = ''.join([line[0] for line in lines])
01428            if s.startswith('X'):
01429                # When no more lines, pump out any remaining blank lines so the
01430                # corresponding add/delete lines get a matching blank line so
01431                # all line pairs get yielded at the next level.
01432                numBlanksToYield = numBlanksPending
01433            elif s.startswith('-?+?'):
01434                # simple intraline change
01435                yield _mkLine(lines,'?',0), _mkLine(lines,'?',1), True
01436                continue
01437            elif s.startswith('--++'):
01438                # in delete block, add block coming: we do NOT want to get
01439                # caught up on blank lines yet, just process the delete line
01440                numBlanksPending -= 1
01441                yield _mkLine(lines,'-',0), None, True
01442                continue
01443            elif s.startswith('--?+') or s.startswith('--+') or \
01444                 s.startswith('- '):
01445                # in delete block and see a intraline change or unchanged line
01446                # coming: yield the delete line and then blanks
01447                fromLine,toLine = _mkLine(lines,'-',0), None
01448                numBlanksToYield, numBlanksPending = numBlanksPending-1, 0
01449            elif s.startswith('-+?'):
01450                # intraline change
01451                yield _mkLine(lines,None,0), _mkLine(lines,'?',1), True
01452                continue
01453            elif s.startswith('-?+'):
01454                # intraline change
01455                yield _mkLine(lines,'?',0), _mkLine(lines,None,1), True
01456                continue
01457            elif s.startswith('-'):
01458                # delete FROM line
01459                numBlanksPending -= 1
01460                yield _mkLine(lines,'-',0), None, True
01461                continue
01462            elif s.startswith('+--'):
01463                # in add block, delete block coming: we do NOT want to get
01464                # caught up on blank lines yet, just process the add line
01465                numBlanksPending += 1
01466                yield None, _mkLine(lines,'+',1), True
01467                continue
01468            elif s.startswith('+ ') or s.startswith('+-'):
01469                # will be leaving an add block: yield blanks then add line
01470                fromLine, toLine = None, _mkLine(lines,'+',1)
01471                numBlanksToYield, numBlanksPending = numBlanksPending+1, 0
01472            elif s.startswith('+'):
01473                # inside an add block, yield the add line
01474                numBlanksPending += 1
01475                yield None, _mkLine(lines,'+',1), True
01476                continue
01477            elif s.startswith(' '):
01478                # unchanged text, yield it to both sides
01479                yield _mkLine(lines[:],None,0),_mkLine(lines,None,1),False
01480                continue
01481            # Catch up on the blank lines so when we yield the next from/to
01482            # pair, they are lined up.
01483            while(numBlanksToYield < 0):
01484                numBlanksToYield += 1
01485                yield None,lineFmt(1,None,'\n'),True
01486            while(numBlanksToYield > 0):
01487                numBlanksToYield -= 1
01488                yield lineFmt(0,None,'\n'),None,True
01489            if s.startswith('X'):
01490                raise StopIteration
01491            else:
01492                yield fromLine,toLine,True
01493 
01494    def _linePairIterator():
01495        """Yields from/to lines of text with a change indication.
01496 
01497        This function is an iterator.  It itself pulls lines from the line
01498        iterator.  It's difference from that iterator is that this function
01499        always yields a pair of from/to text lines (with the change
01500        indication).  If necessary it will collect single from/to lines
01501        until it has a matching pair from/to pair to yield.
01502 
01503        Note, this function is purposefully not defined at the module scope so
01504        that data it needs from it's parent function (within whose context it
01505        is defined) does not need to be of module scope.
01506        """
01507        lineIterator = _lineIterator()
01508        fromLines,toLines=[],[]
01509        while True:
01510            # Collecting lines of text until we have a from/to pair
01511            while (len(fromLines)==0 or len(toLines)==0):
01512                fromLine, toLine, foundDiff =lineIterator.next()
01513                if fromLine is not None:
01514                    fromLines.append((fromLine,foundDiff))
01515                if toLine is not None:
01516                    toLines.append((toLine,foundDiff))
01517            # Once we have a pair, remove them from the collection and yield it
01518            fromLine, fromDiff = fromLines.pop(0)
01519            toLine, toDiff = toLines.pop(0)
01520            yield (fromLine,toLine,fromDiff or toDiff)
01521 
01522    # Handle case where user does not context differencing, just yield them up
01523    # without doing anything else with them.
01524    linePairIterator = _linePairIterator()
01525    if context is None or context <= 0:
01526        while True:
01527            yield linePairIterator.next()
01528    # Handle case where user want context differencing.  We must do some
01529    # storage of lines until we know for sure that they are to be yielded.
01530    else:
01531        linesToWrite = 0
01532        insertSeparator = False
01533        while True:
01534            # Store lines up until we find a difference, note use of a
01535            # circular queue because we only need to keep around what
01536            # we need for context.
01537            index, contextLines = 0, [None]*(context)
01538            foundDiff = False
01539            while(foundDiff is False):
01540                fromLine, toLine, foundDiff = linePairIterator.next()
01541                i = index % context
01542                contextLines[i] = (fromLine, toLine, foundDiff)
01543                index += 1
01544            # Yield lines that we have collected so far, but first yield
01545            # the user's separator.
01546            if insertSeparator:
01547                yield sep, sep, None
01548            else:
01549                insertSeparator = True
01550            if index > context:
01551                linesToWrite = context
01552            else:
01553                linesToWrite = index
01554                index = 0
01555            while(linesToWrite):
01556                i = index % context
01557                index += 1
01558                yield contextLines[i]
01559                linesToWrite -= 1
01560            # Now yield the context lines after the change
01561            linesToWrite = context-1 #xxx -1 added
01562            while(linesToWrite):
01563                fromLine, toLine, foundDiff = linePairIterator.next()
01564                # If another change within the context, extend the context
01565                if foundDiff:
01566                    linesToWrite = context
01567                else:
01568                    linesToWrite -= 1
01569                yield fromLine, toLine, foundDiff
01570 
01571 
01572class HtmlDiff(object):
01573    _file = """
01574        <html>
01575        <head>
01576        <title>%(title)s</title>
01577        <style type="text/css">%(styles)s
01578        </style>
01579        </head>
01580        <body>
01581        %(body)s<p>%(legend)s
01582        </body>
01583        </html>"""
01584 
01585    legend = """
01586        <table style="font-family:Courier">
01587            <tr> <th colspan=2> Legends
01588            <tr> <td> <table border>
01589                          <tr> <th> Colors
01590                          <tr> <td> <span class=add>&nbsp;Added&nbsp</span>
01591                          <tr> <td> <span class=chg>Changed</span> <td>
01592                          <tr> <td> <span class=sub>Deleted</span> <td>
01593                      </table>
01594                 <td> <table border>
01595                          <tr> <th colspan=2> Links
01596                          <tr> <td> (f)irst change
01597                          <tr> <td> (n)ext change
01598                          <tr> <td> (t)able top
01599                      </table>
01600        </table>"""
01601 
01602    styles = """
01603        td.xtra {background-color:#e0e0e0}
01604        td.next {background-color:#c0c0c0}
01605        th.xtra {background-color:#e0e0e0}
01606        th.next {background-color:#c0c0c0}
01607        span.add {background-color:#aaffaa}
01608        span.chg {background-color:#ffff77}
01609        span.sub {background-color:#ffaaaa}"""
01610 
01611    table = """
01612        <table id="_chg_%(prefix)s_top" border=3 cellspacing=0 cellpadding=0 cols=5 rules=groups style="font-family:Courier">
01613            <colgroup> <colgroup> <colgroup> <colgroup> <colgroup>%(headerRow)s%(dataRows)s
01614        </table>"""
01615 
01616    def __init__(self,fromdesc='',todesc='',title='Side by Side Difference',prefix=['from','to']):
01617        """
01618        prefix -- for line anchor
01619        desc -- ['from','to']
01620        title -- window title
01621        """
01622        self._prefix = prefix
01623        self._changed = {}
01624        self._title = title
01625        self._fromdesc = fromdesc
01626        self._todesc = todesc
01627        import xml.sax.saxutils 
01628        self._escape = xml.sax.saxutils.escape
01629 
01630    def make_file(self,*args,**kwargs):
01631        body = self.make_table(*args,**kwargs)
01632        return self._file % dict(title=self._title,body=body,styles=self.styles,legend=self.legend)
01633 
01634    def make_table(self,fromlines,tolines,context=False,numlines=5):
01635        """Returns from/to side by side difference lines with HTML change links.
01636 
01637        context -- number of context lines
01638        sep -- separator string
01639 
01640        Returns table
01641        
01642        This function was developed in combination with mdiff to generate side by
01643        side file difference for making HTML pages.  The mdiff function is a
01644        generator that yields from/to lines with an associated difference flag.
01645        This function collects (and returns) the from/to lines in a text string.
01646        It also collects the difference flags, processes them and generates a
01647        text string that can be displayed in between the from/to lines that
01648        hyperlinks the changed areas.
01649        """
01650        if context:
01651            context = numlines
01652        else:
01653            context = 0
01654        diffs = mdiff(fromlines,tolines,self.format_change,self.format_line,context,None)
01655        prefix = self._prefix[1]
01656        # collect up from/to lines in string, difference flags in a list
01657        fromText, toText, diffFlags = [],[],[]
01658        for fromLine, toLine, foundDiff in diffs:
01659            fromText.append(fromLine)
01660            toText.append(toLine)
01661            diffFlags.append(foundDiff)
01662        # process change flags, generating middle column of next anchors/links
01663        anchors = ['']*len(diffFlags)
01664        numChg, inChange = 0, False
01665        last = 0
01666        for i,flag in enumerate(diffFlags):
01667            if flag is None:
01668                # mdiff yields None on separator lines # TBD can I get rid of this??
01669                pass
01670            elif flag:
01671                if not inChange:
01672                    inChange = True
01673                    last = i
01674                    # at the beginning of a change, drop an anchor a few lines
01675                    # (the context lines) before the change for the previous link
01676                    i = max([0,i-numlines])
01677                    anchors[i] += '<a name="_chg_%s_%d"/>' % (prefix,numChg)
01678                    # at the beginning of a change, drop a link to the next change
01679                    numChg += 1
01680                    anchors[last] = '<a href="#_chg_%s_%d">n</a>' % (prefix,numChg)
01681            else:
01682                inChange = False
01683        # if not a change on first line, drop a link
01684        if not diffFlags[0]:
01685            anchors[0] += '<a href="#_chg_%s_0">f</a>' % prefix
01686        # drop an anchor at the top
01687        #anchors[0] += '<a name="_chg_%s_top"><br></a>' % prefix
01688        # redo the last link to link to the top
01689        anchors[last] = '<a href="#_chg_%s_top">t</a>' % prefix
01690        import cStringIO
01691        s = cStringIO.StringIO()
01692        for i in range(len(anchors)):
01693            if diffFlags[i] is None:
01694                # mdiff yields None on separator lines
01695                s.write('<tbody>\n')
01696            else:
01697                s.write('<tr>%s\n<td class=next>%s\n%s\n</tr>' % (fromText[i],anchors[i],toText[i]))
01698        if self._fromdesc or self._todesc:
01699            headerRow = '<tr><th colspan=2 class=xtra>%s<th class=next><br><th colspan=2 class=xtra>%s</tr>' % (self._fromdesc,self._todesc)
01700        else:
01701            headerRow = ''
01702        return self.table % dict(dataRows=s.getvalue(),headerRow=headerRow,prefix=prefix)
01703 
01704    def format_line(self,side,linenum,text):
01705        try:
01706            linenum = '<a name="%s%05d">%05d</a>' % (self._prefix[side],linenum,linenum)
01707        except TypeError:
01708            # handle blank lines where linenum is None
01709            linenum = ''
01710 
01711        text = self._escape(text)
01712        text = text.replace(' ','&nbsp;')    
01713        return '<td class=xtra>%s<td nowrap>%s' % (linenum,text)
01714 
01715    def format_change(self,side,linenum,text,type):
01716        if side:
01717            self._changed[linenum] = True
01718        if type == '+':
01719            return '<span class=add>%s</span>' % text
01720        if type == '-':
01721            return '<span class=sub>%s</span>' % text
01722        if type == '^':
01723            return '<span class=chg>%s</span>' % text
01724 
01725 01279
01726def restore(delta, which): 01280def restore(delta, which):
01727    r""" 01281    r"""
01728    Generate one of the two sequences that generated a delta. 01282    Generate one of the two sequences that generated a delta.
01759    import doctest, difflib 01313    import doctest, difflib
01760    return doctest.testmod(difflib) 01314    return doctest.testmod(difflib)
01761 01315
01762  t
01763del re
01764 
01765 
01766if __name__ == "__main__": 01316if __name__ == "__main__":
01767    _test() 01317    _test()

Legends
Colors
 Added 
Changed
Deleted
Links
(f)irst change
(n)ext change
(t)able top