1043171 - Editing events last selectable category in listbox is shown twice

Status: RESOLVED FIXED

(Calendar :: Dialogs, defect)

Description

[Rudolf Kollien]

Attachment: Screenshot editing category of existing event

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:31.0) Gecko/20100101 Firefox/31.0 (Beta/Release)
Build ID: 20140716183446

Steps to reproduce:

- Update Lightning to 3.3 with TB 31 from TB24.
- Edit an existing event with an assigned category and open category select box. 

Before L3.3/TB31 all where correct. Error appeared with 3.3.


Actual results:

- If the event has a category which is in sort order above the last entry, all is shown correct.
- If the event has a category which is last in sort order, the category is displayed twice.
F.e.:
Available categories:
A, B, C
If event has category A or B assigned, editing the event and category, the listbox with the categories is correct.
If event has category C assigned, editing the event and category, the listbox shows C twice.
This doesn't happen, when new events are created. Than the category listbox is correct.


Expected results:

Editing events with categories last in sort order should show the category in the listbox only once.

Comment 1

[Rudolf Kollien]

Attachment: Screenshot creating new event selecting category

Comment 2

[Decathlon]

Attachment: patch-v1

Confirmed.

It seems there is an issue in the function binarySearch because it doesn't find the last element in the array.

@ Rudolf Kollien
The screenshot you attached shows an evident issue about icons in the dialog may I ask you what operative system are you using and if you are using themes or others addons?

Comment 3

[Rudolf Kollien]

@Decathlon
Yes, this is the MS Office JB 2003 Edition v3.31.0 theme for TB on OSX 10.9. The theme lacks some correct icons on some places.
There are some addons along with lightning installed:
Adblock Edge
LookOut
NestedQuote Remover
Printing Tools
QuickFolders
Theme Font & Size Changer
ThunderBirthDay

Comment 4

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Comment on attachment 8461462 [details] [diff] [review]
patch-v1

Review of attachment 8461462 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good. Maybe you can add a unit test on the binary search/insert functions? This way we could easily migrate them to asm.js some day.

Comment 5

[Decathlon]

(In reply to Rudolf Kollien from comment #3)
> @Decathlon
> Yes, this is the MS Office JB 2003 Edition v3.31.0 theme for TB on OSX 10.9.
> ...

Ok, so it isn't a Lightning's problem ;-).

