[SOLVED]MultiColumnList crash - Adding row while sorting

[Tiblanc]

Hi all!

I'm using CEGUI 0.7 with Ogre. I'm not sure if this is a bug in my code or in CEGUI as I lack experience with the library. I have a MultiColumnList that I update every once in a while with object's info. Objects are added periodically to the list. If I sort the list, the next object to be added does not appear in the list and the one after that causes the crash. If I do not sort the list, everything is fine. The error is "Expression : sequence not ordered". Also, if I try to reorder the list after the object that does not appear, it still doesn't appear. Just in case it doesn't make any sense, here's a play-by-play :

1. Let objects A and B be added into the list
2. Sort the list
3. Object C is added to the list but does not appear
4. Reordering the list here does not make C appear
5. Object D is added to the list and it crashes

This is the stack trace :

Code: Select all

>   CEGUIBase_d.dll!std::_Debug_order_single2<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > >(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04fef110 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04fef520 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=0 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[349230288](...,...) d_sortColumn=0 d_rowID=983049 }, bool __formal=true, const wchar_t * _File=0x00eea018, unsigned int _Line=2325, bool __formal=true)  Line 1671 + 0x15 bytes   C++
    CEGUIBase_d.dll!std::_Debug_order_single<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > >(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04fef110 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04fef520 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=0 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[349230288](...,...) d_sortColumn=0 d_rowID=983049 }, bool _IsFirstIteration=true, const wchar_t * _File=0x00eea018, unsigned int _Line=2325)  Line 1679 + 0x75 bytes   C++
    CEGUIBase_d.dll!std::_Upper_bound<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> >,CEGUI::MultiColumnList::ListRow,int>(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04fef110 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04fef520 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=0 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[349230288](...,...) d_sortColumn=0 d_rowID=983049 }, const CEGUI::MultiColumnList::ListRow & _Val={...}, int * __formal=0x00000000)  Line 2325 + 0x59 bytes   C++
    CEGUIBase_d.dll!std::upper_bound<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> >,CEGUI::MultiColumnList::ListRow>(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04fef110 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04fef520 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=0 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[349230288](...,...) d_sortColumn=0 d_rowID=983049 }, const CEGUI::MultiColumnList::ListRow & _Val={...})  Line 2347 + 0x8f bytes   C++
    CEGUIBase_d.dll!CEGUI::MultiColumnList::addRow(CEGUI::ListboxItem * item=0x00000000, unsigned int col_id=0, unsigned int row_id=0)  Line 830 + 0x61 bytes   C++
    CEGUIBase_d.dll!CEGUI::MultiColumnList::insertRow(CEGUI::ListboxItem * item=0x00000000, unsigned int col_id=0, unsigned int row_idx=0, unsigned int row_id=6)  Line 868 + 0x12 bytes   C++
    CEGUIBase_d.dll!CEGUI::MultiColumnList::insertRow(unsigned int row_idx=0, unsigned int row_id=6)  Line 857   C++
    ThisGame.exe!GUISquad::update()  Line 60 + 0x1d bytes   C++


And this is the bit of code that creates a new entry in the list. It crashes at the insertRow line.

Code: Select all

                // Create a new row
                unsigned int lRow = lList->insertRow(0, lShip->getId());
                CEGUI::ListboxTextItem* lItem = new CEGUI::ListboxTextItem(CEGUI::PropertyHelper::intToString(lShip->getId()), lShip->getId());
                lList->setItem(lItem, 0, lRow);
               
                lItem = new CEGUI::ListboxTextItem(CEGUI::PropertyHelper::intToString(lShip->getId()), lShip->getId());
                lList->setItem(lItem, 1, lRow);


Let me know if you need more info. Thanks!

[CrazyEddie]

Hi,

From briefly reading the description, it sounds like a bug to me. I'll test it to confirm (or not) later and get back to you. Thanks for the report.

CE.

[CrazyEddie]

