Re: [patch #3596] Sort directories before files in "ls"

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Francesco Montorsi on 12/14/2005 1:52 PM:
> Hi all,
>    could anyone have a look at this patch ?

Usually, posting patches directly to the list instead of to the savannah
web site gets more response for this project.

My review:

> Index: ChangeLog

Usually, ChangeLog entries are just attached separately from the patch
(chances are, by the time your patch is incorporated, other changes will
have been committed, leading to needless patch conflicts if you include
ChangeLog in your patch).

> ===================================================================
> RCS file: /cvsroot/coreutils/coreutils/ChangeLog,v
> retrieving revision 1.1565
> diff -b -u -2 -r1.1565 ChangeLog
> --- ChangeLog   3 Dec 2005 22:24:31 -0000   1.1565
> +++ ChangeLog   9 Dec 2005 13:42:46 -0000
> @@ -3,4 +3,6 @@
>     * Version 6.0-cvs.
>
> +   * src/ls.c: Added the -e,--group-directories option to group
> +   directories before files (Francesco Montorsi).
>     * src/rm.c (long_opts): Change the name of each undocumented, for-
>     testing-only option to start with `-', so that it cannot render

WHOA - Don't add your entry into the middle of someone else's.  Make a
brand new entry.  Also, your entry needs to call out all the functions you
touched, not just an overview.  Your change is big enough that you will
need to assign copyright, and it is more formal than just a disclaimer on
the savannah website.  Ask Paul or Jim for the paperwork you will need to
mail into the FSF.

> Index: NEWS
> ===================================================================
> RCS file: /cvsroot/coreutils/coreutils/NEWS,v
> retrieving revision 1.349
> diff -b -u -2 -r1.349 NEWS
> --- NEWS    26 Nov 2005 07:51:27 -0000  1.349
> +++ NEWS    9 Dec 2005 13:42:49 -0000
> @@ -24,4 +24,7 @@
>    attempts to have the default be the best of both worlds.
>
> +  ls now supports the '-e,--group-directories' option to group directories
> +  before files.

Call out the two spellings in separate words.

> +
>  ** Scheduled for removal
>
> Index: THANKS
> ===================================================================
> RCS file: /cvsroot/coreutils/coreutils/THANKS,v
> retrieving revision 1.412
> diff -b -u -2 -r1.412 THANKS
> --- THANKS  16 Nov 2005 09:30:25 -0000  1.412
> +++ THANKS  9 Dec 2005 13:42:50 -0000
> @@ -152,4 +152,5 @@
>  Fletcher Mattox                     address@hidden
>  Florin Iucha                        address@hidden
> +Francesco Montorsi                  address@hidden
>  François Pinard                     address@hidden
>  Frank Adler                         address@hidden
> Index: src/ls.c
> ===================================================================
> RCS file: /cvsroot/coreutils/coreutils/src/ls.c,v
> retrieving revision 1.403
> diff -b -u -2 -r1.403 ls.c
> --- src/ls.c    17 Nov 2005 12:28:34 -0000  1.403
> +++ src/ls.c    9 Dec 2005 13:49:09 -0000
> @@ -592,4 +592,8 @@
>  static bool immediate_dirs;
>
> +/* True means that directories are grouped before files.
- -e,--group-directories  */

Follow the GNU coding conventions, plus the example of existing code in
this file.  In particular, comments end in a period, and must not exceed
80 columns.

> +
> +static bool group_dirs;
> +
>  /* Which files to ignore.  */
>
> @@ -751,4 +755,5 @@
>    {"directory", no_argument, NULL, 'd'},
>    {"dired", no_argument, NULL, 'D'},
> +  {"group-directories", no_argument, NULL, 'e'},
>    {"full-time", no_argument, NULL, FULL_TIME_OPTION},
>    {"human-readable", no_argument, NULL, 'h'},
> @@ -1490,5 +1495,5 @@
>
>    while ((c = getopt_long (argc, argv,
> -              "abcdfghiklmnopqrstuvw:xABCDFGHI:LNQRST:UX1",
> +               "abcdefghiklmnopqrstuvw:xABCDFGHI:LNQRST:UX1",

Careful on leading whitespace.  For changes, coreutils prefers leading
tabs except in string literals that wrap lines (although, as I recently
found out, you should not change whitespace on lines that are otherwise
unaffected, as it makes diff's to prior versions harder to follow).

>                long_options, NULL)) != -1)
>      {
> @@ -1511,4 +1516,8 @@
>       break;
>
> +    case 'e':
> +      group_dirs = true;
> +      break;
> +
>     case 'f':
>       /* Same as enabling -a -U and disabling -l -s.  */
> @@ -2728,4 +2737,11 @@
>  }
>
> +/* Returns true if the given fileinfo refers to a directory */
> +static bool is_directory (const struct fileinfo *f)
> +{
> +  return f->filetype == directory || f->filetype == arg_directory;
> +}

You didn't ensure that f->filetype was always populated.  You will have to
look for the existing code that checks whether to stat files, such as when
- -F is in effect, and add that a stat must take place if your proposed -e
is in effect.

> +
> +
>  #ifdef S_ISLNK
>
> @@ -2810,6 +2826,5 @@
>       order.  */
>    for (i = files_index; i-- != 0; )
> -    if ((files[i].filetype == directory || files[i].filetype ==
arg_directory)
> -   && (!ignore_dot_and_dot_dot
> +    if (is_directory(&files[i]) && (!ignore_dot_and_dot_dot
>         || !basename_is_dot_or_dotdot (files[i].name)))

You broke coding conventions again.  Nested conditionals indent to the
level of the open parenthesis that groups them.

>        {
> @@ -2956,4 +2971,34 @@
>  static int rev_str_extension (V a, V b) { return compstr_extension (b,
a); }
>
> +/* Groups directories at the beginning of the array */
> +
> +static inline int
> +cmp_directories (V a, V b)
> +{
> +  bool a_isfolder = is_directory((struct fileinfo const *)a);
> +  bool b_isfolder = is_directory((struct fileinfo const *)b);
> +  if (a_isfolder && !b_isfolder)
> +     return -1;        // a goes before b
> +  else if (!a_isfolder && b_isfolder)

When the previous if statement only does a return, the else is redundant.
 You can make this line just say if instead of else if.

> +     return 1;          // b goes before a
> +
> +  /* a and b are both files or both folders;
> +     will be sorted later using the user-selected sortkey */
> +  return 0;
> +}
> +
> +int group_dirs_first()
> +{
> +  int i, n=0;
> +  qsort (files, files_index, sizeof *files, cmp_directories);

EVIL.  You are calling qsort twice for every element (once to put
directories first, then twice again on the subsets).  This is twice as
slow as just writing a proper sort function that does everything all in
one comparison, so that you only call qsort once.

> +
> +  /* now return the number of directories which are present in the
files array */
> +  for (i=0; i < files_index; i++)
> +    if (is_directory(&files[i]))
> +      n++;          /* found another directory */
> +  return n;

This is a bit of an overkill, and would not be necessary if you fixed it
to only call qsort once.

> +}
> +
> +
>  /* Sort the files now in the table.  */
>
> @@ -2962,4 +3007,9 @@
>  {
>    int (*func) (V, V);
> +  int dirs;
> +
> +  /* do we have to do two separate sorts ? */
> +  if (group_dirs)
> +     dirs = group_dirs_first();
>
>    /* Try strcoll.  If it fails, fall back on strcmp.  We can't safely
> @@ -3040,4 +3090,9 @@
>      }
>
> +  if (group_dirs && dirs > 0) {
> +    /* sort separately the directories and the files */
> +    qsort (files, dirs, sizeof *files, func);
> +    qsort (&files[dirs], files_index - dirs, sizeof *files, func);
> +  } else
>    qsort (files, files_index, sizeof *files, func);
>  }
> @@ -4136,4 +4191,7 @@
>                                 and do not dereference symbolic links\n\
>    -D, --dired                generate output designed for Emacs' dired
mode\n\
> +"), stdout);
> +      fputs(_("\
> +  -e, --group-directories    group directories before files\n\
>  "), stdout);
>        fputs (_("\


- --
Life is short - so eat dessert first!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFDoPZj84KuGfSFAYARAqhAAJwPzyjroF0whDjrD1r3HiZ1YABKOwCgieUw
vAmu1RNgyxvaYd9gHEdgEb8=
=K9PQ
-----END PGP SIGNATURE-----