820672 - nsTArray should have a Sort() method that takes a function pointer.

Status: RESOLVED WORKSFORME

(Core :: XPCOM, enhancement, P5)

Description

[Trevor Saunders (:tbsaunde)]

nsCOMArray has it, and you don't always want to bother with a class just so you can sort an array.

Comment 1

[Sankha Narayan Guria [:sankha]]

Attachment: sort method with function pointer

Comment 2

[Trevor Saunders (:tbsaunde)]

Comment on attachment 691808 [details] [diff] [review]
sort method with function pointer

> #include "nsAlgorithm.h"
> #include "nscore.h"
>+#include "nsVoidArray.h"

please don't include that here.

>+  // A variation on the Sort method that uses a function pointer directly
>+  // to compare the elements
>+  // @param aFunc The comparator function

it would be more useful if this comment described how the function is supposed to behave.

>+  void Sort(nsVoidArrayComparatorFunc aFunc, void* aData) {

define your own typedef that takes pointers to the element type.

Comment 3

[Sankha Narayan Guria [:sankha]]

Attachment: sort method with function pointer

Comment 4

[Trevor Saunders (:tbsaunde)]

Comment on attachment 692577 [details] [diff] [review]
sort method with function pointer

>+  typedef int (* aComparatorFunc)
>+            (const void* aElement1, const void* aElement2, void* aData);

elem_type* please

>+  // @param aFunc The comparator function

nit, describe how it should behave?

Comment 5

[Sankha Narayan Guria [:sankha]]

Attachment: Addresses the previous comments

Comment 6

[Trevor Saunders (:tbsaunde)]

Comment on attachment 692905 [details] [diff] [review]
Addresses the previous comments

aData) {
>+        NS_QuickSort(Elements(), Length(), sizeof(elem_type),
>+                 aFunc, aData);

I'm  dubius that compiles without a cast, but if it does that's cool.

I'm not a xpcom peer so over to jlebar who is.

Comment 7

[Justin Lebar (not reading bugmail)]

Is this going to be used somewhere?  I'd rather not add a method without using it in a least one place; YAGNI.

Sankha, perhaps you could modify one of the existing calls to Sort() to use this new method, if you can find one where the use of the comparator class is onerous.

Comment 8

[Justin Lebar (not reading bugmail)]

Thanks for writing this patch!

>+  typedef int (* aComparatorFunc)
>+            (const elem_type* aElement1, const elem_type* aElement2, void* aData);

|aFoo| is reserved for argument names.  We don't use |aFoo| for type names.
This should be |ComparatorFunc|.

Please wrap your lines at 80 characters.  When wrapping long lines, we prefer
not to indent an arbitrary amount (as the line beginning with "const elem_type"
is indented).  Instead, we'd prefer something like

>   typedef int (* aComparatorFunc) (const elem_type* aElement1,
>                                    const elem_type* aElement2, void* aData);

so the args line up nicely.

>+  // Sort method that sorts the elements of an array using a function
>+  // pointer passed to it as a parameter

Nit: Period at the end of the sentence, please.

>+  // @param aFunc The comparator function that takes the two elements to compare 
>+  // as first two function parameters followed by an other parameter to be passed 
>+  // to the comparator function

s/an other/another

This still does not explain how the comparator function is supposed to behave.
What we mean is, what is the comparator function supposed to return, and under
what circumstances?

>+  // @param aData Any additional data that needs to be passed on to the 
>+  // comparator function
>+  void Sort(aComparatorFunc aFunc, void* aData) {
>+        NS_QuickSort(Elements(), Length(), sizeof(elem_type),
>+                 aFunc, aData);
>+  }

Again, please line up |aFunc| so it's below the "E" in "Elements()".

> I'm dubious that compiles without a cast, but if it does that's cool.

OOC, what cast where you worried about here?  I'm kind of surprised you can
implicitly cast a ComparatorFunc to an |int (*fn)(const void*, const void*,
void*)|, but if it works, that's fine.

Comment 9

[Trevor Saunders (:tbsaunde)]

(In reply to Justin Lebar [:jlebar] from comment #7)
> Is this going to be used somewhere?  I'd rather not add a method without
> using it in a least one place; YAGNI.
> 
> Sankha, perhaps you could modify one of the existing calls to Sort() to use
> this new method, if you can find one where the use of the comparator class
> is onerous.

I filed this because of the one added in bug 792566, but I think that just used nsQuickSort() directly instead of bothering with a class.

Comment 10

[Sankha Narayan Guria [:sankha]]

Attachment: WIP patch

I have made the suggested changes as well as changed the implementation of bug 792566. But it refuses to compile with that change. I would have asked on IRC, but you were away. Here is the build error I am getting: http://pastebin.mozilla.org/2061328

Please help.

Comment 11

[Justin Lebar (not reading bugmail)]

Comment on attachment 702301 [details] [diff] [review]
WIP patch

> error: no matching function for call to ‘nsTArray<nsCOMPtr<nsIFile>
> >::Sort(int (*&)(const void*, const void*, void*), std::nullptr_t)’

> no known conversion for argument 1 from ‘int (*)(const void*, const void*,
> void*)’ to ‘int (*)(const elem_type*, const elem_type*, void*) {aka int
> (*)(const nsCOMPtr<nsIFile>*, const nsCOMPtr<nsIFile>*, void*)}’

So the problem is that your Sort() function takes a Comparator which takes
|const elem_type*| args, while you're passing a function which takes |const
void*| args.

Comment 12

[Josh Yuan]

Hello there,

My friend and I are interested in helping out.  Is this bug still active?  If so, where/how do we begin?

Thanks.

Comment 13

[Justin Lebar (not reading bugmail)]

I think Sankha is actively working on this bug.  You may want to find another mentored bug.

(If you want tarray stuff, bug 723228 is not being worked on.)

Comment 14

[[e-mail]]

Attachment: What it would look like with nsCOMArray

Note: this patch requires bug 493711.

Comment 15

[Marco Bonardo [:mak] (Away 10-21 August)]

A problem with the comparators as implemented is that with nsTArray<nsRefPtr<Something> >, the comparator functions get "nsRefPtr<Something>* a", that is not really nice, cause then have to (*a)->prop.

Comment 16

[Rahul Gandhi]

Sir i want to take this bug i am well acquainted with the knowledge of c/c++ and would give my best effort to solve this bug.

Comment 17

[Sankha Narayan Guria [:sankha]]

Attachment: Compile errors on 2 different methods

There is some particular problem when I try to adapt this Sort function to the nsFileView class, because it is defined as nsTArray<nsCOMPtr<nsIFile> > like said in comment 15.

I wrote another method for sort that takes elem_type& as the parameters, but it fails to compile. Errors here: http://bit.ly/ZSibb1

Comment 18

[Trevor Saunders (:tbsaunde)]

(In reply to Sankha Narayan Guria from comment #17)
> Created attachment 725233 [details] [diff] [review]
> Compile errors on 2 different methods
> 
> There is some particular problem when I try to adapt this Sort function to
> the nsFileView class, because it is defined as nsTArray<nsCOMPtr<nsIFile> >
> like said in comment 15.
> 
> I wrote another method for sort that takes elem_type& as the parameters, but
> it fails to compile. Errors here: http://bit.ly/ZSibb1

I'm pretty sure those errors came from a slightly different patch than the one you attached, it looks like after those errors you renamed one of the typedefs to ComparatorFuncNext after which the build gets to building nsFileView.cpp for me locally at which point it fails because you haven't changed the type of the functions you has into the sort method.

Comment 19

[Justin Lebar (not reading bugmail)]

Comment on attachment 725233 [details] [diff] [review]
Compile errors on 2 different methods

Looks like Trevor has this one covered.

Comment 20

[Anuj Agarwal [:anujagarwal464]]

Is this bug still active?

Comment 21

[Trevor Saunders (:tbsaunde)]

(In reply to Anuj Agarwal [:anujagarwal464] from comment #20)
> Is this bug still active?

I don't think anything's happend on it in a long time, feel free to work on it if you need it or whatever.

Comment 22

[Trevor Saunders (:tbsaunde)]

Comment on attachment 725233 [details] [diff] [review]
Compile errors on 2 different methods

I think I commented on this on irc or something...

Comment 23

[Dean Zhu]

Hi, I'd like to take up this bug.
I understand we should implement a sorting algorithm to sort arrays, could I be given a description of the problem?

Comment 24

[Trevor Saunders (:tbsaunde)]

(In reply to Dean Zhu from comment #23)
> Hi, I'd like to take up this bug.
> I understand we should implement a sorting algorithm to sort arrays, could I
> be given a description of the problem?

not exactly, there's already code to sort the array.  That's nsTArray::Sort() in xpcom/ds/nsTArray.h.  The task is just to add another overload of that function that at this point should probably accept either a function pointer or a lambda and use that instead of operator < or a comparator object to compare the objects in the array.

Then you should find some places where a comparator is only used in one spot as an argument to Sort() and simplify them with this.

Comment 25

[Dean Zhu]

ok, I might be a little busy these days but I'll try and get my hands on it as soon as possible

Comment 26

[Dean Zhu]

Sorry, for the delay, couldnt get my hands on a computer these days. How should I start?

Comment 27

[Dean Zhu]

I've been trying to read about function pointers etc, and I have a few doubts,
1) After the overload, what sort function should I call?
2) What is Elem_type? I've seen its a typedef for E, but I cant find any documentation about it.
3) What should the comparator function take as parameters, and what should it return? I've seen that the implementation above returns an int instead of a bool, and takes and extra parameter aData.

Thank you very much!

Comment 28

[Dean Zhu]

I'm calling
> typedef int (* CompareFunc) (elem_type* aElem1, elem_type* aElem2);
> void Sort(CompareFunc Comp) { Sort(*Comp); }
And it does compile, but I'm not sure how the Sort function behaves. Could someone provide some insight?


> I've been trying to read about function pointers etc, and I have a few
> doubts,
> 1) After the overload, what sort function should I call?
Is what I've done correct?

> 2) What is Elem_type? I've seen its a typedef for E, but I cant find any
> documentation about it.
I've seen that E is a template for a smart pointer.

