Support order by clause

[jhspetersson]

Support order by clause

[jhspetersson]

Finally order by has arrived. Enjoy fresh 0.4.x branch :)

[ceyhunsony]

This was why I forked your repository. I would like to implement sorting feature as a practice of Rust. Do you have any specific plans? Would you advise me to go on or not start?
Edit: I mean my other account.

[jhspetersson]

This project started as my own practice in Rust, so why not to participate?

I see these steps in doing the thing:

1. add lexems for ORDER BY and ordering option to the expression type
2. add optional buffer before printing all the stuff in check_file()
3. apply sorting and actual printing of the results

The only hard part is the very last one because of printing code currently being a mess :) That would be great if you could improve it in any way. Good luck!

[jhspetersson]

Yeah, I see. We need to define enum of possible columns with standard (ordering type, etc.) and specific (e.g., precomputed datetimes) fields. And after that query would contain a collection of such enums + specific options (asc/desc ordering, whether to display column value or just use it for ordering, etc.).

Something like that. We definitely have to manage all that magic string values as number of columns grows.

[ceyhunsony]

Great news! And sorry for not being able to implement it and not informing, I was quite busy with my day job lately.
Thank you again!

[jhspetersson]

That would require buffering of the results, but is also what I'm planning to implement in not so distant future. Thanks for creating an issue!

[ceyhunsony]

Oh, looking at the code, I see what you mean, now :) But it's ok, improving it would be a cool task and an even better exercise. (Not that mess, btw. 👍)

Thanks for the steps, I will be looking into implementation this weekend.

Have a nice day!

[ciuncan]

Hi, here is a work-in-progress commit for order by feature:
ciuncan@d102885

It supports orderby clause with both field names and field projection order.

I think I could make check_file and visit_dirs generic and accept an io::Write instead of passing an optional buffer for sorting. This way, we could pass stdout when no sorting is required or pass something (like my Vec<Sortable>) that we can buffer results and then sort them.

Currently I didn't handle limit clause right, where I should have sorted before applying limit, instead it sorts the limited set. I will fix that.

I also will try to work on tidying the code, just wanted to give heads-up on progress.
Btw, your code rocks!

[jhspetersson]

Great job! I really like how you streamlined that printing stuff written in a rather rushed manner. It's much clearer now even for myself :) The only catch I see here is that check_file() should know target output being some abstract buffer or stdout as soon as terminal colors would be involved (planning dircolors support right now).

[ceyhunsony]

Thank you!

For the terminal colors case, I think maybe we could extend the write trait and accept Result type instead of a direct string (well, I maybe its rather u8 slice, but we can make it work), then if the result is Err, we could set color and print, otherwise business as usual.

For sorting combined with limiting, I think BTreeMap will be a great match. Here is a proof of concept:
(playground) (gist)

If BTreeMap has more than k elements, and the last key (largest) is less then the one to be inserted, remove last and insert the new one (it will find its correct place, keeping keys sorted). And The values will be the strings we were going to actually print. I will try this at weekend.

[jhspetersson]

Great pull request implementing this feature has landed. I'll try to polish few things, and we are ready to go.

[jhspetersson]

It seems that all values are sorted as strings, but we unfortunately have file sizes and datetimes as well. And it would be handy to have ordering by columns we have not requested directly, as such:

fselect path from ~ order by size

Wouldn't it be too much to ask you for a couple of additions to this overall great PR, @ciuncan ? :)

Anyway, thanks again for that!

[ceyhunsony]

Hi @jhspetersson ,

Thank you, I am glad you liked it!

Ah, the ordering by dates and file sizes eluded my attention, that is a quite valid request. I would like to solve that issue.

But maybe, before starting this, we should store what's parsed so far in appropriate data structures so that those values can be used in other phases (such as sorting, filtering) and therefore we also eliminate the code duplication and redundant computation. After that the sorting could be easier as well. We should be able to selectively compute what is actually necessary (fields used in projection, filtering and ordering) rather that pre-computing all possible field values; otherwise there would be much more redundant computation. I wonder if this kind of thing is possible while retaining great compile time knowledge Rust provides, while being flexible as imposed by runtime input.

What are your thoughts on this? I hope I am not carried away with over-engineering. :D

[ceyhunsony]

By the way, ordering by columns not appearing in projections should be possible, I believe I hand-tested it. Otherwise there is another issue there that needs solving. :)

[ceyhunsony]

That seems like a great solution, just as I imagined, better put into words. I guess we can build a nice enum structure so that in average they have similar size (for example, strings will already not be an issue, since actual characters are heap allocated), so putting them in a collection will not waste memory.

I will try this, this week. Thanks!