ELIST_ITERATOR::add_after_then_move:Error:Attemting to add an element with non NULL links, to a list

[GoogleCodeExporter]

What steps will reproduce the problem?

1. Run "tesseract 000000.tif tmp".

What is the expected output? What do you see instead?

Tesseract crashes with segmentation fault:

Tesseract Open Source OCR Engine v3.01 with Leptonica
Page 0
ELIST_ITERATOR::add_after_then_move:Error:Attemting to add an element with non 
NULL links, to a list
Segmentation fault

What version of the product are you using? On what operating system?

Subversion snapshot r624. Linux, i386.

Please provide any additional information below.

gdb backtrace:

#0  ERRCODE::error (this=0xf7f693f4, caller=0xf7f4dc34 
"ELIST_ITERATOR::add_after_then_move", action=2 '\002', format=0x0) at 
errcode.cpp:99
#1  0xf7ecb23d in add_after_then_move (new_element=<optimized out>, 
this=<optimized out>) at ../ccutil/elst.h:349
#2  tesseract::ColPartition::MakeBlock (bleft=..., tright=..., 
block_parts=0xffffab78, used_parts=0xffffbc00) at colpartition.cpp:1401
#3  0xf7f4c17d in tesseract::WorkingPartSet::MakeBlocks (this=0x8a1cda0, 
bleft=..., tright=..., resolution=600, used_parts=0xffffbc00)
    at workingpartset.cpp:122
#4  0xf7f4ca6b in tesseract::WorkingPartSet::ExtractCompletedBlocks 
(this=0x8a1cda0, bleft=..., tright=..., resolution=600, used_parts=0xffffbc00,
    blocks=0xffffb7f8, to_blocks=0xffffb7fc) at workingpartset.cpp:61
#5  0xf7ec40e4 in tesseract::ColPartition::AddToWorkingSet (this=0x87f6520, 
bleft=..., tright=..., resolution=600, used_parts=0xffffbc00,
    working_sets=0xffffb968) at colpartition.cpp:1201
#6  0xf7eb76f8 in tesseract::ColumnFinder::EmptyTempPartList (this=0xffffbb1c, 
temp_list=0xffffb96c, work_set=0xffffb968) at colfind.cpp:1717
#7  0xf7eba5f8 in tesseract::ColumnFinder::TransformToBlocks (this=0xffffbb1c, 
blocks=0xffffbc50, to_blocks=0xffffbce4) at colfind.cpp:1741
#8  0xf7ebd724 in tesseract::ColumnFinder::FindBlocks (this=0xffffbb1c, 
single_column=false, imageheight=3544, block=0x834b1b8, boxa=0x0, pixa=0x0,
    blocks=0xffffbc50, to_blocks=0xffffbce4) at colfind.cpp:348
#9  0xf7f9e504 in tesseract::Tesseract::AutoPageSeg (this=0x809c8d0, 
resolution=600, single_column=false, osd=false, only_osd=false, 
blocks=0x80aa570,
    to_blocks=0xffffbce4, osd_tess=0x0, osr=0xffffbd6c) at pagesegmain.cpp:320
#10 0xf7f9f231 in tesseract::Tesseract::SegmentPage (this=0x809c8d0, 
input_file=0x80aa5f0, blocks=0x80aa570, osd_tess=0x0, osr=0xffffbd6c)
    at pagesegmain.cpp:149
#11 0xf7fd129c in tesseract::TessBaseAPI::FindLines (this=0xffffd694) at 
baseapi.cpp:1418
#12 0xf7fd169d in tesseract::TessBaseAPI::Recognize (this=0xffffd694, 
monitor=0x0) at baseapi.cpp:528
#13 0xf7fd3c1d in tesseract::TessBaseAPI::ProcessPage (this=0xffffd694, 
pix=0x80aa5c0, page_index=0, filename=0xffffd996 "000000.tif", retry_config=0x0,
    timeout_millisec=0, text_out=0xffffd6e4) at baseapi.cpp:737
#14 0xf7fd3eda in tesseract::TessBaseAPI::ProcessPages (this=0xffffd694, 
filename=0xffffd996 "000000.tif", retry_config=0x0, timeout_millisec=0,
    text_out=0xffffd6e4) at baseapi.cpp:653
#15 0x08049109 in main (argc=3, argv=0xffffd7b4) at tesseractmain.cpp:141

Original issue reported on code.google.com by jwilk@jwilk.net on 30 Aug 2011 at 6:19

Attachments:

• 000000.tif

[GoogleCodeExporter]

I got the same issue on the attached file; MacOS X 10.7 running with dev 
snapshot r267.  Commenting out the STILL_LINKED check in elst.h 
(ELIST_ITERATOR::add_after_then_move) lets it work.  This will therefore not 
show up on platforms which define NDEBUG (which eliminates these checks).  
colpartition.cpp seems like it is taking nodes from a CLIST_ITERATOR (which 
does not null out next/prev links since it does not know about them) and 
inserting using an ELIST_ITERATOR, but apparently the node was part of some 
list earlier having its next link set, and either not properly taken out, or 
still existing in it.

Original comment by clindb...@gmail.com on 12 Oct 2011 at 3:35

Attachments:

• bug_p31.tif

[GoogleCodeExporter]

A bit of a "me too" adding another test case.  I cropped out the minimal part 
of the image which would reproduce the problem.

Original comment by matthew....@gmail.com on 16 Dec 2011 at 5:23

Attachments:

• crop.tif

[GoogleCodeExporter]

Thanks to the previous commenter I've been able to track this issue to its root 
cause.  A ColPartition is being created which references the same BLOBNBOX 
twice.  When that gets processed inside MakeBlock, it asserts when it tries to 
add it a second time.  

The problem is the way the boxes get added in different places in 
colpartition.cpp.  Initially they get added with AddBox, which adds sorted and 
unique using:

    if (IsVerticalType())
      boxes_.add_sorted(SortByBoxBottom<BLOBNBOX>, true, bbox2);
    else
      boxes_.add_sorted(SortByBoxLeft<BLOBNBOX>, true, bbox2);

Later, they can be added using Absorb(), which only sorts based on 
bounding_box().left().  That's less strict than the sort operator, and totally 
wrong for vertical types.  Later again, Unique() adds more boxes using 
AddBox().  At this point, boxes added in the wrong order inside Absorb() mean 
the list is out of order, which can cause the same box to be added twice.

This could be fixed by removing the iterator "it" from the block which says 
"Merge the two sorted lists", and adding bbox2 using the same add_sorted() code 
as AddBox().  However, further down it seems that it can change the blob type, 
which might break sorting.  It may be safest just to force a re-sort at the end 
of Absorb(), although I'm not sure how efficient that is as it requires a 
memory allocation.

Original comment by matthew....@gmail.com on 19 Dec 2011 at 5:28

[GoogleCodeExporter]

This appears to be fixed in the latest SVN, as the bit of code I mentioned 
above is no longer there.  I can't be absolutely sure it's fixed because too 
much has changed.. but it no longer crashes on the attached images.

Original comment by matthew....@gmail.com on 13 Apr 2012 at 8:18

[GoogleCodeExporter]

Original comment by zde...@gmail.com on 13 Apr 2012 at 10:18

• Changed state: Fixed