(In reply to Philipp Kewisch [:Fallen] from comment #4)
> Looks good. Maybe you can add a unit test on the binary search/insert
> functions? This way we could easily migrate them to asm.js some day.

Unfortunately I'm still fighting against tests on both platforms, comm-central and GitHub. Nothing is working as it should, so it's hard to make tests without ... testing the tests.
We can leave this bug open after the checkin so I will try to do a unit test when I will get something working.

Comment 6

[Rudolf Kollien]

(In reply to Decathlon from comment #5)
> Ok, so it isn't a Lightning's problem ;-).

No. But fortunately it doesn't cause the problem. Checked with standard theme.

> Unfortunately I'm still fighting against tests on both platforms,

Let me know, When i can help you testing on Mac OSX (10.9 and 10.10!).

Comment 7

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Pushed to comm-central <http://hg.mozilla.org/comm-central/rev/67470d6e08f9>

Comment 8

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

We actually had a unit test, which was broken itself. I've pushed a bustage fix for the test failures:

https://hg.mozilla.org/comm-central/rev/74a135a7eff4

Comment 9

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

I'm going to have to back this out, I don't feel safe pushing another bustage fix. Before we make further changes to the algorithm we should take a good hard look at what our callers are expecting and if it matches the algorithm.

I believe that binarySearch was supposed to work in a way that if the item is not found, it would return the ideal insert position. We need to double check that this is how the algorithm is actually meant to work because the implementations I found on the net work a bit differently.

There is also a BSD-licensed implementation in devtools, I'd rather stick with MPL code though.
http://mxr.mozilla.org/comm-central/source/mozilla/toolkit/devtools/sourcemap/source-map.js#1482


Backout changeset:

https://hg.mozilla.org/comm-central/rev/a1abfc82c23e

Comment 10

[Decathlon]

The duplicate element is added by insertCategory() [1], which uses the index provided by binaryInsert() [2] and hence by binarySearch() [3]. The index is always correct except when the item to add is the last in the array, because in this case the index is equal to itemArray.length instead of itemArray.length -1.

On a new profile we currently have 22 categories, with index for the array that goes from 0 ("Anniversary") to 21 ("Vacation"), I've checked how the function binarySearch() works when opening the event after previously set the last category ("Vacation") on the event, what happens to the temporary indexes in the function is:

iteration    indexes
-----------------------------------------------------------------
      1      low: 0,  high: 21, mid: 10, itemArray[mid]: Holidays
      2      low: 11, high: 21, mid: 16, itemArray[mid]: Projects
      3      low: 17, high: 21, mid: 19, itemArray[mid]: Suppliers
      4      low: 20, high: 21, mid: 20, itemArray[mid]: Travel
      5      low: 21, high: 21
             -> return from binarySearch() with index = 22 


the fifth iteration (low=high=21) allows the function to return from line 1743 where the comptor is 0 because his arguments are
  newItem: Vacation
  itemArray[low]: Vacation
but with comptor=0 the function adds 1 to the index of the last item and returns with a *wrong* index of 22 instead of 21 and this happens always when the function search for the item with the last index, independently from the array or the comptor (when this returns 0 for elements that are equal).

The bug seems evident to me so I have to admit that I've not verified if binarySearch causes problems in others contexts. I will take a look.

Comment 11

[Decathlon]

Sorry, I didn't add the links to the functions:
insertCategory()
[1] http://mxr.mozilla.org/comm-central/source/calendar/base/content/widgets/calendar-widgets.xml#119
binaryInsert()
[2] http://mxr.mozilla.org/comm-central/source/calendar/base/src/calUtils.js#1815
binarySearch()
[3] http://mxr.mozilla.org/comm-central/source/calendar/base/src/calUtils.js#1739

Comment 12

[Decathlon]

Attachment: patch - v2

(In reply to Philipp Kewisch [:Fallen] from comment #9)
> 
> I believe that binarySearch was supposed to work in a way that if the item
> is not found, it would return the ideal insert position. We need to double
> check that this is how the algorithm is actually meant to work because the
> implementations I found on the net work a bit differently.

binarySearch() works in that way for every element in the array except the last one that, when found, returns the real index incremented by one (see also
http://mxr.mozilla.org/comm-central/source/calendar/test/unit/test_utils.js#181 where the array to test has 11 elements). 


> Before we make further changes to the algorithm we should take
> a good hard look at what our callers are expecting and if it matches the
> algorithm.

As far as I can see binarySearch() is used only inside the functions binaryInsert() and binaryInsertNode():
http://mzl.la/1xtoOzq
and the issue of the last item's index doesn't cause any problem in these functions because when the duplicates must not be discarded, the (wrong) last index is anyway correct (it allows to add the duplicate "on the right" of the last item but for a duplicate it makes no difference), when discarding duplicates instead, the code compares correctly the last element of the array.

Though, these functions also return the index provided by binarySearch() and when the calling function needs to use this index the problem of the last element must be considered. 

Here there are all the request for the functions binaryInsert() and binaryInsertNode():

binaryInsert:    http://mzl.la/1siBMvA
biaryInsertNode: http://mzl.la/1wE62Y9

it seems that only three of them use the index returned by binaryInsert().
Two are related to a function that seems used only in the tests: SortedHashedArray()
http://mxr.mozilla.org/comm-central/source/calendar/base/modules/calHashedArray.jsm#236
http://mxr.mozilla.org/comm-central/source/calendar/base/modules/calHashedArray.jsm#252

the third is exactly the method insertCategory() that affects this bug:
http://mxr.mozilla.org/comm-central/source/calendar/base/content/widgets/calendar-widgets.xml#119

If we don't want to change binarySearch(), we can properly treat that index inside insertCategory(), but I think that at least a comment in the binarySearch() function is necessary.
This patch adds the same check about the last item that is present in the functions binaryInsert() and binaryInsertNode().
What's your opinion?

Comment 13

[Decathlon]

Attachment: patch - v2 for check in

Comment 14

[Patrick Cloke [:clokep]]

https://hg.mozilla.org/comm-central/rev/0e8fa43bc68b