Issue 144: mtn diff infinite loop - A distributed version control system

Reported by joe 23, Feb 8, 2011

The internal diff is apparently buggy. On a pathological (but real 
life) text file, mtn diff never returns. mtn diff --external works 
fine. This seems to have broken somewhere between 0.44 and 0.48. I 
have reports of this working for some people and not others, so it 
may depend on platform or libraries, but I haven't been able to 
isolate it further.


Steps to reproduce the problem:
-------------------------------

1. gunzip v1.txt.gz
2. gunzip v2.txt.gz
3. mtn add v1.txt
4. mtn ci v1.txt
5. cp v2.txt v1.txt
6  mtn diff v1.txt

Expected result:
----------------
completion

Actual results:
---------------
100% CPU forever

Output of `mtn version --full`:
-------------------------------
monotone 0.99.1 (base revision: 
8973482283db7c36780dce2b54721ccc0f5b7388)
Running on          : Linux 2.6.35-24-generic #42-Ubuntu SMP Thu Dec 
2 01:41:57 UTC 2010 i686
C++ compiler        : GNU C++ version 4.3.2
C++ standard library: GNU libstdc++ version 20080905
Boost version       : 1_40
SQLite version      : 3.5.9 (compiled against 3.5.9)
Lua version         : Lua 5.1
PCRE version        : 7.6 2008-01-28 (compiled against 7.6)
Botan version       : 1.8.9 (compiled against 1.8.9)
Changes since base revision:
format_version "1"

new_manifest [c1270158b7fa91abf8235ad129b0476943bde1ed]

old_revision [8973482283db7c36780dce2b54721ccc0f5b7388]

  Generated from data cached in the distribution;
  further changes may have been made.

v1.txt.gz - 696.80 kB
v2.txt.gz - 684.96 kB

Comment 1 by joe 23, Feb 8, 2011

Correction (to the between 0.44 and 0.48 statement), also seen on 
0.38:

monotone 0.38 (base revision: 
c1757f6cde49bddd77c82580059105bc470145b2)
Running on          : Linux 2.6.28.7 #1 Sat Feb 28 11:17:44 UTC 2009 
i686
C++ compiler        : GNU C++ version 3.4.2 20041017 (Red Hat 
3.4.2-6.fc3)
C++ standard library: GNU libstdc++ version 20041017
Boost version       : 1_34_1
Changes since base revision:
format_version "1"

new_manifest [085f4d04a0bbbc06b44cf6194ca9c2079f924cdd]

old_revision [c1757f6cde49bddd77c82580059105bc470145b2]

  Generated from data cached in the distribution;
  further changes may have been made.

Comment 2 by Thomas Keller, Feb 8, 2011

Confirmed, git 1.7.1 gets it right btw.

It hangs somewhere in lcs.cc (jaffer_edit_calculator::compare).

Status: Accepted

Comment 3 by Thomas Keller, Feb 10, 2011

Tim pointed me on IRC that it doesn't actually hang, but just takes 
an awful lot of time to complete (roughly 9 seconds for me here on 
an old P4 with HT, Tim timed 10 seconds). Meh, I expect that things 
always run blazingly fast these days :)

We'll try to spot the issue.

Comment 4 by joe 23, Feb 11, 2011

Sorry for claiming 'forever'. I retried the test case above on an 
Atom processor and it took about 45 seconds. I have another test 
case that took 5 minutes (that test case with --external is 2.5 
seconds). If you want those test case files also, please let me 
know. I could swear I had a test case that actually was forever, but 
I can't find it at the moment. Maybe it was on older hardware and it 
only seemed like forever. I'll keep looking. Thanks for 
investigating on your side.

Comment 5 by Thomas Keller, Feb 21, 2011

I'd like to see this fixed for 1.0

Labels: Milestone:1.0

Comment 6 by Thomas Keller, Mar 13, 2011

@Tim: I added you as owner for this issue, because you already 
started on this and improved the timings quite a lot. If you have no 
time to look into this more, I'd close this ticket for now for the 
upcoming release, what do you say?

Status: Started
Owner: tbrownaw