Ok, I have tested a little, but failed to get a crash; though this was not on MSVC and the level of debug checks is probably different. However, I do believe I understand the issue - that is basically, that the "sorted" list is somehow becoming "unsorted" and so causing upperbound to freak out. The way this is probably happening is due to changes in item content after the initial insertion of items, so basically anywhere you modify item data or set items into existing rows, you need to call MultiColumnList::handleUpdatedItemData - so there should be a call to that at least at the end of the code that inserts new rows (and also anywhere else you might be modifying data. Let us know if this helps or not, and if not, I'll test it on MSVC so I get the same debug checks

Btw, the reason the handleUpdatedItemData call is not automatic is to allow user code to update potentially large batches of items, and have just a single update call - otherwise in certain cases it might become prohibitively expensive to update large lists with lots of data.

Your backtrace did however alert me to another bug where we're not correctly passing on a row_id value internally - so thanks for that I'll fix this little bug, though I don't think it's causing your issue

CE.

[Tiblanc]

Sadly, I was already calling handleUpdatedItemData at the end of my updates.

My algorithm for updating this list is:
- For every object, check if its id is in the list. If it is not, then create a row entry with the code listed above
- For every item in the list, check if the corresponding object exists. If it doesn't, delete the row with:

Code: Select all

lList->removeRow(lList->getRowID(i));

where "i" comes from the loop definition:

Code: Select all

for (unsigned int i=0; i < lList->getRowCount(); ++i) {

If it exists, update the contents with:

Code: Select all

                    // Update the row's data
                    CEGUI::uint lRowId = lList->getRowWithID(lShip->getId());
                    CEGUI::uint lCol1 = lList->getColumnWithID(0);
                    CEGUI::uint lCol2 = lList->getColumnWithID(1);
                   
                    lList->getItemAtGridReference(CEGUI::MCLGridRef(lRowId, lCol1))->setText(CEGUI::PropertyHelper::intToString(lShip->getId()));
                    lList->getItemAtGridReference(CEGUI::MCLGridRef(lRowId, lCol2))->setText(CEGUI::PropertyHelper::intToString(lShip->getId()));


- Call handleUpdatedItemData()

This is done every 60 frames for performance reasons. I'm wondering if this delay could play any role in this issue, or maybe it's because I do not use the library properly?

Thanks for looking into this!

[CrazyEddie]

Ah, ok.

An interesting point is that you're accessing rows by ID - this means that you almost certainly could have been affected by the small bug I mentioned earlier - not saying it's the cause of this issue - but I'm surprised that perhaps you did not get the 'wrong' rows being updated or not being updated at all.

Thanks for the additional info - I'll run some more tests

CE.

[CrazyEddie]

I have confirmed this as a bug, and it's now fixed in the v0-7.

The issue was that we did not correctly consider the sort direction when deciding the insertion point for a new when the list was sorted ascending. This bug has been in there for a long time, I'm surprised it's not come up earlier!

CE.

[Tiblanc]

I tested it and it works perfectly!

Thanks!

[Tiblanc]

I've managed to make it crash once again with revision 2321. This time, it seems to be related to the deletion of rows when they are ordered. The items are deleted this way

Code: Select all

        for (unsigned int i=0; i < lList->getRowCount(); ++i) {
            bool lExist = false;

            if (!lExist) {
                // Delete the row
                lList->removeRow(i);
                --i;
            }
        }


There is some code that checks if the item still exists in the game that I removed. Since I switch the displayed object, none of the rows are valid anymore and they all get deleted. When I switch back to the original object, it will crash.

Play by play:
1. Create 3 items in the list
2. Order the list (this can also be done before step 1)
3. Switch to some other object with 0 item, list gets cleaned
4. Switch back to object with 3 items, crash on 3rd insert

This will only crash when there are 3 or more items in the list. It crashes with a "sequence not ordered" error again.

[CrazyEddie]

After deleting the items, and before adding new items, do you call handleUpdatedItemData? We don't do this internally for performance reasons (in case, as in your example code, user code sits in a loop of some kind removing multiple items).

CE.

[Tiblanc]

Yes. handleUpdatedItemData is called at the end of the function. Pseudo-code is something like this :

- For every object, add it if it is not in the list, update it if it is
- For every list item, remove it if it is no longer valid
- Call handleUpdatedItemData

Code to add items is in the first post. I tried calling handleUpdatedItemData between inserts and deletes and it still crashes.

Here's the stack trace in case it may help

Code: Select all

>   CEGUIBase_d.dll!std::_Debug_order_single2<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > >(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04d09c50 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04d0a028 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=5 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[0]() d_sortColumn=0 d_rowID=6 }, bool __formal=true, const wchar_t * _File=0x00fe39d8, unsigned int _Line=2325, bool __formal=true)  Line 1671 + 0x15 bytes   C++
    CEGUIBase_d.dll!std::_Debug_order_single<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > >(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04d09c50 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04d0a028 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=5 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[0]() d_sortColumn=0 d_rowID=6 }, bool _IsFirstIteration=true, const wchar_t * _File=0x00fe39d8, unsigned int _Line=2325)  Line 1679 + 0x75 bytes   C++
    CEGUIBase_d.dll!std::_Upper_bound<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> >,CEGUI::MultiColumnList::ListRow,int>(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04d09c50 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04d0a028 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=5 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[0]() d_sortColumn=0 d_rowID=6 }, const CEGUI::MultiColumnList::ListRow & _Val={...}, int * __formal=0x00000000)  Line 2325 + 0x59 bytes   C++
    CEGUIBase_d.dll!std::upper_bound<std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> >,CEGUI::MultiColumnList::ListRow>(std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _First={d_items=[2](0x04d09c50 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...},0x04d0a028 {d_textCols={...} d_font=0x00000000 d_renderedString={...} ...}) d_sortColumn=0 d_rowID=5 }, std::_Vector_iterator<CEGUI::MultiColumnList::ListRow,std::allocator<CEGUI::MultiColumnList::ListRow> > _Last={d_items=[0]() d_sortColumn=0 d_rowID=6 }, const CEGUI::MultiColumnList::ListRow & _Val={...})  Line 2347 + 0x8f bytes   C++
    CEGUIBase_d.dll!CEGUI::MultiColumnList::addRow(CEGUI::ListboxItem * item=0x00000000, unsigned int col_id=0, unsigned int row_id=6)  Line 833 + 0x6e bytes   C++
    CEGUIBase_d.dll!CEGUI::MultiColumnList::insertRow(CEGUI::ListboxItem * item=0x00000000, unsigned int col_id=0, unsigned int row_idx=0, unsigned int row_id=6)  Line 871 + 0x14 bytes   C++
    CEGUIBase_d.dll!CEGUI::MultiColumnList::insertRow(unsigned int row_idx=0, unsigned int row_id=6)  Line 860   C++
    ThisGame.exe!GUISquad::update()  Line 64 + 0x1d bytes   C++