> 3) What should the comparator function take as parameters, and what should
> it return? I've seen that the implementation above returns an int instead of
> a bool, and takes and extra parameter aData.
Still not sure about this.

Comment 29

[Srujana Peddinti [:srujana121]]

Hi, I would like to work on this bug. Can anyone assign this to me?

Comment 30

[Srujana Peddinti [:srujana121]]

From the previous code and comments this is what I have understood.

1. The function mustake a function pointer that does the sorting.
2. The elements to be sorted must be of the type elem_type
3. Should internally use NS_QuickSort

Here are my doubts.

1. When NS_QuickSort is doing exactly the same why do we need another function? What are we supposed to do here that NS_QuickSort does not?

2. elem_type seems to be typedef of class E. I could find class E anywhere.

3. Much of the code seems to have moved. I couldnt find nsTArray.h in glue/ . Where are we supposed to code this?

Comment 31

[Nathan Froyd [:froydnj]]

(In reply to Srujana Peddinti from comment #30)

1. When NS_QuickSort is doing exactly the same why do we need another function? What are we supposed to do here that NS_QuickSort does not?

NS_QuickSort requires extracting various bits from nsTArray; it should be more convenient to just ask the array to sort itself, and let the array figure out what needs to be passed to NS_QuickSort.

2. elem_type seems to be typedef of class E. I could find class E anywhere.

https://searchfox.org/mozilla-central/rev/14dc5b7d8a6da1854b2f9f33f1da77a97368cd54/xpcom/ds/nsTArray.h#857

E is one of the template parameters of nsTArray_Impl.

3. Much of the code seems to have moved. I couldnt find nsTArray.h in glue/ . Where are we supposed to code this?

Ideally you should see where nsTArray.h is as a result of answer to question 2. :)

