--- a/mercurial/commands.py	Fri Aug 11 14:50:41 2006 -0700
+++ b/mercurial/commands.py	Sat Aug 12 13:51:14 2006 -0700
@@ -10,7 +10,7 @@
 from i18n import gettext as _
 demandload(globals(), "os re sys signal shutil imp urllib pdb")
 demandload(globals(), "fancyopts ui hg util lock revlog templater bundlerepo")
-demandload(globals(), "fnmatch mdiff random signal tempfile time")
+demandload(globals(), "fnmatch mdiff difflib random signal tempfile time")
 demandload(globals(), "traceback errno socket version struct atexit sets bz2")
 demandload(globals(), "archival cStringIO changegroup email.Parser")
 demandload(globals(), "hgweb.server sshserver")
@@ -1644,42 +1644,55 @@
             self.linenum = linenum
             self.colstart = colstart
             self.colend = colend
+
         def __eq__(self, other):
             return self.line == other.line
-        def __hash__(self):
-            return hash(self.line)
 
     matches = {}
     def grepbody(fn, rev, body):
-        matches[rev].setdefault(fn, {})
+        matches[rev].setdefault(fn, [])
         m = matches[rev][fn]
         for lnum, cstart, cend, line in matchlines(body):
             s = linestate(line, lnum, cstart, cend)
-            m[s] = s
-
-    # FIXME: prev isn't used, why ?
+            m.append(s)
+
+    def difflinestates(a, b):
+        sm = difflib.SequenceMatcher(None, a, b)
+        for tag, alo, ahi, blo, bhi in sm.get_opcodes():
+            if tag == 'insert':
+                for i in range(blo, bhi):
+                    yield ('+', b[i])
+            elif tag == 'delete':
+                for i in range(alo, ahi):
+                    yield ('-', a[i])
+            elif tag == 'replace':
+                for i in range(alo, ahi):
+                    yield ('-', a[i])
+                for i in range(blo, bhi):
+                    yield ('+', b[i])
+
     prev = {}
     ucache = {}
     def display(fn, rev, states, prevstates):
-        diff = list(sets.Set(states).symmetric_difference(sets.Set(prevstates)))
-        diff.sort(lambda x, y: cmp(x.linenum, y.linenum))
         counts = {'-': 0, '+': 0}
         filerevmatches = {}
-        for l in diff:
+        if incrementing or not opts['all']:
+            a, b = prevstates, states
+        else:
+            a, b = states, prevstates
+        for change, l in difflinestates(a, b):
             if incrementing or not opts['all']:
-                change = ((l in prevstates) and '-') or '+'
                 r = rev
             else:
-                change = ((l in states) and '-') or '+'
                 r = prev[fn]
-            cols = [fn, str(rev)]
+            cols = [fn, str(r)]
             if opts['line_number']:
                 cols.append(str(l.linenum))
             if opts['all']:
                 cols.append(change)
             if opts['user']:
-                cols.append(trimuser(ui, getchange(rev)[1], rev,
-                                                  ucache))
+                cols.append(trimuser(ui, getchange(r)[1], rev,
+                                     ucache))
             if opts['files_with_matches']:
                 c = (fn, rev)
                 if c in filerevmatches:

--- a/tests/test-grep	Fri Aug 11 14:50:41 2006 -0700
+++ b/tests/test-grep	Sat Aug 12 13:51:14 2006 -0700
@@ -18,6 +18,5 @@
 mv port1 port
 hg commit -m 4 -u spam -d '4 0'
 hg grep port port
-echo 'FIXME: history is wrong here'
 hg grep --all -nu port port
 hg grep import port

--- a/tests/test-grep.out	Fri Aug 11 14:50:41 2006 -0700
+++ b/tests/test-grep.out	Sat Aug 12 13:51:14 2006 -0700
@@ -1,10 +1,13 @@
 port:4:export
 port:4:vaportight
 port:4:import/export
-FIXME: history is wrong here
-port:1:1:-:eggs:import
-port:1:2:+:eggs:vaportight
-port:1:3:+:eggs:import/export
-port:0:2:+:spam:export
-port:0:1:+:spam:import
+port:4:4:-:spam:import/export
+port:3:4:+:eggs:import/export
+port:2:1:-:spam:import
+port:2:2:-:spam:export
+port:2:1:+:spam:export
+port:2:2:+:spam:vaportight
+port:2:3:+:spam:import/export
+port:1:2:+:eggs:export
+port:0:1:+:eggs:import
 port:4:import/export