I'm using VC++ 2008 Express.

[CrazyEddie]

Thanks for the info.

I've tested this a bit and the only time I could reproduce the issue was if I missed the handleUpdatedItemData call (in this case after setting the two items into the newly added row)

CE.

[Tiblanc]

Do you mean that you call handleUpdatedItemData after every insert? I'm calling it after my batch of 3 inserts. When I call it after every insert, it doesn't crash and works fine, but I guess that defeats the whole point.

I'm trying to decipher the code right now and I think I see what's causing it to crash. First the < operator for ListRow :

Code: Select all

bool MultiColumnList::ListRow::operator<(const ListRow& rhs) const
{
   ListboxItem* a = d_items[d_sortColumn];
   ListboxItem* b = rhs.d_items[d_sortColumn];

   // handle cases with empty slots
   if (!b)
   {
      return false;
   }
   else if (!a)
   {
      return true;
   }
   else
   {
      return *a < *b;
   }

}


Since I'm creating my rows with

Code: Select all

insertRow(0, lShip->getId());

b is always null because no columns have been created yet. in addRow, this bit of code is called:

Code: Select all

        ListItemGrid::iterator ins_pos = dir == ListHeaderSegment::Descending ?
            std::upper_bound(d_grid.begin(), d_grid.end(), row) :
            std::upper_bound(d_grid.begin(), d_grid.end(), row, pred_descend);
        // insert item and get final inserted position.
        ListItemGrid::iterator final_pos = d_grid.insert(ins_pos, row);


Since operator< always returns false, upper_bound returns an iterator to the first element. Since the values are ascending when I add them, this happens in the vector :
1. vector : empty
2. add 1, vector : 1
3. add 2, vector : 2, 1
4. add 3, crash

