Closed Bug 1043171 Opened 5 years ago Closed 5 years ago
Editing events last selectable category in listbox is shown twice
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.
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?
Assignee: nobody → bv1578
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Attachment #8461462 - Flags: review?(philipp)
@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 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.
Attachment #8461462 - Flags: review?(philipp) → review+
(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.
(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!).
Pushed to comm-central <http://hg.mozilla.org/comm-central/rev/67470d6e08f9>
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.7
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
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
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
The duplicate element is added by insertCategory() , which uses the index provided by binaryInsert()  and hence by binarySearch() . 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.
Sorry, I didn't add the links to the functions: insertCategory()  http://mxr.mozilla.org/comm-central/source/calendar/base/content/widgets/calendar-widgets.xml#119 binaryInsert()  http://mxr.mozilla.org/comm-central/source/calendar/base/src/calUtils.js#1815 binarySearch()  http://mxr.mozilla.org/comm-central/source/calendar/base/src/calUtils.js#1739
(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?
Attachment #8519528 - Flags: review?(philipp)
Attachment #8519528 - Flags: review?(philipp) → review+
Status: REOPENED → RESOLVED
Closed: 5 years ago → 5 years ago
Resolution: --- → FIXED
Target Milestone: 3.8 → 3.7
You need to log in before you can comment on or make changes to this bug.