Comment 32

[Srujana Peddinti [:srujana121]]

Yes, I found nsTArray.h but I wasnt sure if this is the file I have to code in because its folder changed.
So as I have understood, I need to code it in nsTArray.h but in ds/ directory using NS_QuickSort.
And write the necessary tests.

I will be right on it. Is there anything else I have to know?

Comment 33

[Srujana Peddinti [:srujana121]]

1. In nsQuickSort.cpp the function NS_QuickSort() is taking void* and (unsigned)int as first 2 parameters. In the file there is no other declaration of NS_QuickSort(). But in nsTArray.h file the functions Elements(), Length() are passed. How come this works? I ve searched ds/ folder. Couldnt find an alternate declaration.

2. Also to the NS_QuickSort() function what is the last argument we pass? In the file nsQuickSort.h it was mentioned that it is extra data to pass to comparison function. But I couldn't understand it. Isnt the first argument ie array of elem_type* enough for comparison function to sort the array?

Comment 34

[Nathan Froyd [:froydnj]]

(In reply to Srujana Peddinti from comment #33)

1. In nsQuickSort.cpp the function NS_QuickSort() is taking void* and (unsigned)int as first 2 parameters. In the file there is no other declaration of NS_QuickSort(). But in nsTArray.h file the functions Elements(), Length() are passed. How come this works? I ve searched ds/ folder. Couldnt find an alternate declaration.

Pointers automatically convert to void*. The result of Length() implicitly converts to unsigned int (and fortunately always fits into unsigned int due to the way nsTArray works).

2. Also to the NS_QuickSort() function what is the last argument we pass? In the file nsQuickSort.h it was mentioned that it is extra data to pass to comparison function. But I couldn't understand it. Isnt the first argument ie array of elem_type* enough for comparison function to sort the array?

Not if the elements require external data to be sorted. Maybe the elements of the array are indices into some other data structure, and you want to sort the indices in a particular order. See e.g. the use of NS_QuickSort in dom/bindings/BindingUtils.cpp.

Comment 35

[Eric Rahm [:erahm]]

I'm pretty sure we already have a sort function in nsTArray that does what this wants.

Comment 36

[Srujana Peddinti [:srujana121]]

(In reply to Nathan Froyd [:froydnj] from comment #34)

(In reply to Srujana Peddinti from comment #33)

Pointers automatically convert to void*. The result of Length() implicitly converts to unsigned int (and fortunately always fits into unsigned int due to the way nsTArray works).
How come functions are passed without any arguments? Where are we telling that the array is the argument for Length() function?

Not if the elements require external data to be sorted. Maybe the elements of the array are indices into some other data structure, and you want to sort the indices in a particular order. See e.g. the use of NS_QuickSort in dom/bindings/BindingUtils.cpp.

Yes, this makes sense.

Comment 37

[Srujana Peddinti [:srujana121]]

I have read the documentations but I did not understand how to run the gtests on a subset of tests.

I have tried

1. changing GTEST_FILTER env. variable

2. mach gtest Testname

3. Using --gtest_filter= 'Testname' option.

These are the docs I read from.
https://developer.mozilla.org/en-US/docs/Mozilla/Developer_guide/Build_Instructions/GTest
https://github.com/google/googletest/blob/master/googletest/docs/advanced.md#running-test-programs-advanced-options

Can anyone help me out in running gtests?

Comment 38

[Eric Rahm [:erahm]]

(In reply to Srujana Peddinti from comment #37)

I have read the documentations but I did not understand how to run the gtests on a subset of tests.

I have tried

1. changing GTEST_FILTER env. variable

2. mach gtest Testname

3. Using --gtest_filter= 'Testname' option.

These are the docs I read from.
https://developer.mozilla.org/en-US/docs/Mozilla/Developer_guide/Build_Instructions/GTest
https://github.com/google/googletest/blob/master/googletest/docs/advanced.md#running-test-programs-advanced-options

Can anyone help me out in running gtests?

The format for the filter is <suite_name>.<test_name>, so for example a command for testing the nsTArray sort function is:

./mach gtest TArray.test_comparator_objects

to run all nsTArray tests you can do:

./mach gtest TArray.*

Comment 39

[Srujana Peddinti [:srujana121]]

The compare function in the quicksort function takes void pointers as arguments. But in one of the comments, it was decided to use elem_type pointers. So should I change the compare function declaration in quicksort from void* to elem_type*?

Comment 40

[David Parks [:handyman]]

(In reply to Eric Rahm [:erahm] from comment #35)

I'm pretty sure we already have a sort function in nsTArray that does what this wants.

This is supposed to be more generic -- that method works on a type with a int Compare(const elem_type&, const elem_type&) method but this should use anything with the right signature as a comparator like e.g. a lambda.

Comment 41

[Eric Rahm [:erahm]]

(In reply to David Parks (dparks) [:handyman] from comment #40)

(In reply to Eric Rahm [:erahm] from comment #35)

I'm pretty sure we already have a sort function in nsTArray that does what this wants.

This is supposed to be more generic -- that method works on a type with a int Compare(const elem_type&, const elem_type&) method but this should use anything with the right signature as a comparator like e.g. a lambda.

nsTArray<int> foo({3, 2, 10});
foo.Sort([](int a, int b) { return a - b; })

works fine.

Comment 42

[Masatoshi Kimura [:emk]]

So is this bug still valid?

Comment 43

[Eric Rahm [:erahm]]

(In reply to Masatoshi Kimura [:emk] from comment #42)

So is this bug still valid?

If I understand correctly, no, but it's hard for me to figure out way the original purpose was. At this point we could definitely use better docs for nsTArray::Sort and converting a bunch of one-off comparators to lambdas would be useful (I think that was the original goal).

Comment 44

[David Parks [:handyman]]

(In reply to Eric Rahm [:erahm] from comment #41)

nsTArray<int> foo({3, 2, 10});
foo.Sort([](int a, int b) { return a - b; })

works fine.

Ah, I missed that there is an implicitly constructable CompareWrapper class.

Comment 45

[BugBot [:suhaib / :marco]]

The bug assignee didn't login in Bugzilla in the last 7 months, so the assignee is being reset.

Comment 46

[Nika Layzell [:nika] (ni? for response)]

Closing this bug because as noted in comment 44 we can already sort with a lambda in the Sort function call.