From the site here about upper_bound : http://www.cplusplus.com/reference/algo ... per_bound/

For the function to yield the expected result, the elements in the range shall already be ordered according to the same criterion (operator< or comp).

Since the vector is not ordered anymore, it figures out something is wrong with the iterators and proclaims holy unsorted array Batman! If I add resortList() before the call to upper_bound, it doesn't crash anymore. That's a very crude fix though and only demonstrate this is what is going on.

With this in mind, I believe this may also occur if a column is sorted and a row gets updated with a value that would put it out of order. Many rows can be updated without a crash, but if you try to add a row before calling handleUpdatedItemData, it will fail. Also, I did not check it out in details, but the same problem may exist in a sorted Listbox. Update the text of an element to put it out of order and when you try to add a new item, it crashes.

[CrazyEddie]

Do you mean that you call handleUpdatedItemData after every insert? I'm calling it after my batch of 3 inserts. When I call it after every insert, it doesn't crash and works fine, but I guess that defeats the whole point.

No, not after every insertion into the list (i.e calls to addRow / insertRow), these calls ensure the row is added or inserted at the appropriate position, thus maintaining the sort. The issue here is not the insertion as such, it's the fact that the row content is modified after insertion; it is this change that causes the previously ordered content to be unordered and this is why you'd have to call the handleUpdatedItemData function (because by setting items into the row you have updated the item data)...

Code: Select all

// Create a new row
//
// [1] After the following call the list is still sorted.  You could call this a million times and the list would remain correctly sorted.
unsigned int lRow = lList->insertRow(0, lShip->getId());

// [2] After the following operation, the list may or may not be sorted, since you are changing the content of an existing row.
// This means that after this call, before performing any other add/remove/find type call, the list needs to be resorted via a
// call to handleUpdatedItemData.
CEGUI::ListboxTextItem* lItem = new CEGUI::ListboxTextItem(CEGUI::PropertyHelper::intToString(lShip->getId()), lShip->getId());
lList->setItem(lItem, 0, lRow);
               
// [3] Again, after the following operation, the list may or may not be sorted, since you are changing the content of an existing row.
// This means that after this call, before performing any other add/remove/find type call, the list needs to be resorted via a
// call to handleUpdatedItemData.
lItem = new CEGUI::ListboxTextItem(CEGUI::PropertyHelper::intToString(lShip->getId()), lShip->getId());
lList->setItem(lItem, 1, lRow);

Ok. As we can see in the above. [1] maintains the list ordering - the fact the row is empty is neither here nor there, the fact is the row is created at an appropriate place given the information it has at the time.

In [2] and [3] we are modifying the content of rows already in the list. Because we might want to update thousands of items, we do not maintain ordering during these types of operation; rather, we allow as many item modification calls to be made as necessary, though once all updates are made the user must call handleUpdatedItemData in order for the list to 're-sync' it's state with regards to the modified items and item data.

Right. Some important notes. When we refer to 'item modification calls' this means calls that modify the items in existing cells of the grid. This can mean removing items (that's items - not rows or columns), setting new items (again, items - not rows or columns), or modifying the content and state of existing items. It is these types of calls that can be batched to minimise calls (to handleUpdatedItemData) that resort the list. Once you come to other operations on the list; adding rows or columns, removing rows or columns, searching the list content and so on and so forth, then the list needs to be in a consistent state and is the purpose of the handleUpdatedItemData function.

The fact that in this specific example a row insert is directly followed by two item modifying calls means that after those calls you will need to resync things. There are other alternatives, you could create the items up front, and include the appropriate item (the one that will go in the sort column) in the call to insertRow, this way the list ordering will be maintained - you may then set the other column(s) freely (without calling handleUpdatedItemData), since you know that the column that could invalidate the list ordering has been dealt with.

HTH

CE.

[Tiblanc]

I wasn't sure if this was the library's responsibility or the user's responsibility to keep the list ordered. I'll try your suggestion of creating items up front. That should fix my problems.

Thanks!

[CrazyEddie]

Well, it's a bit of both CEGUI does it's bit in that it will insert or add rows in the correct place, though the user has to also do their bit to ensure that the ordering is updated if they change the content of the list cells.

CE.