| \section{\module{difflib} ---
|
f |
\section{\module{difflib} ---
|
| Helpers for computing deltas}
|
|
Helpers for computing deltas}
|
|
|
|
|
| \declaremodule{standard}{difflib}
|
|
\declaremodule{standard}{difflib}
|
| \modulesynopsis{Helpers for computing differences between objects.}
|
|
\modulesynopsis{Helpers for computing differences between objects.}
|
| \moduleauthor{Tim Peters}{tim_one@users.sourceforge.net}
|
|
\moduleauthor{Tim Peters}{tim_one@users.sourceforge.net}
|
| \sectionauthor{Tim Peters}{tim_one@users.sourceforge.net}
|
|
\sectionauthor{Tim Peters}{tim_one@users.sourceforge.net}
|
| % LaTeXification by Fred L. Drake, Jr. <fdrake@acm.org>.
|
|
% LaTeXification by Fred L. Drake, Jr. <fdrake@acm.org>.
|
|
|
|
|
| \versionadded{2.1}
|
|
\versionadded{2.1}
|
|
|
|
|
|
|
|
|
| \begin{classdesc*}{SequenceMatcher}
|
|
\begin{classdesc*}{SequenceMatcher}
|
| This is a flexible class for comparing pairs of sequences of any
|
|
This is a flexible class for comparing pairs of sequences of any
|
| type, so long as the sequence elements are hashable. The basic
|
|
type, so long as the sequence elements are hashable. The basic
|
| algorithm predates, and is a little fancier than, an algorithm
|
|
algorithm predates, and is a little fancier than, an algorithm
|
| published in the late 1980's by Ratcliff and Obershelp under the
|
|
published in the late 1980's by Ratcliff and Obershelp under the
|
| hyperbolic name ``gestalt pattern matching.'' The idea is to find
|
|
hyperbolic name ``gestalt pattern matching.'' The idea is to find
|
| the longest contiguous matching subsequence that contains no
|
|
the longest contiguous matching subsequence that contains no
|
| ``junk'' elements (the Ratcliff and Obershelp algorithm doesn't
|
|
``junk'' elements (the Ratcliff and Obershelp algorithm doesn't
|
| address junk). The same idea is then applied recursively to the
|
|
address junk). The same idea is then applied recursively to the
|
| pieces of the sequences to the left and to the right of the matching
|
|
pieces of the sequences to the left and to the right of the matching
|
| subsequence. This does not yield minimal edit sequences, but does
|
|
subsequence. This does not yield minimal edit sequences, but does
|
| tend to yield matches that ``look right'' to people.
|
|
tend to yield matches that ``look right'' to people.
|
|
|
|
|
| \strong{Timing:} The basic Ratcliff-Obershelp algorithm is cubic
|
|
\strong{Timing:} The basic Ratcliff-Obershelp algorithm is cubic
|
| time in the worst case and quadratic time in the expected case.
|
|
time in the worst case and quadratic time in the expected case.
|
| \class{SequenceMatcher} is quadratic time for the worst case and has
|
|
\class{SequenceMatcher} is quadratic time for the worst case and has
|
| expected-case behavior dependent in a complicated way on how many
|
|
expected-case behavior dependent in a complicated way on how many
|
| elements the sequences have in common; best case time is linear.
|
|
elements the sequences have in common; best case time is linear.
|
| \end{classdesc*}
|
|
\end{classdesc*}
|
|
|
|
|
| \begin{classdesc*}{Differ}
|
|
\begin{classdesc*}{Differ}
|
| This is a class for comparing sequences of lines of text, and
|
|
This is a class for comparing sequences of lines of text, and
|
| producing human-readable differences or deltas. Differ uses
|
|
producing human-readable differences or deltas. Differ uses
|
| \class{SequenceMatcher} both to compare sequences of lines, and to
|
|
\class{SequenceMatcher} both to compare sequences of lines, and to
|
| compare sequences of characters within similar (near-matching)
|
|
compare sequences of characters within similar (near-matching)
|
| lines.
|
|
lines.
|
|
|
|
|
| Each line of a \class{Differ} delta begins with a two-letter code:
|
|
Each line of a \class{Differ} delta begins with a two-letter code:
|
|
|
|
|
| \begin{tableii}{l|l}{code}{Code}{Meaning}
|
|
\begin{tableii}{l|l}{code}{Code}{Meaning}
|
| \lineii{'- '}{line unique to sequence 1}
|
|
\lineii{'- '}{line unique to sequence 1}
|
| \lineii{'+ '}{line unique to sequence 2}
|
|
\lineii{'+ '}{line unique to sequence 2}
|
| \lineii{' '}{line common to both sequences}
|
|
\lineii{' '}{line common to both sequences}
|
| \lineii{'? '}{line not present in either input sequence}
|
|
\lineii{'? '}{line not present in either input sequence}
|
| \end{tableii}
|
|
\end{tableii}
|
|
|
|
|
| Lines beginning with `\code{?~}' attempt to guide the eye to
|
|
Lines beginning with `\code{?~}' attempt to guide the eye to
|
| intraline differences, and were not present in either input
|
|
intraline differences, and were not present in either input
|
| sequence. These lines can be confusing if the sequences contain tab
|
|
sequence. These lines can be confusing if the sequences contain tab
|
| characters.
|
|
characters.
|
| \end{classdesc*}
|
|
\end{classdesc*}
|
|
|
|
|
|
|
n |
\begin{classdesc*}{HtmlDiff}
|
|
|
|
|
|
|
|
This class can be used to create an HTML table (or a complete HTML file
|
|
|
|
containing the table) showing a side by side, line by line comparision
|
|
|
|
of text with inter-line and intra-line changes highlighted. The table can
|
|
|
|
be generated showing either the full files or just contextual differences.
|
|
|
|
|
|
|
|
This class may be subclassed to override certain methods and members to
|
|
|
|
customize the HTML output. In general this is not necessary but for special
|
|
|
|
applications where it is, please refer to the class documentation string in
|
|
|
|
the \module{difflib} module. Note, this class utilizes the
|
|
|
|
\function{ndiff()} function. Its optional keyword arguments for filtering
|
|
|
|
are supported by the \code{__init__()} method of this class.
|
|
|
|
|
|
|
|
The following methods are public:
|
|
|
|
|
|
|
|
\begin{funcdesc}{make_file}{fromlines, tolines
|
|
|
|
\optional{, fromdesc
|
|
|
|
\optional{, todesc
|
|
|
|
\optional{, context
|
|
|
|
\optional{, numlines
|
|
|
|
\optional{, title
|
|
|
|
\optional{, header
|
|
|
|
\optional{, summary}}}}}}}}
|
|
|
|
Compares \var{fromlines} and \var{tolines} (lists of strings) and returns
|
|
|
|
a string which is a complete HTML file containing a table showing line by
|
|
|
|
line differences with inter-line and intra-line changes highlighted.
|
|
|
|
|
|
|
|
\var{fromdesc} and \var{todesc} are optional keyword arguments to specify
|
|
|
|
from/to file column header strings (both default to an empty string).
|
|
|
|
|
|
|
|
\var{context} and \var{numlines} are both optional keyword arguments.
|
|
|
|
Set \var{context} to \code{True} when contextual differences are to be
|
|
|
|
shown, else the default is \code{False} to show the full files.
|
|
|
|
\var{numlines} defaults to \code{5}. When \var{context} is \code{True}
|
|
|
|
\var{numlines} controls the number of context lines which surround the
|
|
|
|
difference highlights. When \var{context} is \code{False} \var{numlines}
|
|
|
|
controls the number of lines which are shown before a difference
|
|
|
|
highlight when using the "next" hyperlinks (setting to zero would cause
|
|
|
|
the "next" hyperlinks to place the next difference highlight at the top of
|
|
|
|
the browser without any leading context).
|
|
|
|
|
|
|
|
\var{title}, \var{header}, and \var{summary} are all optional keyword
|
|
|
|
arguments and default to an empty string. Use \var{title} to specify the
|
|
|
|
window title string, \var{header} to specify the HTML markup string to be
|
|
|
|
placed above the table and \var{summary} to specify the table's 'summary'
|
|
|
|
attribute string.
|
|
|
|
\end{funcdesc}
|
|
|
|
|
|
|
|
\begin{funcdesc}{make_table}{fromlines, tolines
|
|
|
|
\optional{, fromdesc
|
|
|
|
\optional{, todesc
|
|
|
|
\optional{, context
|
|
|
|
\optional{, numlines
|
|
|
|
\optional{, summary}}}}}}
|
|
|
|
Compares \var{fromlines} and \var{tolines} (lists of strings) and returns
|
|
|
|
a string which is a complete HTML table showing line by line differences
|
|
|
|
with inter-line and intra-line changes highlighted.
|
|
|
|
|
|
|
|
The arguments of this method are a subset of those for the
|
|
|
|
\code{make_file} method. Please refer to the \code{make_file} method
|
|
|
|
documentation.
|
|
|
|
\end{funcdesc}
|
|
|
|
|
|
|
|
\file{Tools/scripts/ndiff.py} is a command-line front-end to this class
|
|
|
|
and contains a good example of its use.
|
|
|
|
\end{classdesc*}
|
|
|
|
|
| \begin{funcdesc}{context_diff}{a, b\optional{, fromfile\optional{, tofile
|
|
\begin{funcdesc}{context_diff}{a, b\optional{, fromfile\optional{, tofile
|
| \optional{, fromfiledate\optional{, tofiledate\optional{, n
|
|
\optional{, fromfiledate\optional{, tofiledate\optional{, n
|
| \optional{, lineterm}}}}}}}
|
|
\optional{, lineterm}}}}}}}
|
| Compare \var{a} and \var{b} (lists of strings); return a
|
|
Compare \var{a} and \var{b} (lists of strings); return a
|
| delta (a generator generating the delta lines) in context diff
|
|
delta (a generator generating the delta lines) in context diff
|
| format.
|
|
format.
|
|
|
|
|
| Context diffs are a compact way of showing just the lines that have
|
|
Context diffs are a compact way of showing just the lines that have
|
| changed plus a few lines of context. The changes are shown in a
|
|
changed plus a few lines of context. The changes are shown in a
|
| before/after style. The number of context lines is set by \var{n}
|
|
before/after style. The number of context lines is set by \var{n}
|
| which defaults to three.
|
|
which defaults to three.
|
|
|
|
|
| By default, the diff control lines (those with \code{***} or \code{---})
|
|
By default, the diff control lines (those with \code{***} or \code{---})
|
| are created with a trailing newline. This is helpful so that inputs created
|
|
are created with a trailing newline. This is helpful so that inputs created
|
| from \function{file.readlines()} result in diffs that are suitable for use
|
|
from \function{file.readlines()} result in diffs that are suitable for use
|
| with \function{file.writelines()} since both the inputs and outputs have
|
|
with \function{file.writelines()} since both the inputs and outputs have
|
| trailing newlines.
|
|
trailing newlines.
|
|
|
|
|
| For inputs that do not have trailing newlines, set the \var{lineterm}
|
|
For inputs that do not have trailing newlines, set the \var{lineterm}
|
| argument to \code{""} so that the output will be uniformly newline free.
|
|
argument to \code{""} so that the output will be uniformly newline free.
|
|
|
|
|
| The context diff format normally has a header for filenames and
|
|
The context diff format normally has a header for filenames and
|
| modification times. Any or all of these may be specified using strings for
|
|
modification times. Any or all of these may be specified using strings for
|
| \var{fromfile}, \var{tofile}, \var{fromfiledate}, and \var{tofiledate}.
|
|
\var{fromfile}, \var{tofile}, \var{fromfiledate}, and \var{tofiledate}.
|
| The modification times are normally expressed in the format returned by
|
|
The modification times are normally expressed in the format returned by
|
| \function{time.ctime()}. If not specified, the strings default to blanks.
|
|
\function{time.ctime()}. If not specified, the strings default to blanks.
|
|
|
|
|
| \file{Tools/scripts/diff.py} is a command-line front-end for this
|
|
\file{Tools/scripts/diff.py} is a command-line front-end for this
|
| function.
|
|
function.
|
|
|
|
|
| \versionadded{2.3}
|
|
\versionadded{2.3}
|
| \end{funcdesc}
|
|
\end{funcdesc}
|
|
|
|
|
| \begin{funcdesc}{get_close_matches}{word, possibilities\optional{,
|
|
\begin{funcdesc}{get_close_matches}{word, possibilities\optional{,
|
| n\optional{, cutoff}}}
|
|
n\optional{, cutoff}}}
|
| Return a list of the best ``good enough'' matches. \var{word} is a
|
|
Return a list of the best ``good enough'' matches. \var{word} is a
|
| sequence for which close matches are desired (typically a string),
|
|
sequence for which close matches are desired (typically a string),
|
| and \var{possibilities} is a list of sequences against which to
|
|
and \var{possibilities} is a list of sequences against which to
|
| match \var{word} (typically a list of strings).
|
|
match \var{word} (typically a list of strings).
|
|
|
|
|
| Optional argument \var{n} (default \code{3}) is the maximum number
|
|
Optional argument \var{n} (default \code{3}) is the maximum number
|
| of close matches to return; \var{n} must be greater than \code{0}.
|
|
of close matches to return; \var{n} must be greater than \code{0}.
|
|
|
|
|
| Optional argument \var{cutoff} (default \code{0.6}) is a float in
|
|
Optional argument \var{cutoff} (default \code{0.6}) is a float in
|
| the range [0, 1]. Possibilities that don't score at least that
|
|
the range [0, 1]. Possibilities that don't score at least that
|
| similar to \var{word} are ignored.
|
|
similar to \var{word} are ignored.
|
|
|
|
|
| The best (no more than \var{n}) matches among the possibilities are
|
|
The best (no more than \var{n}) matches among the possibilities are
|
| returned in a list, sorted by similarity score, most similar first.
|
|
returned in a list, sorted by similarity score, most similar first.
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
|
|
>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
|
| ['apple', 'ape']
|
|
['apple', 'ape']
|
| >>> import keyword
|
|
>>> import keyword
|
| >>> get_close_matches('wheel', keyword.kwlist)
|
|
>>> get_close_matches('wheel', keyword.kwlist)
|
| ['while']
|
|
['while']
|
| >>> get_close_matches('apple', keyword.kwlist)
|
|
>>> get_close_matches('apple', keyword.kwlist)
|
| []
|
|
[]
|
| >>> get_close_matches('accept', keyword.kwlist)
|
|
>>> get_close_matches('accept', keyword.kwlist)
|
| ['except']
|
|
['except']
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
t |
\end{funcdesc}
|
|
|
|
|
|
|
|
\begin{funcdesc}{mdiff}{fromlines, tolines, chgfmt, linefmt
|
|
|
|
\optional{, context
|
|
|
|
\optional{, sep
|
|
|
|
\optional{, linejunk
|
|
|
|
\optional{, charjunk}}}}}
|
|
|
|
Compare \var{fromlines} and \var{tolines} (lists of strings); return a
|
|
|
|
generator generating marked up differences to be used for creating side
|
|
|
|
by side differences. Note, most users should use the \class{HtmlDiff} class
|
|
|
|
to produce HTML side by side differences.
|
|
|
|
|
|
|
|
\var{chgfmt} and \var{linefmt} are for filter functions to markup intra-line
|
|
|
|
differences and complete lines respectively.
|
|
|
|
|
|
|
|
Optional keyword parameter \var{context} specifies number of lines of
|
|
|
|
context (default is \code{None} for full differences) while \var{sep}
|
|
|
|
specifies the separator string between contextual differences (default
|
|
|
|
is \code{None}).
|
|
|
|
|
|
|
|
Optional keyword parameters \var{linejunk} and \var{charjunk} are
|
|
|
|
for filter functions (or \code{None}) and their description can be found
|
|
|
|
in the \function{ndiff()} documentation (\function{mdiff()} utilizes
|
|
|
|
\function{ndiff()} and passes these parameters to it).
|
|
|
|
|
|
|
|
This function was originally developed for use by the \class{HtmlDiff} for
|
|
|
|
generating side by side HTML differences but can be used for generating
|
|
|
|
side by side difference representations for any markup language. See
|
|
|
|
\class{HtmlDiff} for an example usage of this function.
|
| \end{funcdesc}
|
|
\end{funcdesc}
|
|
|
|
|
| \begin{funcdesc}{ndiff}{a, b\optional{, linejunk\optional{,
|
|
\begin{funcdesc}{ndiff}{a, b\optional{, linejunk\optional{,
|
| charjunk}}}
|
|
charjunk}}}
|
| Compare \var{a} and \var{b} (lists of strings); return a
|
|
Compare \var{a} and \var{b} (lists of strings); return a
|
| \class{Differ}-style delta (a generator generating the delta lines).
|
|
\class{Differ}-style delta (a generator generating the delta lines).
|
|
|
|
|
| Optional keyword parameters \var{linejunk} and \var{charjunk} are
|
|
Optional keyword parameters \var{linejunk} and \var{charjunk} are
|
| for filter functions (or \code{None}):
|
|
for filter functions (or \code{None}):
|
|
|
|
|
| \var{linejunk}: A function that accepts a single string
|
|
\var{linejunk}: A function that accepts a single string
|
| argument, and returns true if the string is junk, or false if not.
|
|
argument, and returns true if the string is junk, or false if not.
|
| The default is (\code{None}), starting with Python 2.3. Before then,
|
|
The default is (\code{None}), starting with Python 2.3. Before then,
|
| the default was the module-level function
|
|
the default was the module-level function
|
| \function{IS_LINE_JUNK()}, which filters out lines without visible
|
|
\function{IS_LINE_JUNK()}, which filters out lines without visible
|
| characters, except for at most one pound character (\character{\#}).
|
|
characters, except for at most one pound character (\character{\#}).
|
| As of Python 2.3, the underlying \class{SequenceMatcher} class
|
|
As of Python 2.3, the underlying \class{SequenceMatcher} class
|
| does a dynamic analysis of which lines are so frequent as to
|
|
does a dynamic analysis of which lines are so frequent as to
|
| constitute noise, and this usually works better than the pre-2.3
|
|
constitute noise, and this usually works better than the pre-2.3
|
| default.
|
|
default.
|
|
|
|
|
| \var{charjunk}: A function that accepts a character (a string of
|
|
\var{charjunk}: A function that accepts a character (a string of
|
| length 1), and returns if the character is junk, or false if not.
|
|
length 1), and returns if the character is junk, or false if not.
|
| The default is module-level function \function{IS_CHARACTER_JUNK()},
|
|
The default is module-level function \function{IS_CHARACTER_JUNK()},
|
| which filters out whitespace characters (a blank or tab; note: bad
|
|
which filters out whitespace characters (a blank or tab; note: bad
|
| idea to include newline in this!).
|
|
idea to include newline in this!).
|
|
|
|
|
| \file{Tools/scripts/ndiff.py} is a command-line front-end to this
|
|
\file{Tools/scripts/ndiff.py} is a command-line front-end to this
|
| function.
|
|
function.
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
|
|
>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
|
| ... 'ore\ntree\nemu\n'.splitlines(1))
|
|
... 'ore\ntree\nemu\n'.splitlines(1))
|
| >>> print ''.join(diff),
|
|
>>> print ''.join(diff),
|
| - one
|
|
- one
|
| ? ^
|
|
? ^
|
| + ore
|
|
+ ore
|
| ? ^
|
|
? ^
|
| - two
|
|
- two
|
| - three
|
|
- three
|
| ? -
|
|
? -
|
| + tree
|
|
+ tree
|
| + emu
|
|
+ emu
|
| \end{verbatim}
|
|
\end{verbatim}
|
| \end{funcdesc}
|
|
\end{funcdesc}
|
|
|
|
|
| \begin{funcdesc}{restore}{sequence, which}
|
|
\begin{funcdesc}{restore}{sequence, which}
|
| Return one of the two sequences that generated a delta.
|
|
Return one of the two sequences that generated a delta.
|
|
|
|
|
| Given a \var{sequence} produced by \method{Differ.compare()} or
|
|
Given a \var{sequence} produced by \method{Differ.compare()} or
|
| \function{ndiff()}, extract lines originating from file 1 or 2
|
|
\function{ndiff()}, extract lines originating from file 1 or 2
|
| (parameter \var{which}), stripping off line prefixes.
|
|
(parameter \var{which}), stripping off line prefixes.
|
|
|
|
|
| Example:
|
|
Example:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
|
|
>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
|
| ... 'ore\ntree\nemu\n'.splitlines(1))
|
|
... 'ore\ntree\nemu\n'.splitlines(1))
|
| >>> diff = list(diff) # materialize the generated delta into a list
|
|
>>> diff = list(diff) # materialize the generated delta into a list
|
| >>> print ''.join(restore(diff, 1)),
|
|
>>> print ''.join(restore(diff, 1)),
|
| one
|
|
one
|
| two
|
|
two
|
| three
|
|
three
|
| >>> print ''.join(restore(diff, 2)),
|
|
>>> print ''.join(restore(diff, 2)),
|
| ore
|
|
ore
|
| tree
|
|
tree
|
| emu
|
|
emu
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| \end{funcdesc}
|
|
\end{funcdesc}
|
|
|
|
|
| \begin{funcdesc}{unified_diff}{a, b\optional{, fromfile\optional{, tofile
|
|
\begin{funcdesc}{unified_diff}{a, b\optional{, fromfile\optional{, tofile
|
| \optional{, fromfiledate\optional{, tofiledate\optional{, n
|
|
\optional{, fromfiledate\optional{, tofiledate\optional{, n
|
| \optional{, lineterm}}}}}}}
|
|
\optional{, lineterm}}}}}}}
|
| Compare \var{a} and \var{b} (lists of strings); return a
|
|
Compare \var{a} and \var{b} (lists of strings); return a
|
| delta (a generator generating the delta lines) in unified diff
|
|
delta (a generator generating the delta lines) in unified diff
|
| format.
|
|
format.
|
|
|
|
|
| Unified diffs are a compact way of showing just the lines that have
|
|
Unified diffs are a compact way of showing just the lines that have
|
| changed plus a few lines of context. The changes are shown in a
|
|
changed plus a few lines of context. The changes are shown in a
|
| inline style (instead of separate before/after blocks). The number
|
|
inline style (instead of separate before/after blocks). The number
|
| of context lines is set by \var{n} which defaults to three.
|
|
of context lines is set by \var{n} which defaults to three.
|
|
|
|
|
| By default, the diff control lines (those with \code{---}, \code{+++},
|
|
By default, the diff control lines (those with \code{---}, \code{+++},
|
| or \code{@@}) are created with a trailing newline. This is helpful so
|
|
or \code{@@}) are created with a trailing newline. This is helpful so
|
| that inputs created from \function{file.readlines()} result in diffs
|
|
that inputs created from \function{file.readlines()} result in diffs
|
| that are suitable for use with \function{file.writelines()} since both
|
|
that are suitable for use with \function{file.writelines()} since both
|
| the inputs and outputs have trailing newlines.
|
|
the inputs and outputs have trailing newlines.
|
|
|
|
|
| For inputs that do not have trailing newlines, set the \var{lineterm}
|
|
For inputs that do not have trailing newlines, set the \var{lineterm}
|
| argument to \code{""} so that the output will be uniformly newline free.
|
|
argument to \code{""} so that the output will be uniformly newline free.
|
|
|
|
|
| The context diff format normally has a header for filenames and
|
|
The context diff format normally has a header for filenames and
|
| modification times. Any or all of these may be specified using strings for
|
|
modification times. Any or all of these may be specified using strings for
|
| \var{fromfile}, \var{tofile}, \var{fromfiledate}, and \var{tofiledate}.
|
|
\var{fromfile}, \var{tofile}, \var{fromfiledate}, and \var{tofiledate}.
|
| The modification times are normally expressed in the format returned by
|
|
The modification times are normally expressed in the format returned by
|
| \function{time.ctime()}. If not specified, the strings default to blanks.
|
|
\function{time.ctime()}. If not specified, the strings default to blanks.
|
|
|
|
|
| \file{Tools/scripts/diff.py} is a command-line front-end for this
|
|
\file{Tools/scripts/diff.py} is a command-line front-end for this
|
| function.
|
|
function.
|
|
|
|
|
| \versionadded{2.3}
|
|
\versionadded{2.3}
|
| \end{funcdesc}
|
|
\end{funcdesc}
|
|
|
|
|
| \begin{funcdesc}{IS_LINE_JUNK}{line}
|
|
\begin{funcdesc}{IS_LINE_JUNK}{line}
|
| Return true for ignorable lines. The line \var{line} is ignorable
|
|
Return true for ignorable lines. The line \var{line} is ignorable
|
| if \var{line} is blank or contains a single \character{\#},
|
|
if \var{line} is blank or contains a single \character{\#},
|
| otherwise it is not ignorable. Used as a default for parameter
|
|
otherwise it is not ignorable. Used as a default for parameter
|
| \var{linejunk} in \function{ndiff()} before Python 2.3.
|
|
\var{linejunk} in \function{ndiff()} before Python 2.3.
|
| \end{funcdesc}
|
|
\end{funcdesc}
|
|
|
|
|
|
|
|
|
| \begin{funcdesc}{IS_CHARACTER_JUNK}{ch}
|
|
\begin{funcdesc}{IS_CHARACTER_JUNK}{ch}
|
| Return true for ignorable characters. The character \var{ch} is
|
|
Return true for ignorable characters. The character \var{ch} is
|
| ignorable if \var{ch} is a space or tab, otherwise it is not
|
|
ignorable if \var{ch} is a space or tab, otherwise it is not
|
| ignorable. Used as a default for parameter \var{charjunk} in
|
|
ignorable. Used as a default for parameter \var{charjunk} in
|
| \function{ndiff()}.
|
|
\function{ndiff()}.
|
| \end{funcdesc}
|
|
\end{funcdesc}
|
|
|
|
|
|
|
|
|
| \begin{seealso}
|
|
\begin{seealso}
|
| \seetitle[http://www.ddj.com/documents/s=1103/ddj8807c/]
|
|
\seetitle[http://www.ddj.com/documents/s=1103/ddj8807c/]
|
| {Pattern Matching: The Gestalt Approach}{Discussion of a
|
|
{Pattern Matching: The Gestalt Approach}{Discussion of a
|
| similar algorithm by John W. Ratcliff and D. E. Metzener.
|
|
similar algorithm by John W. Ratcliff and D. E. Metzener.
|
| This was published in
|
|
This was published in
|
| \citetitle[http://www.ddj.com/]{Dr. Dobb's Journal} in
|
|
\citetitle[http://www.ddj.com/]{Dr. Dobb's Journal} in
|
| July, 1988.}
|
|
July, 1988.}
|
| \end{seealso}
|
|
\end{seealso}
|
|
|
|
|
|
|
|
|
| \subsection{SequenceMatcher Objects \label{sequence-matcher}}
|
|
\subsection{SequenceMatcher Objects \label{sequence-matcher}}
|
|
|
|
|
| The \class{SequenceMatcher} class has this constructor:
|
|
The \class{SequenceMatcher} class has this constructor:
|
|
|
|
|
| \begin{classdesc}{SequenceMatcher}{\optional{isjunk\optional{,
|
|
\begin{classdesc}{SequenceMatcher}{\optional{isjunk\optional{,
|
| a\optional{, b}}}}
|
|
a\optional{, b}}}}
|
| Optional argument \var{isjunk} must be \code{None} (the default) or
|
|
Optional argument \var{isjunk} must be \code{None} (the default) or
|
| a one-argument function that takes a sequence element and returns
|
|
a one-argument function that takes a sequence element and returns
|
| true if and only if the element is ``junk'' and should be ignored.
|
|
true if and only if the element is ``junk'' and should be ignored.
|
| Passing \code{None} for \var{b} is equivalent to passing
|
|
Passing \code{None} for \var{b} is equivalent to passing
|
| \code{lambda x: 0}; in other words, no elements are ignored. For
|
|
\code{lambda x: 0}; in other words, no elements are ignored. For
|
| example, pass:
|
|
example, pass:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| lambda x: x in " \t"
|
|
lambda x: x in " \t"
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| if you're comparing lines as sequences of characters, and don't want
|
|
if you're comparing lines as sequences of characters, and don't want
|
| to synch up on blanks or hard tabs.
|
|
to synch up on blanks or hard tabs.
|
|
|
|
|
| The optional arguments \var{a} and \var{b} are sequences to be
|
|
The optional arguments \var{a} and \var{b} are sequences to be
|
| compared; both default to empty strings. The elements of both
|
|
compared; both default to empty strings. The elements of both
|
| sequences must be hashable.
|
|
sequences must be hashable.
|
| \end{classdesc}
|
|
\end{classdesc}
|
|
|
|
|
|
|
|
|
| \class{SequenceMatcher} objects have the following methods:
|
|
\class{SequenceMatcher} objects have the following methods:
|
|
|
|
|
| \begin{methoddesc}{set_seqs}{a, b}
|
|
\begin{methoddesc}{set_seqs}{a, b}
|
| Set the two sequences to be compared.
|
|
Set the two sequences to be compared.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \class{SequenceMatcher} computes and caches detailed information about
|
|
\class{SequenceMatcher} computes and caches detailed information about
|
| the second sequence, so if you want to compare one sequence against
|
|
the second sequence, so if you want to compare one sequence against
|
| many sequences, use \method{set_seq2()} to set the commonly used
|
|
many sequences, use \method{set_seq2()} to set the commonly used
|
| sequence once and call \method{set_seq1()} repeatedly, once for each
|
|
sequence once and call \method{set_seq1()} repeatedly, once for each
|
| of the other sequences.
|
|
of the other sequences.
|
|
|
|
|
| \begin{methoddesc}{set_seq1}{a}
|
|
\begin{methoddesc}{set_seq1}{a}
|
| Set the first sequence to be compared. The second sequence to be
|
|
Set the first sequence to be compared. The second sequence to be
|
| compared is not changed.
|
|
compared is not changed.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{set_seq2}{b}
|
|
\begin{methoddesc}{set_seq2}{b}
|
| Set the second sequence to be compared. The first sequence to be
|
|
Set the second sequence to be compared. The first sequence to be
|
| compared is not changed.
|
|
compared is not changed.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{find_longest_match}{alo, ahi, blo, bhi}
|
|
\begin{methoddesc}{find_longest_match}{alo, ahi, blo, bhi}
|
| Find longest matching block in \code{\var{a}[\var{alo}:\var{ahi}]}
|
|
Find longest matching block in \code{\var{a}[\var{alo}:\var{ahi}]}
|
| and \code{\var{b}[\var{blo}:\var{bhi}]}.
|
|
and \code{\var{b}[\var{blo}:\var{bhi}]}.
|
|
|
|
|
| If \var{isjunk} was omitted or \code{None},
|
|
If \var{isjunk} was omitted or \code{None},
|
| \method{get_longest_match()} returns \code{(\var{i}, \var{j},
|
|
\method{get_longest_match()} returns \code{(\var{i}, \var{j},
|
| \var{k})} such that \code{\var{a}[\var{i}:\var{i}+\var{k}]} is equal
|
|
\var{k})} such that \code{\var{a}[\var{i}:\var{i}+\var{k}]} is equal
|
| to \code{\var{b}[\var{j}:\var{j}+\var{k}]}, where
|
|
to \code{\var{b}[\var{j}:\var{j}+\var{k}]}, where
|
| \code{\var{alo} <= \var{i} <= \var{i}+\var{k} <= \var{ahi}} and
|
|
\code{\var{alo} <= \var{i} <= \var{i}+\var{k} <= \var{ahi}} and
|
| \code{\var{blo} <= \var{j} <= \var{j}+\var{k} <= \var{bhi}}.
|
|
\code{\var{blo} <= \var{j} <= \var{j}+\var{k} <= \var{bhi}}.
|
| For all \code{(\var{i'}, \var{j'}, \var{k'})} meeting those
|
|
For all \code{(\var{i'}, \var{j'}, \var{k'})} meeting those
|
| conditions, the additional conditions
|
|
conditions, the additional conditions
|
| \code{\var{k} >= \var{k'}},
|
|
\code{\var{k} >= \var{k'}},
|
| \code{\var{i} <= \var{i'}},
|
|
\code{\var{i} <= \var{i'}},
|
| and if \code{\var{i} == \var{i'}}, \code{\var{j} <= \var{j'}}
|
|
and if \code{\var{i} == \var{i'}}, \code{\var{j} <= \var{j'}}
|
| are also met.
|
|
are also met.
|
| In other words, of all maximal matching blocks, return one that
|
|
In other words, of all maximal matching blocks, return one that
|
| starts earliest in \var{a}, and of all those maximal matching blocks
|
|
starts earliest in \var{a}, and of all those maximal matching blocks
|
| that start earliest in \var{a}, return the one that starts earliest
|
|
that start earliest in \var{a}, return the one that starts earliest
|
| in \var{b}.
|
|
in \var{b}.
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
|
|
>>> s = SequenceMatcher(None, " abcd", "abcd abcd")
|
| >>> s.find_longest_match(0, 5, 0, 9)
|
|
>>> s.find_longest_match(0, 5, 0, 9)
|
| (0, 4, 5)
|
|
(0, 4, 5)
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| If \var{isjunk} was provided, first the longest matching block is
|
|
If \var{isjunk} was provided, first the longest matching block is
|
| determined as above, but with the additional restriction that no
|
|
determined as above, but with the additional restriction that no
|
| junk element appears in the block. Then that block is extended as
|
|
junk element appears in the block. Then that block is extended as
|
| far as possible by matching (only) junk elements on both sides.
|
|
far as possible by matching (only) junk elements on both sides.
|
| So the resulting block never matches on junk except as identical
|
|
So the resulting block never matches on junk except as identical
|
| junk happens to be adjacent to an interesting match.
|
|
junk happens to be adjacent to an interesting match.
|
|
|
|
|
| Here's the same example as before, but considering blanks to be junk.
|
|
Here's the same example as before, but considering blanks to be junk.
|
| That prevents \code{' abcd'} from matching the \code{' abcd'} at the
|
|
That prevents \code{' abcd'} from matching the \code{' abcd'} at the
|
| tail end of the second sequence directly. Instead only the
|
|
tail end of the second sequence directly. Instead only the
|
| \code{'abcd'} can match, and matches the leftmost \code{'abcd'} in
|
|
\code{'abcd'} can match, and matches the leftmost \code{'abcd'} in
|
| the second sequence:
|
|
the second sequence:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
|
|
>>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
|
| >>> s.find_longest_match(0, 5, 0, 9)
|
|
>>> s.find_longest_match(0, 5, 0, 9)
|
| (1, 0, 4)
|
|
(1, 0, 4)
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| If no blocks match, this returns \code{(\var{alo}, \var{blo}, 0)}.
|
|
If no blocks match, this returns \code{(\var{alo}, \var{blo}, 0)}.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{get_matching_blocks}{}
|
|
\begin{methoddesc}{get_matching_blocks}{}
|
| Return list of triples describing matching subsequences.
|
|
Return list of triples describing matching subsequences.
|
| Each triple is of the form \code{(\var{i}, \var{j}, \var{n})}, and
|
|
Each triple is of the form \code{(\var{i}, \var{j}, \var{n})}, and
|
| means that \code{\var{a}[\var{i}:\var{i}+\var{n}] ==
|
|
means that \code{\var{a}[\var{i}:\var{i}+\var{n}] ==
|
| \var{b}[\var{j}:\var{j}+\var{n}]}. The triples are monotonically
|
|
\var{b}[\var{j}:\var{j}+\var{n}]}. The triples are monotonically
|
| increasing in \var{i} and \var{j}.
|
|
increasing in \var{i} and \var{j}.
|
|
|
|
|
| The last triple is a dummy, and has the value \code{(len(\var{a}),
|
|
The last triple is a dummy, and has the value \code{(len(\var{a}),
|
| len(\var{b}), 0)}. It is the only triple with \code{\var{n} == 0}.
|
|
len(\var{b}), 0)}. It is the only triple with \code{\var{n} == 0}.
|
| % Explain why a dummy is used!
|
|
% Explain why a dummy is used!
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> s = SequenceMatcher(None, "abxcd", "abcd")
|
|
>>> s = SequenceMatcher(None, "abxcd", "abcd")
|
| >>> s.get_matching_blocks()
|
|
>>> s.get_matching_blocks()
|
| [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
|
|
[(0, 0, 2), (3, 2, 2), (5, 4, 0)]
|
| \end{verbatim}
|
|
\end{verbatim}
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{get_opcodes}{}
|
|
\begin{methoddesc}{get_opcodes}{}
|
| Return list of 5-tuples describing how to turn \var{a} into \var{b}.
|
|
Return list of 5-tuples describing how to turn \var{a} into \var{b}.
|
| Each tuple is of the form \code{(\var{tag}, \var{i1}, \var{i2},
|
|
Each tuple is of the form \code{(\var{tag}, \var{i1}, \var{i2},
|
| \var{j1}, \var{j2})}. The first tuple has \code{\var{i1} ==
|
|
\var{j1}, \var{j2})}. The first tuple has \code{\var{i1} ==
|
| \var{j1} == 0}, and remaining tuples have \var{i1} equal to the
|
|
\var{j1} == 0}, and remaining tuples have \var{i1} equal to the
|
| \var{i2} from the preceeding tuple, and, likewise, \var{j1} equal to
|
|
\var{i2} from the preceeding tuple, and, likewise, \var{j1} equal to
|
| the previous \var{j2}.
|
|
the previous \var{j2}.
|
|
|
|
|
| The \var{tag} values are strings, with these meanings:
|
|
The \var{tag} values are strings, with these meanings:
|
|
|
|
|
| \begin{tableii}{l|l}{code}{Value}{Meaning}
|
|
\begin{tableii}{l|l}{code}{Value}{Meaning}
|
| \lineii{'replace'}{\code{\var{a}[\var{i1}:\var{i2}]} should be
|
|
\lineii{'replace'}{\code{\var{a}[\var{i1}:\var{i2}]} should be
|
| replaced by \code{\var{b}[\var{j1}:\var{j2}]}.}
|
|
replaced by \code{\var{b}[\var{j1}:\var{j2}]}.}
|
| \lineii{'delete'}{\code{\var{a}[\var{i1}:\var{i2}]} should be
|
|
\lineii{'delete'}{\code{\var{a}[\var{i1}:\var{i2}]} should be
|
| deleted. Note that \code{\var{j1} == \var{j2}} in
|
|
deleted. Note that \code{\var{j1} == \var{j2}} in
|
| this case.}
|
|
this case.}
|
| \lineii{'insert'}{\code{\var{b}[\var{j1}:\var{j2}]} should be
|
|
\lineii{'insert'}{\code{\var{b}[\var{j1}:\var{j2}]} should be
|
| inserted at \code{\var{a}[\var{i1}:\var{i1}]}.
|
|
inserted at \code{\var{a}[\var{i1}:\var{i1}]}.
|
| Note that \code{\var{i1} == \var{i2}} in this
|
|
Note that \code{\var{i1} == \var{i2}} in this
|
| case.}
|
|
case.}
|
| \lineii{'equal'}{\code{\var{a}[\var{i1}:\var{i2}] ==
|
|
\lineii{'equal'}{\code{\var{a}[\var{i1}:\var{i2}] ==
|
| \var{b}[\var{j1}:\var{j2}]} (the sub-sequences are
|
|
\var{b}[\var{j1}:\var{j2}]} (the sub-sequences are
|
| equal).}
|
|
equal).}
|
| \end{tableii}
|
|
\end{tableii}
|
|
|
|
|
| For example:
|
|
For example:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> a = "qabxcd"
|
|
>>> a = "qabxcd"
|
| >>> b = "abycdf"
|
|
>>> b = "abycdf"
|
| >>> s = SequenceMatcher(None, a, b)
|
|
>>> s = SequenceMatcher(None, a, b)
|
| >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
|
|
>>> for tag, i1, i2, j1, j2 in s.get_opcodes():
|
| ... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
|
|
... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
|
| ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
|
|
... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
|
| delete a[0:1] (q) b[0:0] ()
|
|
delete a[0:1] (q) b[0:0] ()
|
| equal a[1:3] (ab) b[0:2] (ab)
|
|
equal a[1:3] (ab) b[0:2] (ab)
|
| replace a[3:4] (x) b[2:3] (y)
|
|
replace a[3:4] (x) b[2:3] (y)
|
| equal a[4:6] (cd) b[3:5] (cd)
|
|
equal a[4:6] (cd) b[3:5] (cd)
|
| insert a[6:6] () b[5:6] (f)
|
|
insert a[6:6] () b[5:6] (f)
|
| \end{verbatim}
|
|
\end{verbatim}
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{get_grouped_opcodes}{\optional{n}}
|
|
\begin{methoddesc}{get_grouped_opcodes}{\optional{n}}
|
| Return a generator of groups with up to \var{n} lines of context.
|
|
Return a generator of groups with up to \var{n} lines of context.
|
|
|
|
|
| Starting with the groups returned by \method{get_opcodes()},
|
|
Starting with the groups returned by \method{get_opcodes()},
|
| this method splits out smaller change clusters and eliminates
|
|
this method splits out smaller change clusters and eliminates
|
| intervening ranges which have no changes.
|
|
intervening ranges which have no changes.
|
|
|
|
|
| The groups are returned in the same format as \method{get_opcodes()}.
|
|
The groups are returned in the same format as \method{get_opcodes()}.
|
| \versionadded{2.3}
|
|
\versionadded{2.3}
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{ratio}{}
|
|
\begin{methoddesc}{ratio}{}
|
| Return a measure of the sequences' similarity as a float in the
|
|
Return a measure of the sequences' similarity as a float in the
|
| range [0, 1].
|
|
range [0, 1].
|
|
|
|
|
| Where T is the total number of elements in both sequences, and M is
|
|
Where T is the total number of elements in both sequences, and M is
|
| the number of matches, this is 2.0*M / T. Note that this is
|
|
the number of matches, this is 2.0*M / T. Note that this is
|
| \code{1.0} if the sequences are identical, and \code{0.0} if they
|
|
\code{1.0} if the sequences are identical, and \code{0.0} if they
|
| have nothing in common.
|
|
have nothing in common.
|
|
|
|
|
| This is expensive to compute if \method{get_matching_blocks()} or
|
|
This is expensive to compute if \method{get_matching_blocks()} or
|
| \method{get_opcodes()} hasn't already been called, in which case you
|
|
\method{get_opcodes()} hasn't already been called, in which case you
|
| may want to try \method{quick_ratio()} or
|
|
may want to try \method{quick_ratio()} or
|
| \method{real_quick_ratio()} first to get an upper bound.
|
|
\method{real_quick_ratio()} first to get an upper bound.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{quick_ratio}{}
|
|
\begin{methoddesc}{quick_ratio}{}
|
| Return an upper bound on \method{ratio()} relatively quickly.
|
|
Return an upper bound on \method{ratio()} relatively quickly.
|
|
|
|
|
| This isn't defined beyond that it is an upper bound on
|
|
This isn't defined beyond that it is an upper bound on
|
| \method{ratio()}, and is faster to compute.
|
|
\method{ratio()}, and is faster to compute.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| \begin{methoddesc}{real_quick_ratio}{}
|
|
\begin{methoddesc}{real_quick_ratio}{}
|
| Return an upper bound on \method{ratio()} very quickly.
|
|
Return an upper bound on \method{ratio()} very quickly.
|
|
|
|
|
| This isn't defined beyond that it is an upper bound on
|
|
This isn't defined beyond that it is an upper bound on
|
| \method{ratio()}, and is faster to compute than either
|
|
\method{ratio()}, and is faster to compute than either
|
| \method{ratio()} or \method{quick_ratio()}.
|
|
\method{ratio()} or \method{quick_ratio()}.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
| The three methods that return the ratio of matching to total characters
|
|
The three methods that return the ratio of matching to total characters
|
| can give different results due to differing levels of approximation,
|
|
can give different results due to differing levels of approximation,
|
| although \method{quick_ratio()} and \method{real_quick_ratio()} are always
|
|
although \method{quick_ratio()} and \method{real_quick_ratio()} are always
|
| at least as large as \method{ratio()}:
|
|
at least as large as \method{ratio()}:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> s = SequenceMatcher(None, "abcd", "bcde")
|
|
>>> s = SequenceMatcher(None, "abcd", "bcde")
|
| >>> s.ratio()
|
|
>>> s.ratio()
|
| 0.75
|
|
0.75
|
| >>> s.quick_ratio()
|
|
>>> s.quick_ratio()
|
| 0.75
|
|
0.75
|
| >>> s.real_quick_ratio()
|
|
>>> s.real_quick_ratio()
|
| 1.0
|
|
1.0
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
|
|
|
|
| \subsection{SequenceMatcher Examples \label{sequencematcher-examples}}
|
|
\subsection{SequenceMatcher Examples \label{sequencematcher-examples}}
|
|
|
|
|
|
|
|
|
| This example compares two strings, considering blanks to be ``junk:''
|
|
This example compares two strings, considering blanks to be ``junk:''
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> s = SequenceMatcher(lambda x: x == " ",
|
|
>>> s = SequenceMatcher(lambda x: x == " ",
|
| ... "private Thread currentThread;",
|
|
... "private Thread currentThread;",
|
| ... "private volatile Thread currentThread;")
|
|
... "private volatile Thread currentThread;")
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| \method{ratio()} returns a float in [0, 1], measuring the similarity
|
|
\method{ratio()} returns a float in [0, 1], measuring the similarity
|
| of the sequences. As a rule of thumb, a \method{ratio()} value over
|
|
of the sequences. As a rule of thumb, a \method{ratio()} value over
|
| 0.6 means the sequences are close matches:
|
|
0.6 means the sequences are close matches:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> print round(s.ratio(), 3)
|
|
>>> print round(s.ratio(), 3)
|
| 0.866
|
|
0.866
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| If you're only interested in where the sequences match,
|
|
If you're only interested in where the sequences match,
|
| \method{get_matching_blocks()} is handy:
|
|
\method{get_matching_blocks()} is handy:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> for block in s.get_matching_blocks():
|
|
>>> for block in s.get_matching_blocks():
|
| ... print "a[%d] and b[%d] match for %d elements" % block
|
|
... print "a[%d] and b[%d] match for %d elements" % block
|
| a[0] and b[0] match for 8 elements
|
|
a[0] and b[0] match for 8 elements
|
| a[8] and b[17] match for 6 elements
|
|
a[8] and b[17] match for 6 elements
|
| a[14] and b[23] match for 15 elements
|
|
a[14] and b[23] match for 15 elements
|
| a[29] and b[38] match for 0 elements
|
|
a[29] and b[38] match for 0 elements
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| Note that the last tuple returned by \method{get_matching_blocks()} is
|
|
Note that the last tuple returned by \method{get_matching_blocks()} is
|
| always a dummy, \code{(len(\var{a}), len(\var{b}), 0)}, and this is
|
|
always a dummy, \code{(len(\var{a}), len(\var{b}), 0)}, and this is
|
| the only case in which the last tuple element (number of elements
|
|
the only case in which the last tuple element (number of elements
|
| matched) is \code{0}.
|
|
matched) is \code{0}.
|
|
|
|
|
| If you want to know how to change the first sequence into the second,
|
|
If you want to know how to change the first sequence into the second,
|
| use \method{get_opcodes()}:
|
|
use \method{get_opcodes()}:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> for opcode in s.get_opcodes():
|
|
>>> for opcode in s.get_opcodes():
|
| ... print "%6s a[%d:%d] b[%d:%d]" % opcode
|
|
... print "%6s a[%d:%d] b[%d:%d]" % opcode
|
| equal a[0:8] b[0:8]
|
|
equal a[0:8] b[0:8]
|
| insert a[8:8] b[8:17]
|
|
insert a[8:8] b[8:17]
|
| equal a[8:14] b[17:23]
|
|
equal a[8:14] b[17:23]
|
| equal a[14:29] b[23:38]
|
|
equal a[14:29] b[23:38]
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| See also the function \function{get_close_matches()} in this module,
|
|
See also the function \function{get_close_matches()} in this module,
|
| which shows how simple code building on \class{SequenceMatcher} can be
|
|
which shows how simple code building on \class{SequenceMatcher} can be
|
| used to do useful work.
|
|
used to do useful work.
|
|
|
|
|
|
|
|
|
| \subsection{Differ Objects \label{differ-objects}}
|
|
\subsection{Differ Objects \label{differ-objects}}
|
|
|
|
|
| Note that \class{Differ}-generated deltas make no claim to be
|
|
Note that \class{Differ}-generated deltas make no claim to be
|
| \strong{minimal} diffs. To the contrary, minimal diffs are often
|
|
\strong{minimal} diffs. To the contrary, minimal diffs are often
|
| counter-intuitive, because they synch up anywhere possible, sometimes
|
|
counter-intuitive, because they synch up anywhere possible, sometimes
|
| accidental matches 100 pages apart. Restricting synch points to
|
|
accidental matches 100 pages apart. Restricting synch points to
|
| contiguous matches preserves some notion of locality, at the
|
|
contiguous matches preserves some notion of locality, at the
|
| occasional cost of producing a longer diff.
|
|
occasional cost of producing a longer diff.
|
|
|
|
|
| The \class{Differ} class has this constructor:
|
|
The \class{Differ} class has this constructor:
|
|
|
|
|
| \begin{classdesc}{Differ}{\optional{linejunk\optional{, charjunk}}}
|
|
\begin{classdesc}{Differ}{\optional{linejunk\optional{, charjunk}}}
|
| Optional keyword parameters \var{linejunk} and \var{charjunk} are
|
|
Optional keyword parameters \var{linejunk} and \var{charjunk} are
|
| for filter functions (or \code{None}):
|
|
for filter functions (or \code{None}):
|
|
|
|
|
| \var{linejunk}: A function that accepts a single string
|
|
\var{linejunk}: A function that accepts a single string
|
| argument, and returns true if the string is junk. The default is
|
|
argument, and returns true if the string is junk. The default is
|
| \code{None}, meaning that no line is considered junk.
|
|
\code{None}, meaning that no line is considered junk.
|
|
|
|
|
| \var{charjunk}: A function that accepts a single character argument
|
|
\var{charjunk}: A function that accepts a single character argument
|
| (a string of length 1), and returns true if the character is junk.
|
|
(a string of length 1), and returns true if the character is junk.
|
| The default is \code{None}, meaning that no character is
|
|
The default is \code{None}, meaning that no character is
|
| considered junk.
|
|
considered junk.
|
| \end{classdesc}
|
|
\end{classdesc}
|
|
|
|
|
| \class{Differ} objects are used (deltas generated) via a single
|
|
\class{Differ} objects are used (deltas generated) via a single
|
| method:
|
|
method:
|
|
|
|
|
| \begin{methoddesc}{compare}{a, b}
|
|
\begin{methoddesc}{compare}{a, b}
|
| Compare two sequences of lines, and generate the delta (a sequence
|
|
Compare two sequences of lines, and generate the delta (a sequence
|
| of lines).
|
|
of lines).
|
|
|
|
|
| Each sequence must contain individual single-line strings ending
|
|
Each sequence must contain individual single-line strings ending
|
| with newlines. Such sequences can be obtained from the
|
|
with newlines. Such sequences can be obtained from the
|
| \method{readlines()} method of file-like objects. The delta generated
|
|
\method{readlines()} method of file-like objects. The delta generated
|
| also consists of newline-terminated strings, ready to be printed as-is
|
|
also consists of newline-terminated strings, ready to be printed as-is
|
| via the \method{writelines()} method of a file-like object.
|
|
via the \method{writelines()} method of a file-like object.
|
| \end{methoddesc}
|
|
\end{methoddesc}
|
|
|
|
|
|
|
|
|
| \subsection{Differ Example \label{differ-examples}}
|
|
\subsection{Differ Example \label{differ-examples}}
|
|
|
|
|
| This example compares two texts. First we set up the texts, sequences
|
|
This example compares two texts. First we set up the texts, sequences
|
| of individual single-line strings ending with newlines (such sequences
|
|
of individual single-line strings ending with newlines (such sequences
|
| can also be obtained from the \method{readlines()} method of file-like
|
|
can also be obtained from the \method{readlines()} method of file-like
|
| objects):
|
|
objects):
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> text1 = ''' 1. Beautiful is better than ugly.
|
|
>>> text1 = ''' 1. Beautiful is better than ugly.
|
| ... 2. Explicit is better than implicit.
|
|
... 2. Explicit is better than implicit.
|
| ... 3. Simple is better than complex.
|
|
... 3. Simple is better than complex.
|
| ... 4. Complex is better than complicated.
|
|
... 4. Complex is better than complicated.
|
| ... '''.splitlines(1)
|
|
... '''.splitlines(1)
|
| >>> len(text1)
|
|
>>> len(text1)
|
| 4
|
|
4
|
| >>> text1[0][-1]
|
|
>>> text1[0][-1]
|
| '\n'
|
|
'\n'
|
| >>> text2 = ''' 1. Beautiful is better than ugly.
|
|
>>> text2 = ''' 1. Beautiful is better than ugly.
|
| ... 3. Simple is better than complex.
|
|
... 3. Simple is better than complex.
|
| ... 4. Complicated is better than complex.
|
|
... 4. Complicated is better than complex.
|
| ... 5. Flat is better than nested.
|
|
... 5. Flat is better than nested.
|
| ... '''.splitlines(1)
|
|
... '''.splitlines(1)
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| Next we instantiate a Differ object:
|
|
Next we instantiate a Differ object:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> d = Differ()
|
|
>>> d = Differ()
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| Note that when instantiating a \class{Differ} object we may pass
|
|
Note that when instantiating a \class{Differ} object we may pass
|
| functions to filter out line and character ``junk.'' See the
|
|
functions to filter out line and character ``junk.'' See the
|
| \method{Differ()} constructor for details.
|
|
\method{Differ()} constructor for details.
|
|
|
|
|
| Finally, we compare the two:
|
|
Finally, we compare the two:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> result = list(d.compare(text1, text2))
|
|
>>> result = list(d.compare(text1, text2))
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| \code{result} is a list of strings, so let's pretty-print it:
|
|
\code{result} is a list of strings, so let's pretty-print it:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> from pprint import pprint
|
|
>>> from pprint import pprint
|
| >>> pprint(result)
|
|
>>> pprint(result)
|
| [' 1. Beautiful is better than ugly.\n',
|
|
[' 1. Beautiful is better than ugly.\n',
|
| '- 2. Explicit is better than implicit.\n',
|
|
'- 2. Explicit is better than implicit.\n',
|
| '- 3. Simple is better than complex.\n',
|
|
'- 3. Simple is better than complex.\n',
|
| '+ 3. Simple is better than complex.\n',
|
|
'+ 3. Simple is better than complex.\n',
|
| '? ++ \n',
|
|
'? ++ \n',
|
| '- 4. Complex is better than complicated.\n',
|
|
'- 4. Complex is better than complicated.\n',
|
| '? ^ ---- ^ \n',
|
|
'? ^ ---- ^ \n',
|
| '+ 4. Complicated is better than complex.\n',
|
|
'+ 4. Complicated is better than complex.\n',
|
| '? ++++ ^ ^ \n',
|
|
'? ++++ ^ ^ \n',
|
| '+ 5. Flat is better than nested.\n']
|
|
'+ 5. Flat is better than nested.\n']
|
| \end{verbatim}
|
|
\end{verbatim}
|
|
|
|
|
| As a single multi-line string it looks like this:
|
|
As a single multi-line string it looks like this:
|
|
|
|
|
| \begin{verbatim}
|
|
\begin{verbatim}
|
| >>> import sys
|
|
>>> import sys
|
| >>> sys.stdout.writelines(result)
|
|
>>> sys.stdout.writelines(result)
|
| 1. Beautiful is better than ugly.
|
|
1. Beautiful is better than ugly.
|
| - 2. Explicit is better than implicit.
|
|
- 2. Explicit is better than implicit.
|
| - 3. Simple is better than complex.
|
|
- 3. Simple is better than complex.
|
| + 3. Simple is better than complex.
|
|
+ 3. Simple is better than complex.
|
| ? ++
|
|
? ++
|
| - 4. Complex is better than complicated.
|
|
- 4. Complex is better than complicated.
|
| ? ^ ---- ^
|
|
? ^ ---- ^
|
| + 4. Complicated is better than complex.
|
|
+ 4. Complicated is better than complex.
|
| ? ++++ ^ ^
|
|
? ++++ ^ ^
|
| + 5. Flat is better than nested.
|
|
+ 5. Flat is better than nested.
|
| \end{verbatim}
|
|
\end{verbatim}
|