src/ls.c

   1 /* `dir', `vdir' and `ls' directory listing programs for GNU.
   2    Copyright (C) 85, 88, 90, 91, 1995-2004 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  17
  18 /* If ls_mode is LS_MULTI_COL,
  19    the multi-column format is the default regardless
  20    of the type of output device.
  21    This is for the `dir' program.
  22
  23    If ls_mode is LS_LONG_FORMAT,
  24    the long format is the default regardless of the
  25    type of output device.
  26    This is for the `vdir' program.
  27
  28    If ls_mode is LS_LS,
  29    the output format depends on whether the output
  30    device is a terminal.
  31    This is for the `ls' program.  */
  32
  33 /* Written by Richard Stallman and David MacKenzie.  */
  34
  35 /* Color support by Peter Anvin <Peter.Anvin@linux.org> and Dennis
  36    Flaherty <dennisf@denix.elk.miles.com> based on original patches by
  37    Greg Lee <lee@uhunix.uhcc.hawaii.edu>.  */
  38
  39 #include <config.h>
  40 #include <sys/types.h>
  41
  42 #if HAVE_TERMIOS_H
  43 # include <termios.h>
  44 #endif
  45
  46 #ifdef GWINSZ_IN_SYS_IOCTL
  47 # include <sys/ioctl.h>
  48 #endif
  49
  50 #ifdef WINSIZE_IN_PTEM
  51 # include <sys/stream.h>
  52 # include <sys/ptem.h>
  53 #endif
  54
  55 #include <stdio.h>
  56 #include <assert.h>
  57 #include <setjmp.h>
  58 #include <grp.h>
  59 #include <pwd.h>
  60 #include <getopt.h>
  61 #include <signal.h>
  62
  63 #ifndef SA_NOCLDSTOP
  64 # define sigprocmask(How, Set, Oset) /* empty */
  65 # define sigset_t int
  66 #endif
  67
  68 /* Get mbstate_t, mbrtowc(), mbsinit(), wcwidth().  */
  69 #if HAVE_WCHAR_H
  70 # include <wchar.h>
  71 #endif
  72
  73 /* Get iswprint().  */
  74 #if HAVE_WCTYPE_H
  75 # include <wctype.h>
  76 #endif
  77 #if !defined iswprint && !HAVE_ISWPRINT
  78 # define iswprint(wc) 1
  79 #endif
  80
  81 #ifndef HAVE_DECL_WCWIDTH
  82 "this configure-time declaration test was not run"
  83 #endif
  84 #if !HAVE_DECL_WCWIDTH
  85 int wcwidth ();
  86 #endif
  87
  88 /* If wcwidth() doesn't exist, assume all printable characters have
  89    width 1.  */
  90 #ifndef wcwidth
  91 # if !HAVE_WCWIDTH
  92 #  define wcwidth(wc) ((wc) == 0 ? 0 : iswprint (wc) ? 1 : -1)
  93 # endif
  94 #endif
  95
  96 #include "system.h"
  97 #include <fnmatch.h>
  98
  99 #include "acl.h"
 100 #include "argmatch.h"
 101 #include "dev-ino.h"
 102 #include "dirname.h"
 103 #include "dirfd.h"
 104 #include "error.h"
 105 #include "hard-locale.h"
 106 #include "hash.h"
 107 #include "human.h"
 108 #include "filemode.h"
 109 #include "inttostr.h"
 110 #include "ls.h"
 111 #include "mbswidth.h"
 112 #include "obstack.h"
 113 #include "path-concat.h"
 114 #include "quote.h"
 115 #include "quotearg.h"
 116 #include "same.h"
 117 #include "strftime.h"
 118 #include "strverscmp.h"
 119 #include "xstrtol.h"
 120 #include "xreadlink.h"
 121
 122 #define PROGRAM_NAME (ls_mode == LS_LS ? "ls" \
 123                       : (ls_mode == LS_MULTI_COL \
 124                          ? "dir" : "vdir"))
 125
 126 #define AUTHORS "Richard Stallman", "David MacKenzie"
 127
 128 #define obstack_chunk_alloc malloc
 129 #define obstack_chunk_free free
 130
 131 /* Return an int indicating the result of comparing two integers.
 132    Subtracting doesn't always work, due to overflow.  */
 133 #define longdiff(a, b) ((a) < (b) ? -1 : (a) > (b))
 134
 135 /* Arrange to make lstat calls go through the wrapper function
 136    on systems with an lstat function that does not dereference symlinks
 137    that are specified with a trailing slash.  */
 138 #if ! LSTAT_FOLLOWS_SLASHED_SYMLINK
 139 int rpl_lstat (const char *, struct stat *);
 140 # undef lstat
 141 # define lstat(Name, Stat_buf) rpl_lstat(Name, Stat_buf)
 142 #endif
 143
 144 #if HAVE_STRUCT_DIRENT_D_TYPE && defined DTTOIF
 145 # define DT_INIT(Val) = Val
 146 #else
 147 # define DT_INIT(Val) /* empty */
 148 #endif
 149
 150 #if ! HAVE_STRUCT_STAT_ST_AUTHOR
 151 # define st_author st_uid
 152 #endif
 153
 154 /* Cray/Unicos DMF: use the file's migrated, not real, status */
 155 #if HAVE_ST_DM_MODE
 156 # define ST_DM_MODE(Stat_buf) ((Stat_buf).st_dm_mode)
 157 #else
 158 # define ST_DM_MODE(Stat_buf) ((Stat_buf).st_mode)
 159 #endif
 160
 161 enum filetype
 162   {
 163     unknown DT_INIT (DT_UNKNOWN),
 164     fifo DT_INIT (DT_FIFO),
 165     chardev DT_INIT (DT_CHR),
 166     directory DT_INIT (DT_DIR),
 167     blockdev DT_INIT (DT_BLK),
 168     normal DT_INIT (DT_REG),
 169     symbolic_link DT_INIT (DT_LNK),
 170     sock DT_INIT (DT_SOCK),
 171     arg_directory DT_INIT (2 * (DT_UNKNOWN | DT_FIFO | DT_CHR | DT_DIR | DT_BLK
 172                                 | DT_REG | DT_LNK | DT_SOCK))
 173   };
 174
 175 struct fileinfo
 176   {
 177     /* The file name.  */
 178     char *name;
 179
 180     struct stat stat;
 181
 182     /* For symbolic link, name of the file linked to, otherwise zero.  */
 183     char *linkname;
 184
 185     /* For symbolic link and long listing, st_mode of file linked to, otherwise
 186        zero.  */
 187     mode_t linkmode;
 188
 189     /* For symbolic link and color printing, true if linked-to file
 190        exists, otherwise false.  */
 191     bool linkok;
 192
 193     enum filetype filetype;
 194
 195 #if HAVE_ACL
 196     /* For long listings, true if the file has an access control list.  */
 197     bool have_acl;
 198 #endif
 199   };
 200
 201 #if HAVE_ACL
 202 # define FILE_HAS_ACL(F) ((F)->have_acl)
 203 #else
 204 # define FILE_HAS_ACL(F) 0
 205 #endif
 206
 207 #define LEN_STR_PAIR(s) sizeof (s) - 1, s
 208
 209 /* Null is a valid character in a color indicator (think about Epson
 210    printers, for example) so we have to use a length/buffer string
 211    type.  */
 212
 213 struct bin_str
 214   {
 215     size_t len;                 /* Number of bytes */
 216     const char *string;         /* Pointer to the same */
 217   };
 218
 219 #ifndef STDC_HEADERS
 220 time_t time ();
 221 #endif
 222
 223 char *getgroup ();
 224 char *getuser ();
 225
 226 #if ! HAVE_TCGETPGRP
 227 # define tcgetpgrp(Fd) 0
 228 #endif
 229
 230 static size_t quote_name (FILE *out, const char *name,
 231                           struct quoting_options const *options,
 232                           size_t *width);
 233 static char *make_link_path (const char *path, const char *linkname);
 234 static int decode_switches (int argc, char **argv);
 235 static bool file_ignored (char const *name);
 236 static uintmax_t gobble_file (const char *name, enum filetype type,
 237                               bool explicit_arg, const char *dirname);
 238 static void print_color_indicator (const char *name, mode_t mode, int linkok);
 239 static void put_indicator (const struct bin_str *ind);
 240 static void add_ignore_pattern (const char *pattern);
 241 static void attach (char *dest, const char *dirname, const char *name);
 242 static void clear_files (void);
 243 static void extract_dirs_from_files (const char *dirname,
 244                                      bool ignore_dot_and_dot_dot);
 245 static void get_link_name (const char *filename, struct fileinfo *f);
 246 static void indent (size_t from, size_t to);
 247 static size_t calculate_columns (bool by_columns);
 248 static void print_current_files (void);
 249 static void print_dir (const char *name, const char *realname);
 250 static void print_file_name_and_frills (const struct fileinfo *f);
 251 static void print_horizontal (void);
 252 static int format_user_width (uid_t u);
 253 static int format_group_width (gid_t g);
 254 static void print_long_format (const struct fileinfo *f);
 255 static void print_many_per_line (void);
 256 static void print_name_with_quoting (const char *p, mode_t mode,
 257                                      int linkok,
 258                                      struct obstack *stack);
 259 static void prep_non_filename_text (void);
 260 static void print_type_indicator (mode_t mode);
 261 static void print_with_commas (void);
 262 static void queue_directory (const char *name, const char *realname);
 263 static void sort_files (void);
 264 static void parse_ls_color (void);
 265 void usage (int status);
 266
 267 /* The name the program was run with, stripped of any leading path.  */
 268 char *program_name;
 269
 270 /* Initial size of hash table.
 271    Most hierarchies are likely to be shallower than this.  */
 272 #define INITIAL_TABLE_SIZE 30
 273
 274 /* The set of `active' directories, from the current command-line argument
 275    to the level in the hierarchy at which files are being listed.
 276    A directory is represented by its device and inode numbers (struct dev_ino).
 277    A directory is added to this set when ls begins listing it or its
 278    entries, and it is removed from the set just after ls has finished
 279    processing it.  This set is used solely to detect loops, e.g., with
 280    mkdir loop; cd loop; ln -s ../loop sub; ls -RL  */
 281 static Hash_table *active_dir_set;
 282
 283 #define LOOP_DETECT (!!active_dir_set)
 284
 285 /* The table of files in the current directory:
 286
 287    `files' points to a vector of `struct fileinfo', one per file.
 288    `nfiles' is the number of elements space has been allocated for.
 289    `files_index' is the number actually in use.  */
 290
 291 /* Address of block containing the files that are described.  */
 292 static struct fileinfo *files;  /* FIXME: rename this to e.g. cwd_file */
 293
 294 /* Length of block that `files' points to, measured in files.  */
 295 static size_t nfiles;  /* FIXME: rename this to e.g. cwd_n_alloc */
 296
 297 /* Index of first unused in `files'.  */
 298 static size_t files_index;  /* FIXME: rename this to e.g. cwd_n_used */
 299
 300 /* When true, in a color listing, color each symlink name according to the
 301    type of file it points to.  Otherwise, color them according to the `ln'
 302    directive in LS_COLORS.  Dangling (orphan) symlinks are treated specially,
 303    regardless.  This is set when `ln=target' appears in LS_COLORS.  */
 304
 305 static bool color_symlink_as_referent;
 306
 307 /* mode of appropriate file for colorization */
 308 #define FILE_OR_LINK_MODE(File) \
 309     ((color_symlink_as_referent & (File)->linkok) \
 310      ? (File)->linkmode : (File)->stat.st_mode)
 311
 312
 313 /* Record of one pending directory waiting to be listed.  */
 314
 315 struct pending
 316   {
 317     char *name;
 318     /* If the directory is actually the file pointed to by a symbolic link we
 319        were told to list, `realname' will contain the name of the symbolic
 320        link, otherwise zero.  */
 321     char *realname;
 322     struct pending *next;
 323   };
 324
 325 static struct pending *pending_dirs;
 326
 327 /* Current time in seconds and nanoseconds since 1970, updated as
 328    needed when deciding whether a file is recent.  */
 329
 330 static time_t current_time = TYPE_MINIMUM (time_t);
 331 static int current_time_ns = -1;
 332
 333 /* The number of columns to use for columns containing inode numbers,
 334    block sizes, link counts, owners, groups, authors, major device
 335    numbers, minor device numbers, and file sizes, respectively.  */
 336
 337 static int inode_number_width;
 338 static int block_size_width;
 339 static int nlink_width;
 340 static int owner_width;
 341 static int group_width;
 342 static int author_width;
 343 static int major_device_number_width;
 344 static int minor_device_number_width;
 345 static int file_size_width;
 346
 347 /* Option flags */
 348
 349 /* long_format for lots of info, one per line.
 350    one_per_line for just names, one per line.
 351    many_per_line for just names, many per line, sorted vertically.
 352    horizontal for just names, many per line, sorted horizontally.
 353    with_commas for just names, many per line, separated by commas.
 354
 355    -l (and other options that imply -l), -1, -C, -x and -m control
 356    this parameter.  */
 357
 358 enum format
 359   {
 360     long_format,                /* -l and other options that imply -l */
 361     one_per_line,               /* -1 */
 362     many_per_line,              /* -C */
 363     horizontal,                 /* -x */
 364     with_commas                 /* -m */
 365   };
 366
 367 static enum format format;
 368
 369 /* `full-iso' uses full ISO-style dates and times.  `long-iso' uses longer
 370    ISO-style time stamps, though shorter than `full-iso'.  `iso' uses shorter
 371    ISO-style time stamps.  `locale' uses locale-dependent time stamps.  */
 372 enum time_style
 373   {
 374     full_iso_time_style,        /* --time-style=full-iso */
 375     long_iso_time_style,        /* --time-style=long-iso */
 376     iso_time_style,             /* --time-style=iso */
 377     locale_time_style           /* --time-style=locale */
 378   };
 379
 380 static char const *const time_style_args[] =
 381 {
 382   "full-iso", "long-iso", "iso", "locale", 0
 383 };
 384
 385 static enum time_style const time_style_types[] =
 386 {
 387   full_iso_time_style, long_iso_time_style, iso_time_style,
 388   locale_time_style, 0
 389 };
 390
 391 /* Type of time to print or sort by.  Controlled by -c and -u.  */
 392
 393 enum time_type
 394   {
 395     time_mtime,                 /* default */
 396     time_ctime,                 /* -c */
 397     time_atime                  /* -u */
 398   };
 399
 400 static enum time_type time_type;
 401
 402 /* The file characteristic to sort by.  Controlled by -t, -S, -U, -X, -v.  */
 403
 404 enum sort_type
 405   {
 406     sort_none,                  /* -U */
 407     sort_name,                  /* default */
 408     sort_extension,             /* -X */
 409     sort_time,                  /* -t */
 410     sort_size,                  /* -S */
 411     sort_version                /* -v */
 412   };
 413
 414 static enum sort_type sort_type;
 415
 416 /* Direction of sort.
 417    false means highest first if numeric,
 418    lowest first if alphabetic;
 419    these are the defaults.
 420    true means the opposite order in each case.  -r  */
 421
 422 static bool sort_reverse;
 423
 424 /* True means to display owner information.  -g turns this off.  */
 425
 426 static bool print_owner = true;
 427
 428 /* True means to display author information.  */
 429
 430 static bool print_author;
 431
 432 /* True means to display group information.  -G and -o turn this off.  */
 433
 434 static bool print_group = true;
 435
 436 /* True means print the user and group id's as numbers rather
 437    than as names.  -n  */
 438
 439 static bool numeric_ids;
 440
 441 /* True means mention the size in blocks of each file.  -s  */
 442
 443 static bool print_block_size;
 444
 445 /* Human-readable options for output.  */
 446 static int human_output_opts;
 447
 448 /* The units to use when printing sizes other than file sizes.  */
 449 static uintmax_t output_block_size;
 450
 451 /* Likewise, but for file sizes.  */
 452 static uintmax_t file_output_block_size = 1;
 453
 454 /* Follow the output with a special string.  Using this format,
 455    Emacs' dired mode starts up twice as fast, and can handle all
 456    strange characters in file names.  */
 457 static bool dired;
 458
 459 /* `none' means don't mention the type of files.
 460    `classify' means mention file types and mark executables.
 461    `file_type' means mention only file types.
 462
 463    Controlled by -F, -p, and --indicator-style.  */
 464
 465 enum indicator_style
 466   {
 467     none,       /*     --indicator-style=none */
 468     classify,   /* -F, --indicator-style=classify */
 469     file_type   /* -p, --indicator-style=file-type */
 470   };
 471
 472 static enum indicator_style indicator_style;
 473
 474 /* Names of indicator styles.  */
 475 static char const *const indicator_style_args[] =
 476 {
 477   "none", "classify", "file-type", 0
 478 };
 479
 480 static enum indicator_style const indicator_style_types[]=
 481 {
 482   none, classify, file_type
 483 };
 484
 485 /* True means use colors to mark types.  Also define the different
 486    colors as well as the stuff for the LS_COLORS environment variable.
 487    The LS_COLORS variable is now in a termcap-like format.  */
 488
 489 static bool print_with_color;
 490
 491 enum color_type
 492   {
 493     color_never,                /* 0: default or --color=never */
 494     color_always,               /* 1: --color=always */
 495     color_if_tty                /* 2: --color=tty */
 496   };
 497
 498 enum Dereference_symlink
 499   {
 500     DEREF_UNDEFINED = 1,
 501     DEREF_NEVER,
 502     DEREF_COMMAND_LINE_ARGUMENTS,       /* -H */
 503     DEREF_COMMAND_LINE_SYMLINK_TO_DIR,  /* the default, in certain cases */
 504     DEREF_ALWAYS                        /* -L */
 505   };
 506
 507 enum indicator_no
 508   {
 509     C_LEFT, C_RIGHT, C_END, C_NORM, C_FILE, C_DIR, C_LINK, C_FIFO, C_SOCK,
 510     C_BLK, C_CHR, C_MISSING, C_ORPHAN, C_EXEC, C_DOOR
 511   };
 512
 513 static const char *const indicator_name[]=
 514   {
 515     "lc", "rc", "ec", "no", "fi", "di", "ln", "pi", "so",
 516     "bd", "cd", "mi", "or", "ex", "do", NULL
 517   };
 518
 519 struct color_ext_type
 520   {
 521     struct bin_str ext;         /* The extension we're looking for */
 522     struct bin_str seq;         /* The sequence to output when we do */
 523     struct color_ext_type *next;        /* Next in list */
 524   };
 525
 526 static struct bin_str color_indicator[] =
 527   {
 528     { LEN_STR_PAIR ("\033[") },         /* lc: Left of color sequence */
 529     { LEN_STR_PAIR ("m") },             /* rc: Right of color sequence */
 530     { 0, NULL },                        /* ec: End color (replaces lc+no+rc) */
 531     { LEN_STR_PAIR ("0") },             /* no: Normal */
 532     { LEN_STR_PAIR ("0") },             /* fi: File: default */
 533     { LEN_STR_PAIR ("01;34") },         /* di: Directory: bright blue */
 534     { LEN_STR_PAIR ("01;36") },         /* ln: Symlink: bright cyan */
 535     { LEN_STR_PAIR ("33") },            /* pi: Pipe: yellow/brown */
 536     { LEN_STR_PAIR ("01;35") },         /* so: Socket: bright magenta */
 537     { LEN_STR_PAIR ("01;33") },         /* bd: Block device: bright yellow */
 538     { LEN_STR_PAIR ("01;33") },         /* cd: Char device: bright yellow */
 539     { 0, NULL },                        /* mi: Missing file: undefined */
 540     { 0, NULL },                        /* or: Orphanned symlink: undefined */
 541     { LEN_STR_PAIR ("01;32") },         /* ex: Executable: bright green */
 542     { LEN_STR_PAIR ("01;35") }          /* do: Door: bright magenta */
 543   };
 544
 545 /* FIXME: comment  */
 546 static struct color_ext_type *color_ext_list = NULL;
 547
 548 /* Buffer for color sequences */
 549 static char *color_buf;
 550
 551 /* True means to check for orphaned symbolic link, for displaying
 552    colors.  */
 553
 554 static bool check_symlink_color;
 555
 556 /* True means mention the inode number of each file.  -i  */
 557
 558 static bool print_inode;
 559
 560 /* What to do with symbolic links.  Affected by -d, -F, -H, -l (and
 561    other options that imply -l), and -L.  */
 562
 563 static enum Dereference_symlink dereference;
 564
 565 /* True means when a directory is found, display info on its
 566    contents.  -R  */
 567
 568 static bool recursive;
 569
 570 /* True means when an argument is a directory name, display info
 571    on it itself.  -d  */
 572
 573 static bool immediate_dirs;
 574
 575 /* Which files to ignore.  */
 576
 577 static enum
 578 {
 579   /* Ignore files whose names start with `.', and files specified by
 580      --hide and --ignore.  */
 581   IGNORE_DEFAULT,
 582
 583   /* Ignore `.', `..', and files specified by --ignore.  */
 584   IGNORE_DOT_AND_DOTDOT,
 585
 586   /* Ignore only files specified by --ignore.  */
 587   IGNORE_MINIMAL
 588 } ignore_mode;
 589
 590 /* A linked list of shell-style globbing patterns.  If a non-argument
 591    file name matches any of these patterns, it is ignored.
 592    Controlled by -I.  Multiple -I options accumulate.
 593    The -B option adds `*~' and `.*~' to this list.  */
 594
 595 struct ignore_pattern
 596   {
 597     const char *pattern;
 598     struct ignore_pattern *next;
 599   };
 600
 601 static struct ignore_pattern *ignore_patterns;
 602
 603 /* Similar to IGNORE_PATTERNS, except that -a or -A causes this
 604    variable itself to be ignored.  */
 605 static struct ignore_pattern *hide_patterns;
 606
 607 /* True means output nongraphic chars in file names as `?'.
 608    (-q, --hide-control-chars)
 609    qmark_funny_chars and the quoting style (-Q, --quoting-style=WORD) are
 610    independent.  The algorithm is: first, obey the quoting style to get a
 611    string representing the file name;  then, if qmark_funny_chars is set,
 612    replace all nonprintable chars in that string with `?'.  It's necessary
 613    to replace nonprintable chars even in quoted strings, because we don't
 614    want to mess up the terminal if control chars get sent to it, and some
 615    quoting methods pass through control chars as-is.  */
 616 static bool qmark_funny_chars;
 617
 618 /* Quoting options for file and dir name output.  */
 619
 620 static struct quoting_options *filename_quoting_options;
 621 static struct quoting_options *dirname_quoting_options;
 622
 623 /* The number of chars per hardware tab stop.  Setting this to zero
 624    inhibits the use of TAB characters for separating columns.  -T */
 625 static size_t tabsize;
 626
 627 /* True means print each directory name before listing it.  */
 628
 629 static bool print_dir_name;
 630
 631 /* The line length to use for breaking lines in many-per-line format.
 632    Can be set with -w.  */
 633
 634 static size_t line_length;
 635
 636 /* If true, the file listing format requires that stat be called on
 637    each file.  */
 638
 639 static bool format_needs_stat;
 640
 641 /* Similar to `format_needs_stat', but set if only the file type is
 642    needed.  */
 643
 644 static bool format_needs_type;
 645
 646 /* strftime formats for non-recent and recent files, respectively, in
 647    -l output.  */
 648
 649 static char const *long_time_format[2] =
 650   {
 651     /* strftime format for non-recent files (older than 6 months), in
 652        -l output when --time-style=locale is specified.  This should
 653        contain the year, month and day (at least), in an order that is
 654        understood by people in your locale's territory.
 655        Please try to keep the number of used screen columns small,
 656        because many people work in windows with only 80 columns.  But
 657        make this as wide as the other string below, for recent files.  */
 658     N_("%b %e  %Y"),
 659     /* strftime format for recent files (younger than 6 months), in
 660        -l output when --time-style=locale is specified.  This should
 661        contain the month, day and time (at least), in an order that is
 662        understood by people in your locale's territory.
 663        Please try to keep the number of used screen columns small,
 664        because many people work in windows with only 80 columns.  But
 665        make this as wide as the other string above, for non-recent files.  */
 666     N_("%b %e %H:%M")
 667   };
 668
 669 /* The set of signals that are caught.  */
 670
 671 static sigset_t caught_signals;
 672
 673 /* If nonzero, the value of the pending fatal signal.  */
 674
 675 static sig_atomic_t volatile interrupt_signal;
 676
 677 /* A count of the number of pending stop signals that have been received.  */
 678
 679 static sig_atomic_t volatile stop_signal_count;
 680
 681 /* Desired exit status.  */
 682
 683 static int exit_status;
 684
 685 /* For long options that have no equivalent short option, use a
 686    non-character as a pseudo short option, starting with CHAR_MAX + 1.  */
 687 enum
 688 {
 689   AUTHOR_OPTION = CHAR_MAX + 1,
 690   BLOCK_SIZE_OPTION,
 691   COLOR_OPTION,
 692   DEREFERENCE_COMMAND_LINE_SYMLINK_TO_DIR_OPTION,
 693   FORMAT_OPTION,
 694   FULL_TIME_OPTION,
 695   HIDE_OPTION,
 696   INDICATOR_STYLE_OPTION,
 697   QUOTING_STYLE_OPTION,
 698   SHOW_CONTROL_CHARS_OPTION,
 699   SI_OPTION,
 700   SORT_OPTION,
 701   TIME_OPTION,
 702   TIME_STYLE_OPTION
 703 };
 704
 705 static struct option const long_options[] =
 706 {
 707   {"all", no_argument, 0, 'a'},
 708   {"escape", no_argument, 0, 'b'},
 709   {"directory", no_argument, 0, 'd'},
 710   {"dired", no_argument, 0, 'D'},
 711   {"full-time", no_argument, 0, FULL_TIME_OPTION},
 712   {"human-readable", no_argument, 0, 'h'},
 713   {"inode", no_argument, 0, 'i'},
 714   {"kilobytes", no_argument, 0, 'k'}, /* long form is obsolescent */
 715   {"numeric-uid-gid", no_argument, 0, 'n'},
 716   {"no-group", no_argument, 0, 'G'},
 717   {"hide-control-chars", no_argument, 0, 'q'},
 718   {"reverse", no_argument, 0, 'r'},
 719   {"size", no_argument, 0, 's'},
 720   {"width", required_argument, 0, 'w'},
 721   {"almost-all", no_argument, 0, 'A'},
 722   {"ignore-backups", no_argument, 0, 'B'},
 723   {"classify", no_argument, 0, 'F'},
 724   {"file-type", no_argument, 0, 'p'},
 725   {"si", no_argument, 0, SI_OPTION},
 726   {"dereference-command-line", no_argument, 0, 'H'},
 727   {"dereference-command-line-symlink-to-dir", no_argument, 0,
 728    DEREFERENCE_COMMAND_LINE_SYMLINK_TO_DIR_OPTION},
 729   {"hide", required_argument, 0, HIDE_OPTION},
 730   {"ignore", required_argument, 0, 'I'},
 731   {"indicator-style", required_argument, 0, INDICATOR_STYLE_OPTION},
 732   {"dereference", no_argument, 0, 'L'},
 733   {"literal", no_argument, 0, 'N'},
 734   {"quote-name", no_argument, 0, 'Q'},
 735   {"quoting-style", required_argument, 0, QUOTING_STYLE_OPTION},
 736   {"recursive", no_argument, 0, 'R'},
 737   {"format", required_argument, 0, FORMAT_OPTION},
 738   {"show-control-chars", no_argument, 0, SHOW_CONTROL_CHARS_OPTION},
 739   {"sort", required_argument, 0, SORT_OPTION},
 740   {"tabsize", required_argument, 0, 'T'},
 741   {"time", required_argument, 0, TIME_OPTION},
 742   {"time-style", required_argument, 0, TIME_STYLE_OPTION},
 743   {"color", optional_argument, 0, COLOR_OPTION},
 744   {"block-size", required_argument, 0, BLOCK_SIZE_OPTION},
 745   {"author", no_argument, 0, AUTHOR_OPTION},
 746   {GETOPT_HELP_OPTION_DECL},
 747   {GETOPT_VERSION_OPTION_DECL},
 748   {NULL, 0, NULL, 0}
 749 };
 750
 751 static char const *const format_args[] =
 752 {
 753   "verbose", "long", "commas", "horizontal", "across",
 754   "vertical", "single-column", 0
 755 };
 756
 757 static enum format const format_types[] =
 758 {
 759   long_format, long_format, with_commas, horizontal, horizontal,
 760   many_per_line, one_per_line
 761 };
 762
 763 static char const *const sort_args[] =
 764 {
 765   "none", "time", "size", "extension", "version", 0
 766 };
 767
 768 static enum sort_type const sort_types[] =
 769 {
 770   sort_none, sort_time, sort_size, sort_extension, sort_version
 771 };
 772
 773 static char const *const time_args[] =
 774 {
 775   "atime", "access", "use", "ctime", "status", 0
 776 };
 777
 778 static enum time_type const time_types[] =
 779 {
 780   time_atime, time_atime, time_atime, time_ctime, time_ctime
 781 };
 782
 783 static char const *const color_args[] =
 784 {
 785   /* force and none are for compatibility with another color-ls version */
 786   "always", "yes", "force",
 787   "never", "no", "none",
 788   "auto", "tty", "if-tty", 0
 789 };
 790
 791 static enum color_type const color_types[] =
 792 {
 793   color_always, color_always, color_always,
 794   color_never, color_never, color_never,
 795   color_if_tty, color_if_tty, color_if_tty
 796 };
 797
 798 /* Information about filling a column.  */
 799 struct column_info
 800 {
 801   bool valid_len;
 802   size_t line_len;
 803   size_t *col_arr;
 804 };
 805
 806 /* Array with information about column filledness.  */
 807 static struct column_info *column_info;
 808
 809 /* Maximum number of columns ever possible for this display.  */
 810 static size_t max_idx;
 811
 812 /* The minimum width of a column is 3: 1 character for the name and 2
 813    for the separating white space.  */
 814 #define MIN_COLUMN_WIDTH        3
 815
 816
 817 /* This zero-based index is used solely with the --dired option.
 818    When that option is in effect, this counter is incremented for each
 819    byte of output generated by this program so that the beginning
 820    and ending indices (in that output) of every file name can be recorded
 821    and later output themselves.  */
 822 static size_t dired_pos;
 823
 824 #define DIRED_PUTCHAR(c) do {putchar ((c)); ++dired_pos;} while (0)
 825
 826 /* Write S to STREAM and increment DIRED_POS by S_LEN.  */
 827 #define DIRED_FPUTS(s, stream, s_len) \
 828     do {fputs ((s), (stream)); dired_pos += s_len;} while (0)
 829
 830 /* Like DIRED_FPUTS, but for use when S is a literal string.  */
 831 #define DIRED_FPUTS_LITERAL(s, stream) \
 832     do {fputs ((s), (stream)); dired_pos += sizeof((s)) - 1;} while (0)
 833
 834 #define DIRED_INDENT()                                                  \
 835     do                                                                  \
 836       {                                                                 \
 837         if (dired)                                                      \
 838           DIRED_FPUTS_LITERAL ("  ", stdout);                           \
 839       }                                                                 \
 840     while (0)
 841
 842 /* With --dired, store pairs of beginning and ending indices of filenames.  */
 843 static struct obstack dired_obstack;
 844
 845 /* With --dired, store pairs of beginning and ending indices of any
 846    directory names that appear as headers (just before `total' line)
 847    for lists of directory entries.  Such directory names are seen when
 848    listing hierarchies using -R and when a directory is listed with at
 849    least one other command line argument.  */
 850 static struct obstack subdired_obstack;
 851
 852 /* Save the current index on the specified obstack, OBS.  */
 853 #define PUSH_CURRENT_DIRED_POS(obs)                                     \
 854   do                                                                    \
 855     {                                                                   \
 856       if (dired)                                                        \
 857         obstack_grow ((obs), &dired_pos, sizeof (dired_pos));           \
 858     }                                                                   \
 859   while (0)
 860
 861 /* With -R, this stack is used to help detect directory cycles.
 862    The device/inode pairs on this stack mirror the pairs in the
 863    active_dir_set hash table.  */
 864 static struct obstack dev_ino_obstack;
 865
 866 /* Push a pair onto the device/inode stack.  */
 867 #define DEV_INO_PUSH(Dev, Ino)                                          \
 868   do                                                                    \
 869     {                                                                   \
 870       struct dev_ino *di;                                               \
 871       obstack_blank (&dev_ino_obstack, sizeof (struct dev_ino));        \
 872       di = -1 + (struct dev_ino *) obstack_next_free (&dev_ino_obstack); \
 873       di->st_dev = (Dev);                                               \
 874       di->st_ino = (Ino);                                               \
 875     }                                                                   \
 876   while (0)
 877
 878 /* Pop a dev/ino struct off the global dev_ino_obstack
 879    and return that struct.  */
 880 static struct dev_ino
 881 dev_ino_pop (void)
 882 {
 883   assert (sizeof (struct dev_ino) <= obstack_object_size (&dev_ino_obstack));
 884   obstack_blank (&dev_ino_obstack, -(int) (sizeof (struct dev_ino)));
 885   return *(struct dev_ino*) obstack_next_free (&dev_ino_obstack);
 886 }
 887
 888 #define ASSERT_MATCHING_DEV_INO(Name, Di)       \
 889   do                                            \
 890     {                                           \
 891       struct stat sb;                           \
 892       assert (Name);                            \
 893       assert (0 <= stat (Name, &sb));           \
 894       assert (sb.st_dev == Di.st_dev);          \
 895       assert (sb.st_ino == Di.st_ino);          \
 896     }                                           \
 897   while (0)
 898
 899
 900 /* Write to standard output PREFIX, followed by the quoting style and
 901    a space-separated list of the integers stored in OS all on one line.  */
 902
 903 static void
 904 dired_dump_obstack (const char *prefix, struct obstack *os)
 905 {
 906   size_t n_pos;
 907
 908   n_pos = obstack_object_size (os) / sizeof (dired_pos);
 909   if (n_pos > 0)
 910     {
 911       size_t i;
 912       size_t *pos;
 913
 914       pos = (size_t *) obstack_finish (os);
 915       fputs (prefix, stdout);
 916       for (i = 0; i < n_pos; i++)
 917         printf (" %lu", (unsigned long int) pos[i]);
 918       putchar ('\n');
 919     }
 920 }
 921
 922 static size_t
 923 dev_ino_hash (void const *x, size_t table_size)
 924 {
 925   struct dev_ino const *p = x;
 926   return (uintmax_t) p->st_ino % table_size;
 927 }
 928
 929 static bool
 930 dev_ino_compare (void const *x, void const *y)
 931 {
 932   struct dev_ino const *a = x;
 933   struct dev_ino const *b = y;
 934   return SAME_INODE (*a, *b) ? true : false;
 935 }
 936
 937 static void
 938 dev_ino_free (void *x)
 939 {
 940   free (x);
 941 }
 942
 943 /* Add the device/inode pair (P->st_dev/P->st_ino) to the set of
 944    active directories.  Return true if there is already a matching
 945    entry in the table.  */
 946
 947 static bool
 948 visit_dir (dev_t dev, ino_t ino)
 949 {
 950   struct dev_ino *ent;
 951   struct dev_ino *ent_from_table;
 952   bool found_match;
 953
 954   ent = xmalloc (sizeof *ent);
 955   ent->st_ino = ino;
 956   ent->st_dev = dev;
 957
 958   /* Attempt to insert this entry into the table.  */
 959   ent_from_table = hash_insert (active_dir_set, ent);
 960
 961   if (ent_from_table == NULL)
 962     {
 963       /* Insertion failed due to lack of memory.  */
 964       xalloc_die ();
 965     }
 966
 967   found_match = (ent_from_table != ent);
 968
 969   if (found_match)
 970     {
 971       /* ent was not inserted, so free it.  */
 972       free (ent);
 973     }
 974
 975   return found_match;
 976 }
 977
 978 static void
 979 free_pending_ent (struct pending *p)
 980 {
 981   if (p->name)
 982     free (p->name);
 983   if (p->realname)
 984     free (p->realname);
 985   free (p);
 986 }
 987
 988 static void
 989 restore_default_color (void)
 990 {
 991   put_indicator (&color_indicator[C_LEFT]);
 992   put_indicator (&color_indicator[C_RIGHT]);
 993 }
 994
 995 /* An ordinary signal was received; arrange for the program to exit.  */
 996
 997 static void
 998 sighandler (int sig)
 999 {
1000 #ifndef SA_NOCLDSTOP
1001   signal (sig, SIG_IGN);
1002 #endif
1003
1004   if (! interrupt_signal)
1005     interrupt_signal = sig;
1006 }
1007
1008 /* A SIGTSTP was received; arrange for the program to suspend itself.  */
1009
1010 static void
1011 stophandler (int sig)
1012 {
1013 #ifndef SA_NOCLDSTOP
1014   signal (sig, stophandler);
1015 #endif
1016
1017   if (! interrupt_signal)
1018     stop_signal_count++;
1019 }
1020
1021 /* Process any pending signals.  If signals are caught, this function
1022    should be called periodically.  Ideally there should never be an
1023    unbounded amount of time when signals are not being processed.
1024    Signal handling can restore the default colors, so callers must
1025    immediately change colors after invoking this function.  */
1026
1027 static void
1028 process_signals (void)
1029 {
1030   while (interrupt_signal | stop_signal_count)
1031     {
1032       int sig;
1033       int stops;
1034       sigset_t oldset;
1035
1036       restore_default_color ();
1037       fflush (stdout);
1038
1039       sigprocmask (SIG_BLOCK, &caught_signals, &oldset);
1040
1041       /* Reload interrupt_signal and stop_signal_count, in case a new
1042          signal was handled before sigprocmask took effect.  */
1043       sig = interrupt_signal;
1044       stops = stop_signal_count;
1045
1046       /* SIGTSTP is special, since the application can receive that signal
1047          more than once.  In this case, don't set the signal handler to the
1048          default.  Instead, just raise the uncatchable SIGSTOP.  */
1049       if (stops)
1050         {
1051           stop_signal_count = stops - 1;
1052           sig = SIGSTOP;
1053         }
1054       else
1055         signal (sig, SIG_DFL);
1056
1057       /* Exit or suspend the program.  */
1058       raise (sig);
1059       sigprocmask (SIG_SETMASK, &oldset, NULL);
1060
1061       /* If execution reaches here, then the program has been
1062          continued (after being suspended).  */
1063     }
1064 }
1065
1066 int
1067 main (int argc, char **argv)
1068 {
1069   register int i;
1070   register struct pending *thispend;
1071   int n_files;
1072
1073   /* The signals that are trapped, and the number of such signals.  */
1074   static int const sig[] = { SIGHUP, SIGINT, SIGPIPE,
1075                              SIGQUIT, SIGTERM, SIGTSTP };
1076   enum { nsigs = sizeof sig / sizeof sig[0] };
1077
1078 #ifndef SA_NOCLDSTOP
1079   bool caught_sig[nsigs];
1080 #endif
1081
1082   initialize_main (&argc, &argv);
1083   program_name = argv[0];
1084   setlocale (LC_ALL, "");
1085   bindtextdomain (PACKAGE, LOCALEDIR);
1086   textdomain (PACKAGE);
1087
1088   atexit (close_stdout);
1089
1090 #define N_ENTRIES(Array) (sizeof Array / sizeof *(Array))
1091   assert (N_ENTRIES (color_indicator) + 1 == N_ENTRIES (indicator_name));
1092
1093   exit_status = EXIT_SUCCESS;
1094   print_dir_name = true;
1095   pending_dirs = 0;
1096
1097   i = decode_switches (argc, argv);
1098
1099   if (print_with_color)
1100     parse_ls_color ();
1101
1102   /* Test print_with_color again, because the call to parse_ls_color
1103      may have just reset it -- e.g., if LS_COLORS is invalid.  */
1104   if (print_with_color)
1105     {
1106       /* Avoid following symbolic links when possible.  */
1107       if (color_indicator[C_ORPHAN].string != NULL
1108           || (color_indicator[C_MISSING].string != NULL
1109               && format == long_format))
1110         check_symlink_color = true;
1111
1112       /* If the standard output is a controlling terminal, watch out
1113          for signals, so that the colors can be restored to the
1114          default state if "ls" is suspended or interrupted.  */
1115
1116       if (0 <= tcgetpgrp (STDOUT_FILENO))
1117         {
1118           int j;
1119 #ifdef SA_NOCLDSTOP
1120           struct sigaction act;
1121
1122           sigemptyset (&caught_signals);
1123           for (j = 0; j < nsigs; j++)
1124             {
1125               sigaction (sig[j], NULL, &act);
1126               if (act.sa_handler != SIG_IGN)
1127                 sigaddset (&caught_signals, sig[j]);
1128             }
1129
1130           act.sa_mask = caught_signals;
1131           act.sa_flags = SA_RESTART;
1132
1133           for (j = 0; j < nsigs; j++)
1134             if (sigismember (&caught_signals, sig[j]))
1135               {
1136                 act.sa_handler = sig[j] == SIGTSTP ? stophandler : sighandler;
1137                 sigaction (sig[j], &act, NULL);
1138               }
1139 #else
1140           for (j = 0; j < nsigs; j++)
1141             {
1142               caught_sig[j] = (signal (sig[j], SIG_IGN) != SIG_IGN);
1143               if (caught_sig[j])
1144                 signal (sig[j], sig[j] == SIGTSTP ? stophandler : sighandler);
1145             }
1146 #endif
1147         }
1148
1149       prep_non_filename_text ();
1150     }
1151
1152   if (dereference == DEREF_UNDEFINED)
1153     dereference = ((immediate_dirs
1154                     || indicator_style == classify
1155                     || format == long_format)
1156                    ? DEREF_NEVER
1157                    : DEREF_COMMAND_LINE_SYMLINK_TO_DIR);
1158
1159   /* When using -R, initialize a data structure we'll use to
1160      detect any directory cycles.  */
1161   if (recursive)
1162     {
1163       active_dir_set = hash_initialize (INITIAL_TABLE_SIZE, NULL,
1164                                         dev_ino_hash,
1165                                         dev_ino_compare,
1166                                         dev_ino_free);
1167       if (active_dir_set == NULL)
1168         xalloc_die ();
1169
1170       obstack_init (&dev_ino_obstack);
1171     }
1172
1173   format_needs_stat = sort_type == sort_time || sort_type == sort_size
1174     || format == long_format
1175     || dereference == DEREF_ALWAYS
1176     || print_block_size || print_inode;
1177   format_needs_type = (!format_needs_stat
1178                        && (recursive || print_with_color
1179                            || indicator_style != none));
1180
1181   if (dired)
1182     {
1183       obstack_init (&dired_obstack);
1184       obstack_init (&subdired_obstack);
1185     }
1186
1187   nfiles = 100;
1188   files = xnmalloc (nfiles, sizeof *files);
1189   files_index = 0;
1190
1191   clear_files ();
1192
1193   n_files = argc - i;
1194
1195   if (n_files <= 0)
1196     {
1197       if (immediate_dirs)
1198         gobble_file (".", directory, true, "");
1199       else
1200         queue_directory (".", 0);
1201     }
1202   else
1203     do
1204       gobble_file (argv[i++], unknown, true, "");
1205     while (i < argc);
1206
1207   if (files_index)
1208     {
1209       sort_files ();
1210       if (!immediate_dirs)
1211         extract_dirs_from_files ("", false);
1212       /* `files_index' might be zero now.  */
1213     }
1214
1215   /* In the following if/else blocks, it is sufficient to test `pending_dirs'
1216      (and not pending_dirs->name) because there may be no markers in the queue
1217      at this point.  A marker may be enqueued when extract_dirs_from_files is
1218      called with a non-empty string or via print_dir.  */
1219   if (files_index)
1220     {
1221       print_current_files ();
1222       if (pending_dirs)
1223         DIRED_PUTCHAR ('\n');
1224     }
1225   else if (n_files <= 1 && pending_dirs && pending_dirs->next == 0)
1226     print_dir_name = false;
1227
1228   while (pending_dirs)
1229     {
1230       thispend = pending_dirs;
1231       pending_dirs = pending_dirs->next;
1232
1233       if (LOOP_DETECT)
1234         {
1235           if (thispend->name == NULL)
1236             {
1237               /* thispend->name == NULL means this is a marker entry
1238                  indicating we've finished processing the directory.
1239                  Use its dev/ino numbers to remove the corresponding
1240                  entry from the active_dir_set hash table.  */
1241               struct dev_ino di = dev_ino_pop ();
1242               struct dev_ino *found = hash_delete (active_dir_set, &di);
1243               /* ASSERT_MATCHING_DEV_INO (thispend->realname, di); */
1244               assert (found);
1245               dev_ino_free (found);
1246               free_pending_ent (thispend);
1247               continue;
1248             }
1249         }
1250
1251       print_dir (thispend->name, thispend->realname);
1252
1253       free_pending_ent (thispend);
1254       print_dir_name = true;
1255     }
1256
1257   if (print_with_color)
1258     {
1259       int j;
1260
1261       restore_default_color ();
1262       fflush (stdout);
1263
1264       /* Restore the default signal handling.  */
1265 #ifdef SA_NOCLDSTOP
1266       for (j = 0; j < nsigs; j++)
1267         if (sigismember (&caught_signals, sig[j]))
1268           signal (sig[j], SIG_DFL);
1269 #else
1270       for (j = 0; j < nsigs; j++)
1271         if (caught_sig[j])
1272           signal (sig[j], SIG_DFL);
1273 #endif
1274
1275       /* Act on any signals that arrived before the default was restored.
1276          This can process signals out of order, but there doesn't seem to
1277          be an easy way to do them in order, and the order isn't that
1278          important anyway.  */
1279       for (j = stop_signal_count; j; j--)
1280         raise (SIGSTOP);
1281       j = interrupt_signal;
1282       if (j)
1283         raise (j);
1284     }
1285
1286   if (dired)
1287     {
1288       /* No need to free these since we're about to exit.  */
1289       dired_dump_obstack ("//DIRED//", &dired_obstack);
1290       dired_dump_obstack ("//SUBDIRED//", &subdired_obstack);
1291       printf ("//DIRED-OPTIONS// --quoting-style=%s\n",
1292               quoting_style_args[get_quoting_style (filename_quoting_options)]);
1293     }
1294
1295   if (LOOP_DETECT)
1296     {
1297       assert (hash_get_n_entries (active_dir_set) == 0);
1298       hash_free (active_dir_set);
1299     }
1300
1301   exit (exit_status);
1302 }
1303
1304 /* Set all the option flags according to the switches specified.
1305    Return the index of the first non-option argument.  */
1306
1307 static int
1308 decode_switches (int argc, char **argv)
1309 {
1310   int c;
1311   char *time_style_option = 0;
1312
1313   /* Record whether there is an option specifying sort type.  */
1314   bool sort_type_specified = false;
1315
1316   qmark_funny_chars = false;
1317
1318   /* initialize all switches to default settings */
1319
1320   switch (ls_mode)
1321     {
1322     case LS_MULTI_COL:
1323       /* This is for the `dir' program.  */
1324       format = many_per_line;
1325       set_quoting_style (NULL, escape_quoting_style);
1326       break;
1327
1328     case LS_LONG_FORMAT:
1329       /* This is for the `vdir' program.  */
1330       format = long_format;
1331       set_quoting_style (NULL, escape_quoting_style);
1332       break;
1333
1334     case LS_LS:
1335       /* This is for the `ls' program.  */
1336       if (isatty (STDOUT_FILENO))
1337         {
1338           format = many_per_line;
1339           /* See description of qmark_funny_chars, above.  */
1340           qmark_funny_chars = true;
1341         }
1342       else
1343         {
1344           format = one_per_line;
1345           qmark_funny_chars = false;
1346         }
1347       break;
1348
1349     default:
1350       abort ();
1351     }
1352
1353   time_type = time_mtime;
1354   sort_type = sort_name;
1355   sort_reverse = false;
1356   numeric_ids = false;
1357   print_block_size = false;
1358   indicator_style = none;
1359   print_inode = false;
1360   dereference = DEREF_UNDEFINED;
1361   recursive = false;
1362   immediate_dirs = false;
1363   ignore_mode = IGNORE_DEFAULT;
1364   ignore_patterns = NULL;
1365   hide_patterns = NULL;
1366
1367   /* FIXME: put this in a function.  */
1368   {
1369     char const *q_style = getenv ("QUOTING_STYLE");
1370     if (q_style)
1371       {
1372         int i = ARGMATCH (q_style, quoting_style_args, quoting_style_vals);
1373         if (0 <= i)
1374           set_quoting_style (NULL, quoting_style_vals[i]);
1375         else
1376           error (0, 0,
1377          _("ignoring invalid value of environment variable QUOTING_STYLE: %s"),
1378                  quotearg (q_style));
1379       }
1380   }
1381
1382   {
1383     char const *ls_block_size = getenv ("LS_BLOCK_SIZE");
1384     human_output_opts = human_options (ls_block_size, false,
1385                                        &output_block_size);
1386     if (ls_block_size || getenv ("BLOCK_SIZE"))
1387       file_output_block_size = output_block_size;
1388   }
1389
1390   line_length = 80;
1391   {
1392     char const *p = getenv ("COLUMNS");
1393     if (p && *p)
1394       {
1395         unsigned long int tmp_ulong;
1396         if (xstrtoul (p, NULL, 0, &tmp_ulong, NULL) == LONGINT_OK
1397             && 0 < tmp_ulong && tmp_ulong <= SIZE_MAX)
1398           {
1399             line_length = tmp_ulong;
1400           }
1401         else
1402           {
1403             error (0, 0,
1404                _("ignoring invalid width in environment variable COLUMNS: %s"),
1405                    quotearg (p));
1406           }
1407       }
1408   }
1409
1410 #ifdef TIOCGWINSZ
1411   {
1412     struct winsize ws;
1413
1414     if (ioctl (STDOUT_FILENO, TIOCGWINSZ, &ws) != -1
1415         && 0 < ws.ws_col && ws.ws_col == (size_t) ws.ws_col)
1416       line_length = ws.ws_col;
1417   }
1418 #endif
1419
1420   {
1421     char const *p = getenv ("TABSIZE");
1422     tabsize = 8;
1423     if (p)
1424       {
1425         unsigned long int tmp_ulong;
1426         if (xstrtoul (p, NULL, 0, &tmp_ulong, NULL) == LONGINT_OK
1427             && tmp_ulong <= SIZE_MAX)
1428           {
1429             tabsize = tmp_ulong;
1430           }
1431         else
1432           {
1433             error (0, 0,
1434              _("ignoring invalid tab size in environment variable TABSIZE: %s"),
1435                    quotearg (p));
1436           }
1437       }
1438   }
1439
1440   while ((c = getopt_long (argc, argv,
1441                            "abcdfghiklmnopqrstuvw:xABCDFGHI:LNQRST:UX1",
1442                            long_options, NULL)) != -1)
1443     {
1444       switch (c)
1445         {
1446         case 'a':
1447           ignore_mode = IGNORE_MINIMAL;
1448           break;
1449
1450         case 'b':
1451           set_quoting_style (NULL, escape_quoting_style);
1452           break;
1453
1454         case 'c':
1455           time_type = time_ctime;
1456           break;
1457
1458         case 'd':
1459           immediate_dirs = true;
1460           break;
1461
1462         case 'f':
1463           /* Same as enabling -a -U and disabling -l -s.  */
1464           ignore_mode = IGNORE_MINIMAL;
1465           sort_type = sort_none;
1466           sort_type_specified = true;
1467           /* disable -l */
1468           if (format == long_format)
1469             format = (isatty (STDOUT_FILENO) ? many_per_line : one_per_line);
1470           print_block_size = false;     /* disable -s */
1471           print_with_color = false;     /* disable --color */
1472           break;
1473
1474         case 'g':
1475           format = long_format;
1476           print_owner = false;
1477           break;
1478
1479         case 'h':
1480           human_output_opts = human_autoscale | human_SI | human_base_1024;
1481           file_output_block_size = output_block_size = 1;
1482           break;
1483
1484         case 'i':
1485           print_inode = true;
1486           break;
1487
1488         case 'k':
1489           human_output_opts = 0;
1490           file_output_block_size = output_block_size = 1024;
1491           break;
1492
1493         case 'l':
1494           format = long_format;
1495           break;
1496
1497         case 'm':
1498           format = with_commas;
1499           break;
1500
1501         case 'n':
1502           numeric_ids = true;
1503           format = long_format;
1504           break;
1505
1506         case 'o':  /* Just like -l, but don't display group info.  */
1507           format = long_format;
1508           print_group = false;
1509           break;
1510
1511         case 'p':
1512           indicator_style = file_type;
1513           break;
1514
1515         case 'q':
1516           qmark_funny_chars = true;
1517           break;
1518
1519         case 'r':
1520           sort_reverse = true;
1521           break;
1522
1523         case 's':
1524           print_block_size = true;
1525           break;
1526
1527         case 't':
1528           sort_type = sort_time;
1529           sort_type_specified = true;
1530           break;
1531
1532         case 'u':
1533           time_type = time_atime;
1534           break;
1535
1536         case 'v':
1537           sort_type = sort_version;
1538           sort_type_specified = true;
1539           break;
1540
1541         case 'w':
1542           {
1543             unsigned long int tmp_ulong;
1544             if (xstrtoul (optarg, NULL, 0, &tmp_ulong, NULL) != LONGINT_OK
1545                 || ! (0 < tmp_ulong && tmp_ulong <= SIZE_MAX))
1546               error (EXIT_FAILURE, 0, _("invalid line width: %s"),
1547                      quotearg (optarg));
1548             line_length = tmp_ulong;
1549             break;
1550           }
1551
1552         case 'x':
1553           format = horizontal;
1554           break;
1555
1556         case 'A':
1557           if (ignore_mode == IGNORE_DEFAULT)
1558             ignore_mode = IGNORE_DOT_AND_DOTDOT;
1559           break;
1560
1561         case 'B':
1562           add_ignore_pattern ("*~");
1563           add_ignore_pattern (".*~");
1564           break;
1565
1566         case 'C':
1567           format = many_per_line;
1568           break;
1569
1570         case 'D':
1571           dired = true;
1572           break;
1573
1574         case 'F':
1575           indicator_style = classify;
1576           break;
1577
1578         case 'G':               /* inhibit display of group info */
1579           print_group = false;
1580           break;
1581
1582         case 'H':
1583           dereference = DEREF_COMMAND_LINE_ARGUMENTS;
1584           break;
1585
1586         case DEREFERENCE_COMMAND_LINE_SYMLINK_TO_DIR_OPTION:
1587           dereference = DEREF_COMMAND_LINE_SYMLINK_TO_DIR;
1588           break;
1589
1590         case 'I':
1591           add_ignore_pattern (optarg);
1592           break;
1593
1594         case 'L':
1595           dereference = DEREF_ALWAYS;
1596           break;
1597
1598         case 'N':
1599           set_quoting_style (NULL, literal_quoting_style);
1600           break;
1601
1602         case 'Q':
1603           set_quoting_style (NULL, c_quoting_style);
1604           break;
1605
1606         case 'R':
1607           recursive = true;
1608           break;
1609
1610         case 'S':
1611           sort_type = sort_size;
1612           sort_type_specified = true;
1613           break;
1614
1615         case 'T':
1616           {
1617             unsigned long int tmp_ulong;
1618             if (xstrtoul (optarg, NULL, 0, &tmp_ulong, NULL) != LONGINT_OK
1619                 || SIZE_MAX < tmp_ulong)
1620               error (EXIT_FAILURE, 0, _("invalid tab size: %s"),
1621                      quotearg (optarg));
1622             tabsize = tmp_ulong;
1623             break;
1624           }
1625
1626         case 'U':
1627           sort_type = sort_none;
1628           sort_type_specified = true;
1629           break;
1630
1631         case 'X':
1632           sort_type = sort_extension;
1633           sort_type_specified = true;
1634           break;
1635
1636         case '1':
1637           /* -1 has no effect after -l.  */
1638           if (format != long_format)
1639             format = one_per_line;
1640           break;
1641
1642         case AUTHOR_OPTION:
1643           print_author = true;
1644           break;
1645
1646         case HIDE_OPTION:
1647           {
1648             struct ignore_pattern *hide = xmalloc (sizeof *hide);
1649             hide->pattern = optarg;
1650             hide->next = hide_patterns;
1651             hide_patterns = hide;
1652           }
1653           break;
1654
1655         case SORT_OPTION:
1656           sort_type = XARGMATCH ("--sort", optarg, sort_args, sort_types);
1657           sort_type_specified = true;
1658           break;
1659
1660         case TIME_OPTION:
1661           time_type = XARGMATCH ("--time", optarg, time_args, time_types);
1662           break;
1663
1664         case FORMAT_OPTION:
1665           format = XARGMATCH ("--format", optarg, format_args, format_types);
1666           break;
1667
1668         case FULL_TIME_OPTION:
1669           format = long_format;
1670           time_style_option = "full-iso";
1671           break;
1672
1673         case COLOR_OPTION:
1674           {
1675             int i;
1676             if (optarg)
1677               i = XARGMATCH ("--color", optarg, color_args, color_types);
1678             else
1679               /* Using --color with no argument is equivalent to using
1680                  --color=always.  */
1681               i = color_always;
1682
1683             print_with_color = (i == color_always
1684                                 || (i == color_if_tty
1685                                     && isatty (STDOUT_FILENO)));
1686
1687             if (print_with_color)
1688               {
1689                 /* Don't use TAB characters in output.  Some terminal
1690                    emulators can't handle the combination of tabs and
1691                    color codes on the same line.  */
1692                 tabsize = 0;
1693               }
1694             break;
1695           }
1696
1697         case INDICATOR_STYLE_OPTION:
1698           indicator_style = XARGMATCH ("--indicator-style", optarg,
1699                                        indicator_style_args,
1700                                        indicator_style_types);
1701           break;
1702
1703         case QUOTING_STYLE_OPTION:
1704           set_quoting_style (NULL,
1705                              XARGMATCH ("--quoting-style", optarg,
1706                                         quoting_style_args,
1707                                         quoting_style_vals));
1708           break;
1709
1710         case TIME_STYLE_OPTION:
1711           time_style_option = optarg;
1712           break;
1713
1714         case SHOW_CONTROL_CHARS_OPTION:
1715           qmark_funny_chars = false;
1716           break;
1717
1718         case BLOCK_SIZE_OPTION:
1719           human_output_opts = human_options (optarg, true, &output_block_size);
1720           file_output_block_size = output_block_size;
1721           break;
1722
1723         case SI_OPTION:
1724           human_output_opts = human_autoscale | human_SI;
1725           file_output_block_size = output_block_size = 1;
1726           break;
1727
1728         case_GETOPT_HELP_CHAR;
1729
1730         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
1731
1732         default:
1733           usage (EXIT_FAILURE);
1734         }
1735     }
1736
1737   max_idx = MAX (1, line_length / MIN_COLUMN_WIDTH);
1738
1739   filename_quoting_options = clone_quoting_options (NULL);
1740   if (get_quoting_style (filename_quoting_options) == escape_quoting_style)
1741     set_char_quoting (filename_quoting_options, ' ', 1);
1742   if (indicator_style != none)
1743     {
1744       char const *p;
1745       for (p = "*=@|" + indicator_style - 1;  *p;  p++)
1746         set_char_quoting (filename_quoting_options, *p, 1);
1747     }
1748
1749   dirname_quoting_options = clone_quoting_options (NULL);
1750   set_char_quoting (dirname_quoting_options, ':', 1);
1751
1752   /* --dired is meaningful only with --format=long (-l).
1753      Otherwise, ignore it.  FIXME: warn about this?
1754      Alternatively, make --dired imply --format=long?  */
1755   if (dired && format != long_format)
1756     dired = false;
1757
1758   /* If -c or -u is specified and not -l (or any other option that implies -l),
1759      and no sort-type was specified, then sort by the ctime (-c) or atime (-u).
1760      The behavior of ls when using either -c or -u but with neither -l nor -t
1761      appears to be unspecified by POSIX.  So, with GNU ls, `-u' alone means
1762      sort by atime (this is the one that's not specified by the POSIX spec),
1763      -lu means show atime and sort by name, -lut means show atime and sort
1764      by atime.  */
1765
1766   if ((time_type == time_ctime || time_type == time_atime)
1767       && !sort_type_specified && format != long_format)
1768     {
1769       sort_type = sort_time;
1770     }
1771
1772   if (format == long_format)
1773     {
1774       char *style = time_style_option;
1775       static char const posix_prefix[] = "posix-";
1776
1777       if (! style)
1778         if (! (style = getenv ("TIME_STYLE")))
1779           style = "posix-long-iso";
1780
1781       while (strncmp (style, posix_prefix, sizeof posix_prefix - 1) == 0)
1782         {
1783           if (! hard_locale (LC_TIME))
1784             return optind;
1785           style += sizeof posix_prefix - 1;
1786         }
1787
1788       if (*style == '+')
1789         {
1790           char *p0 = style + 1;
1791           char *p1 = strchr (p0, '\n');
1792           if (! p1)
1793             p1 = p0;
1794           else
1795             {
1796               if (strchr (p1 + 1, '\n'))
1797                 error (EXIT_FAILURE, 0, _("invalid time style format %s"),
1798                        quote (p0));
1799               *p1++ = '\0';
1800             }
1801           long_time_format[0] = p0;
1802           long_time_format[1] = p1;
1803         }
1804       else
1805         switch (XARGMATCH ("time style", style,
1806                            time_style_args,
1807                            time_style_types))
1808           {
1809           case full_iso_time_style:
1810             long_time_format[0] = long_time_format[1] =
1811               "%Y-%m-%d %H:%M:%S.%N %z";
1812             break;
1813
1814           case long_iso_time_style:
1815             long_time_format[0] = long_time_format[1] = "%Y-%m-%d %H:%M";
1816             break;
1817
1818           case iso_time_style:
1819             long_time_format[0] = "%Y-%m-%d ";
1820             long_time_format[1] = "%m-%d %H:%M";
1821             break;
1822
1823           case locale_time_style:
1824             if (hard_locale (LC_TIME))
1825               {
1826                 int i;
1827                 for (i = 0; i < 2; i++)
1828                   long_time_format[i] =
1829                     dcgettext (NULL, long_time_format[i], LC_TIME);
1830               }
1831           }
1832     }
1833
1834   return optind;
1835 }
1836
1837 /* Parse a string as part of the LS_COLORS variable; this may involve
1838    decoding all kinds of escape characters.  If equals_end is set an
1839    unescaped equal sign ends the string, otherwise only a : or \0
1840    does.  Set *OUTPUT_COUNT to the number of bytes output.  Return
1841    true if successful.
1842
1843    The resulting string is *not* null-terminated, but may contain
1844    embedded nulls.
1845
1846    Note that both dest and src are char **; on return they point to
1847    the first free byte after the array and the character that ended
1848    the input string, respectively.  */
1849
1850 static bool
1851 get_funky_string (char **dest, const char **src, bool equals_end,
1852                   size_t *output_count)
1853 {
1854   char num;                     /* For numerical codes */
1855   size_t count;                 /* Something to count with */
1856   enum {
1857     ST_GND, ST_BACKSLASH, ST_OCTAL, ST_HEX, ST_CARET, ST_END, ST_ERROR
1858   } state;
1859   const char *p;
1860   char *q;
1861
1862   p = *src;                     /* We don't want to double-indirect */
1863   q = *dest;                    /* the whole darn time.  */
1864
1865   count = 0;                    /* No characters counted in yet.  */
1866   num = 0;
1867
1868   state = ST_GND;               /* Start in ground state.  */
1869   while (state < ST_END)
1870     {
1871       switch (state)
1872         {
1873         case ST_GND:            /* Ground state (no escapes) */
1874           switch (*p)
1875             {
1876             case ':':
1877             case '\0':
1878               state = ST_END;   /* End of string */
1879               break;
1880             case '\\':
1881               state = ST_BACKSLASH; /* Backslash scape sequence */
1882               ++p;
1883               break;
1884             case '^':
1885               state = ST_CARET; /* Caret escape */
1886               ++p;
1887               break;
1888             case '=':
1889               if (equals_end)
1890                 {
1891                   state = ST_END; /* End */
1892                   break;
1893                 }
1894               /* else fall through */
1895             default:
1896               *(q++) = *(p++);
1897               ++count;
1898               break;
1899             }
1900           break;
1901
1902         case ST_BACKSLASH:      /* Backslash escaped character */
1903           switch (*p)
1904             {
1905             case '0':
1906             case '1':
1907             case '2':
1908             case '3':
1909             case '4':
1910             case '5':
1911             case '6':
1912             case '7':
1913               state = ST_OCTAL; /* Octal sequence */
1914               num = *p - '0';
1915               break;
1916             case 'x':
1917             case 'X':
1918               state = ST_HEX;   /* Hex sequence */
1919               num = 0;
1920               break;
1921             case 'a':           /* Bell */
1922               num = 7;          /* Not all C compilers know what \a means */
1923               break;
1924             case 'b':           /* Backspace */
1925               num = '\b';
1926               break;
1927             case 'e':           /* Escape */
1928               num = 27;
1929               break;
1930             case 'f':           /* Form feed */
1931               num = '\f';
1932               break;
1933             case 'n':           /* Newline */
1934               num = '\n';
1935               break;
1936             case 'r':           /* Carriage return */
1937               num = '\r';
1938               break;
1939             case 't':           /* Tab */
1940               num = '\t';
1941               break;
1942             case 'v':           /* Vtab */
1943               num = '\v';
1944               break;
1945             case '?':           /* Delete */
1946               num = 127;
1947               break;
1948             case '_':           /* Space */
1949               num = ' ';
1950               break;
1951             case '\0':          /* End of string */
1952               state = ST_ERROR; /* Error! */
1953               break;
1954             default:            /* Escaped character like \ ^ : = */
1955               num = *p;
1956               break;
1957             }
1958           if (state == ST_BACKSLASH)
1959             {
1960               *(q++) = num;
1961               ++count;
1962               state = ST_GND;
1963             }
1964           ++p;
1965           break;
1966
1967         case ST_OCTAL:          /* Octal sequence */
1968           if (*p < '0' || *p > '7')
1969             {
1970               *(q++) = num;
1971               ++count;
1972               state = ST_GND;
1973             }
1974           else
1975             num = (num << 3) + (*(p++) - '0');
1976           break;
1977
1978         case ST_HEX:            /* Hex sequence */
1979           switch (*p)
1980             {
1981             case '0':
1982             case '1':
1983             case '2':
1984             case '3':
1985             case '4':
1986             case '5':
1987             case '6':
1988             case '7':
1989             case '8':
1990             case '9':
1991               num = (num << 4) + (*(p++) - '0');
1992               break;
1993             case 'a':
1994             case 'b':
1995             case 'c':
1996             case 'd':
1997             case 'e':
1998             case 'f':
1999               num = (num << 4) + (*(p++) - 'a') + 10;
2000               break;
2001             case 'A':
2002             case 'B':
2003             case 'C':
2004             case 'D':
2005             case 'E':
2006             case 'F':
2007               num = (num << 4) + (*(p++) - 'A') + 10;
2008               break;
2009             default:
2010               *(q++) = num;
2011               ++count;
2012               state = ST_GND;
2013               break;
2014             }
2015           break;
2016
2017         case ST_CARET:          /* Caret escape */
2018           state = ST_GND;       /* Should be the next state... */
2019           if (*p >= '@' && *p <= '~')
2020             {
2021               *(q++) = *(p++) & 037;
2022               ++count;
2023             }
2024           else if (*p == '?')
2025             {
2026               *(q++) = 127;
2027               ++count;
2028             }
2029           else
2030             state = ST_ERROR;
2031           break;
2032
2033         default:
2034           abort ();
2035         }
2036     }
2037
2038   *dest = q;
2039   *src = p;
2040   *output_count = count;
2041
2042   return state != ST_ERROR;
2043 }
2044
2045 static void
2046 parse_ls_color (void)
2047 {
2048   const char *p;                /* Pointer to character being parsed */
2049   char *buf;                    /* color_buf buffer pointer */
2050   int state;                    /* State of parser */
2051   int ind_no;                   /* Indicator number */
2052   char label[3];                /* Indicator label */
2053   struct color_ext_type *ext;   /* Extension we are working on */
2054
2055   if ((p = getenv ("LS_COLORS")) == NULL || *p == '\0')
2056     return;
2057
2058   ext = NULL;
2059   strcpy (label, "??");
2060
2061   /* This is an overly conservative estimate, but any possible
2062      LS_COLORS string will *not* generate a color_buf longer than
2063      itself, so it is a safe way of allocating a buffer in
2064      advance.  */
2065   buf = color_buf = xstrdup (p);
2066
2067   state = 1;
2068   while (state > 0)
2069     {
2070       switch (state)
2071         {
2072         case 1:         /* First label character */
2073           switch (*p)
2074             {
2075             case ':':
2076               ++p;
2077               break;
2078
2079             case '*':
2080               /* Allocate new extension block and add to head of
2081                  linked list (this way a later definition will
2082                  override an earlier one, which can be useful for
2083                  having terminal-specific defs override global).  */
2084
2085               ext = xmalloc (sizeof *ext);
2086               ext->next = color_ext_list;
2087               color_ext_list = ext;
2088
2089               ++p;
2090               ext->ext.string = buf;
2091
2092               state = (get_funky_string (&buf, &p, true, &ext->ext.len)
2093                        ? 4 : -1);
2094               break;
2095
2096             case '\0':
2097               state = 0;        /* Done! */
2098               break;
2099
2100             default:    /* Assume it is file type label */
2101               label[0] = *(p++);
2102               state = 2;
2103               break;
2104             }
2105           break;
2106
2107         case 2:         /* Second label character */
2108           if (*p)
2109             {
2110               label[1] = *(p++);
2111               state = 3;
2112             }
2113           else
2114             state = -1; /* Error */
2115           break;
2116
2117         case 3:         /* Equal sign after indicator label */
2118           state = -1;   /* Assume failure...  */
2119           if (*(p++) == '=')/* It *should* be...  */
2120             {
2121               for (ind_no = 0; indicator_name[ind_no] != NULL; ++ind_no)
2122                 {
2123                   if (STREQ (label, indicator_name[ind_no]))
2124                     {
2125                       color_indicator[ind_no].string = buf;
2126                       state = (get_funky_string (&buf, &p, false,
2127                                                  &color_indicator[ind_no].len)
2128                                ? 1 : -1);
2129                       break;
2130                     }
2131                 }
2132               if (state == -1)
2133                 error (0, 0, _("unrecognized prefix: %s"), quotearg (label));
2134             }
2135          break;
2136
2137         case 4:         /* Equal sign after *.ext */
2138           if (*(p++) == '=')
2139             {
2140               ext->seq.string = buf;
2141               state = (get_funky_string (&buf, &p, false, &ext->seq.len)
2142                        ? 1 : -1);
2143             }
2144           else
2145             state = -1;
2146           break;
2147         }
2148     }
2149
2150   if (state < 0)
2151     {
2152       struct color_ext_type *e;
2153       struct color_ext_type *e2;
2154
2155       error (0, 0,
2156              _("unparsable value for LS_COLORS environment variable"));
2157       free (color_buf);
2158       for (e = color_ext_list; e != NULL; /* empty */)
2159         {
2160           e2 = e;
2161           e = e->next;
2162           free (e2);
2163         }
2164       print_with_color = false;
2165     }
2166
2167   if (color_indicator[C_LINK].len == 6
2168       && !strncmp (color_indicator[C_LINK].string, "target", 6))
2169     color_symlink_as_referent = true;
2170 }
2171
2172 /* Request that the directory named NAME have its contents listed later.
2173    If REALNAME is nonzero, it will be used instead of NAME when the
2174    directory name is printed.  This allows symbolic links to directories
2175    to be treated as regular directories but still be listed under their
2176    real names.  NAME == NULL is used to insert a marker entry for the
2177    directory named in REALNAME.
2178    If F is non-NULL, we use its dev/ino information to save
2179    a call to stat -- when doing a recursive (-R) traversal.  */
2180
2181 static void
2182 queue_directory (const char *name, const char *realname)
2183 {
2184   struct pending *new;
2185
2186   new = xmalloc (sizeof *new);
2187   new->realname = realname ? xstrdup (realname) : NULL;
2188   new->name = name ? xstrdup (name) : NULL;
2189   new->next = pending_dirs;
2190   pending_dirs = new;
2191 }
2192
2193 /* Read directory `name', and list the files in it.
2194    If `realname' is nonzero, print its name instead of `name';
2195    this is used for symbolic links to directories.  */
2196
2197 static void
2198 print_dir (const char *name, const char *realname)
2199 {
2200   register DIR *dirp;
2201   register struct dirent *next;
2202   register uintmax_t total_blocks = 0;
2203   static bool first = true;
2204
2205   errno = 0;
2206   dirp = opendir (name);
2207   if (!dirp)
2208     {
2209       error (0, errno, "%s", quotearg_colon (name));
2210       exit_status = EXIT_FAILURE;
2211       return;
2212     }
2213
2214   if (LOOP_DETECT)
2215     {
2216       struct stat dir_stat;
2217       int fd = dirfd (dirp);
2218
2219       /* If dirfd failed, endure the overhead of using stat.  */
2220       if ((0 <= fd
2221            ? fstat (fd, &dir_stat)
2222            : stat (name, &dir_stat)) < 0)
2223         {
2224           error (0, errno, _("cannot determine device and inode of %s"),
2225                  quotearg_colon (name));
2226           exit_status = EXIT_FAILURE;
2227           return;
2228         }
2229
2230       /* If we've already visited this dev/inode pair, warn that
2231          we've found a loop, and do not process this directory.  */
2232       if (visit_dir (dir_stat.st_dev, dir_stat.st_ino))
2233         {
2234           error (0, 0, _("not listing already-listed directory: %s"),
2235                  quotearg_colon (name));
2236           return;
2237         }
2238
2239       DEV_INO_PUSH (dir_stat.st_dev, dir_stat.st_ino);
2240     }
2241
2242   /* Read the directory entries, and insert the subfiles into the `files'
2243      table.  */
2244
2245   clear_files ();
2246
2247   while (1)
2248     {
2249       /* Set errno to zero so we can distinguish between a readdir failure
2250          and when readdir simply finds that there are no more entries.  */
2251       errno = 0;
2252       if ((next = readdir (dirp)) == NULL)
2253         {
2254           if (errno)
2255             {
2256               /* Save/restore errno across closedir call.  */
2257               int e = errno;
2258               closedir (dirp);
2259               errno = e;
2260
2261               /* Arrange to give a diagnostic after exiting this loop.  */
2262               dirp = NULL;
2263             }
2264           break;
2265         }
2266
2267       if (! file_ignored (next->d_name))
2268         {
2269           enum filetype type = unknown;
2270
2271 #if HAVE_STRUCT_DIRENT_D_TYPE
2272           if (next->d_type == DT_BLK
2273               || next->d_type == DT_CHR
2274               || next->d_type == DT_DIR
2275               || next->d_type == DT_FIFO
2276               || next->d_type == DT_LNK
2277               || next->d_type == DT_REG
2278               || next->d_type == DT_SOCK)
2279             type = next->d_type;
2280 #endif
2281           total_blocks += gobble_file (next->d_name, type, false, name);
2282         }
2283     }
2284
2285   if (dirp == NULL || CLOSEDIR (dirp))
2286     {
2287       error (0, errno, _("reading directory %s"), quotearg_colon (name));
2288       exit_status = EXIT_FAILURE;
2289       /* Don't return; print whatever we got.  */
2290     }
2291
2292   /* Sort the directory contents.  */
2293   sort_files ();
2294
2295   /* If any member files are subdirectories, perhaps they should have their
2296      contents listed rather than being mentioned here as files.  */
2297
2298   if (recursive)
2299     extract_dirs_from_files (name, true);
2300
2301   if (recursive | print_dir_name)
2302     {
2303       if (!first)
2304         DIRED_PUTCHAR ('\n');
2305       first = false;
2306       DIRED_INDENT ();
2307       PUSH_CURRENT_DIRED_POS (&subdired_obstack);
2308       dired_pos += quote_name (stdout, realname ? realname : name,
2309                                dirname_quoting_options, NULL);
2310       PUSH_CURRENT_DIRED_POS (&subdired_obstack);
2311       DIRED_FPUTS_LITERAL (":\n", stdout);
2312     }
2313
2314   if (format == long_format || print_block_size)
2315     {
2316       const char *p;
2317       char buf[LONGEST_HUMAN_READABLE + 1];
2318
2319       DIRED_INDENT ();
2320       p = _("total");
2321       DIRED_FPUTS (p, stdout, strlen (p));
2322       DIRED_PUTCHAR (' ');
2323       p = human_readable (total_blocks, buf, human_output_opts,
2324                           ST_NBLOCKSIZE, output_block_size);
2325       DIRED_FPUTS (p, stdout, strlen (p));
2326       DIRED_PUTCHAR ('\n');
2327     }
2328
2329   if (files_index)
2330     print_current_files ();
2331 }
2332
2333 /* Add `pattern' to the list of patterns for which files that match are
2334    not listed.  */
2335
2336 static void
2337 add_ignore_pattern (const char *pattern)
2338 {
2339   register struct ignore_pattern *ignore;
2340
2341   ignore = xmalloc (sizeof *ignore);
2342   ignore->pattern = pattern;
2343   /* Add it to the head of the linked list.  */
2344   ignore->next = ignore_patterns;
2345   ignore_patterns = ignore;
2346 }
2347
2348 /* Return true if one of the PATTERNS matches FILE.  */
2349
2350 static bool
2351 patterns_match (struct ignore_pattern const *patterns, char const *file)
2352 {
2353   struct ignore_pattern const *p;
2354   for (p = patterns; p; p = p->next)
2355     if (fnmatch (p->pattern, file, FNM_PERIOD) == 0)
2356       return true;
2357   return false;
2358 }
2359
2360 /* Return true if FILE should be ignored.  */
2361
2362 static bool
2363 file_ignored (char const *name)
2364 {
2365   return ((ignore_mode != IGNORE_MINIMAL
2366            && name[0] == '.'
2367            && (ignore_mode == IGNORE_DEFAULT || ! name[1 + (name[1] == '.')]))
2368           || (ignore_mode == IGNORE_DEFAULT
2369               && patterns_match (hide_patterns, name))
2370           || patterns_match (ignore_patterns, name));
2371 }
2372
2373 /* POSIX requires that a file size be printed without a sign, even
2374    when negative.  Assume the typical case where negative sizes are
2375    actually positive values that have wrapped around.  */
2376
2377 static uintmax_t
2378 unsigned_file_size (off_t size)
2379 {
2380   return size + (size < 0) * ((uintmax_t) OFF_T_MAX - OFF_T_MIN + 1);
2381 }
2382
2383 /* Enter and remove entries in the table `files'.  */
2384
2385 /* Empty the table of files.  */
2386
2387 static void
2388 clear_files (void)
2389 {
2390   register size_t i;
2391
2392   for (i = 0; i < files_index; i++)
2393     {
2394       free (files[i].name);
2395       if (files[i].linkname)
2396         free (files[i].linkname);
2397     }
2398
2399   files_index = 0;
2400   inode_number_width = 0;
2401   block_size_width = 0;
2402   nlink_width = 0;
2403   owner_width = 0;
2404   group_width = 0;
2405   author_width = 0;
2406   major_device_number_width = 0;
2407   minor_device_number_width = 0;
2408   file_size_width = 0;
2409 }
2410
2411 /* Add a file to the current table of files.
2412    Verify that the file exists, and print an error message if it does not.
2413    Return the number of blocks that the file occupies.  */
2414
2415 static uintmax_t
2416 gobble_file (const char *name, enum filetype type, bool explicit_arg,
2417              const char *dirname)
2418 {
2419   register uintmax_t blocks;
2420   register char *path;
2421   register struct fileinfo *f;
2422
2423   if (files_index == nfiles)
2424     {
2425       files = xnrealloc (files, nfiles, 2 * sizeof *files);
2426       nfiles *= 2;
2427     }
2428
2429   f = &files[files_index];
2430   f->linkname = 0;
2431   f->linkmode = 0;
2432   f->linkok = false;
2433
2434   if (explicit_arg
2435       || format_needs_stat
2436       || (format_needs_type
2437           && (type == unknown
2438
2439               /* FIXME: remove this disjunct.
2440                  I don't think we care about symlinks here, but for now
2441                  this won't make a big performance difference.  */
2442               || type == symbolic_link
2443
2444               /* --indicator-style=classify (aka -F)
2445                  requires that we stat each regular file
2446                  to see if it's executable.  */
2447               || (type == normal && (indicator_style == classify
2448                                      /* This is so that --color ends up
2449                                         highlighting files with the executable
2450                                         bit set even when options like -F are
2451                                         not specified.  */
2452                                      || print_with_color)))))
2453
2454     {
2455       /* `path' is the absolute pathname of this file.  */
2456       int err;
2457
2458       if (name[0] == '/' || dirname[0] == 0)
2459         path = (char *) name;
2460       else
2461         {
2462           path = alloca (strlen (name) + strlen (dirname) + 2);
2463           attach (path, dirname, name);
2464         }
2465
2466       switch (dereference)
2467         {
2468         case DEREF_ALWAYS:
2469           err = stat (path, &f->stat);
2470           break;
2471
2472         case DEREF_COMMAND_LINE_ARGUMENTS:
2473         case DEREF_COMMAND_LINE_SYMLINK_TO_DIR:
2474           if (explicit_arg)
2475             {
2476               bool need_lstat;
2477               err = stat (path, &f->stat);
2478
2479               if (dereference == DEREF_COMMAND_LINE_ARGUMENTS)
2480                 break;
2481
2482               need_lstat = (err < 0
2483                             ? errno == ENOENT
2484                             : ! S_ISDIR (f->stat.st_mode));
2485               if (!need_lstat)
2486                 break;
2487
2488               /* stat failed because of ENOENT, maybe indicating a dangling
2489                  symlink.  Or stat succeeded, PATH does not refer to a
2490                  directory, and --dereference-command-line-symlink-to-dir is
2491                  in effect.  Fall through so that we call lstat instead.  */
2492             }
2493
2494         default: /* DEREF_NEVER */
2495           err = lstat (path, &f->stat);
2496           break;
2497         }
2498
2499       if (err < 0)
2500         {
2501           error (0, errno, "%s", quotearg_colon (path));
2502           exit_status = EXIT_FAILURE;
2503           return 0;
2504         }
2505
2506 #if HAVE_ACL
2507       if (format == long_format)
2508         {
2509           int n = file_has_acl (path, &f->stat);
2510           f->have_acl = (0 < n);
2511           if (n < 0)
2512             error (0, errno, "%s", quotearg_colon (path));
2513         }
2514 #endif
2515
2516       if (S_ISLNK (f->stat.st_mode)
2517           && (format == long_format || check_symlink_color))
2518         {
2519           char *linkpath;
2520           struct stat linkstats;
2521
2522           get_link_name (path, f);
2523           linkpath = make_link_path (path, f->linkname);
2524
2525           /* Avoid following symbolic links when possible, ie, when
2526              they won't be traced and when no indicator is needed.  */
2527           if (linkpath
2528               && (indicator_style != none || check_symlink_color)
2529               && stat (linkpath, &linkstats) == 0)
2530             {
2531               f->linkok = true;
2532
2533               /* Symbolic links to directories that are mentioned on the
2534                  command line are automatically traced if not being
2535                  listed as files.  */
2536               if (!explicit_arg || format == long_format
2537                   || !S_ISDIR (linkstats.st_mode))
2538                 {
2539                   /* Get the linked-to file's mode for the filetype indicator
2540                      in long listings.  */
2541                   f->linkmode = linkstats.st_mode;
2542                   f->linkok = true;
2543                 }
2544             }
2545           if (linkpath)
2546             free (linkpath);
2547         }
2548
2549       if (S_ISLNK (f->stat.st_mode))
2550         f->filetype = symbolic_link;
2551       else if (S_ISDIR (f->stat.st_mode))
2552         {
2553           if (explicit_arg & !immediate_dirs)
2554             f->filetype = arg_directory;
2555           else
2556             f->filetype = directory;
2557         }
2558       else
2559         f->filetype = normal;
2560
2561       {
2562         char buf[INT_BUFSIZE_BOUND (uintmax_t)];
2563         int len = strlen (umaxtostr (f->stat.st_ino, buf));
2564         if (inode_number_width < len)
2565           inode_number_width = len;
2566       }
2567
2568       blocks = ST_NBLOCKS (f->stat);
2569       {
2570         char buf[LONGEST_HUMAN_READABLE + 1];
2571         int len = mbswidth (human_readable (blocks, buf, human_output_opts,
2572                                             ST_NBLOCKSIZE, output_block_size),
2573                             0);
2574         if (block_size_width < len)
2575           block_size_width = len;
2576       }
2577
2578       if (print_owner)
2579         {
2580           int len = format_user_width (f->stat.st_uid);
2581           if (owner_width < len)
2582             owner_width = len;
2583         }
2584
2585       if (print_group)
2586         {
2587           int len = format_group_width (f->stat.st_gid);
2588           if (group_width < len)
2589             group_width = len;
2590         }
2591
2592       if (print_author)
2593         {
2594           int len = format_user_width (f->stat.st_uid);
2595           if (author_width < len)
2596             author_width = len;
2597         }
2598
2599       {
2600         char buf[INT_BUFSIZE_BOUND (uintmax_t)];
2601         int len = strlen (umaxtostr (f->stat.st_nlink, buf));
2602         if (nlink_width < len)
2603           nlink_width = len;
2604       }
2605
2606       if (S_ISCHR (f->stat.st_mode) || S_ISBLK (f->stat.st_mode))
2607         {
2608           char buf[INT_BUFSIZE_BOUND (uintmax_t)];
2609           int len = strlen (umaxtostr (major (f->stat.st_rdev), buf));
2610           if (major_device_number_width < len)
2611             major_device_number_width = len;
2612           len = strlen (umaxtostr (minor (f->stat.st_rdev), buf));
2613           if (minor_device_number_width < len)
2614             minor_device_number_width = len;
2615           len = major_device_number_width + 2 + minor_device_number_width;
2616           if (file_size_width < len)
2617             file_size_width = len;
2618         }
2619       else
2620         {
2621           char buf[LONGEST_HUMAN_READABLE + 1];
2622           uintmax_t size = unsigned_file_size (f->stat.st_size);
2623           int len = mbswidth (human_readable (size, buf, human_output_opts,
2624                                               1, file_output_block_size),
2625                               0);
2626           if (file_size_width < len)
2627             file_size_width = len;
2628         }
2629     }
2630   else
2631     {
2632       f->filetype = type;
2633 #if HAVE_STRUCT_DIRENT_D_TYPE
2634       f->stat.st_mode = DTTOIF (type);
2635 #endif
2636       blocks = 0;
2637     }
2638
2639   f->name = xstrdup (name);
2640   files_index++;
2641
2642   return blocks;
2643 }
2644
2645 #ifdef S_ISLNK
2646
2647 /* Put the name of the file that `filename' is a symbolic link to
2648    into the `linkname' field of `f'.  */
2649
2650 static void
2651 get_link_name (const char *filename, struct fileinfo *f)
2652 {
2653   f->linkname = xreadlink (filename, f->stat.st_size);
2654   if (f->linkname == NULL)
2655     {
2656       error (0, errno, _("cannot read symbolic link %s"),
2657              quotearg_colon (filename));
2658       exit_status = EXIT_FAILURE;
2659     }
2660 }
2661
2662 /* If `linkname' is a relative path and `path' contains one or more
2663    leading directories, return `linkname' with those directories
2664    prepended; otherwise, return a copy of `linkname'.
2665    If `linkname' is zero, return zero.  */
2666
2667 static char *
2668 make_link_path (const char *path, const char *linkname)
2669 {
2670   char *linkbuf;
2671   size_t bufsiz;
2672
2673   if (!linkname)
2674     return NULL;
2675
2676   if (*linkname == '/')
2677     return xstrdup (linkname);
2678
2679   /* The link is to a relative path.  Prepend any leading path
2680      in `path' to the link name.  */
2681   linkbuf = strrchr (path, '/');
2682   if (linkbuf == 0)
2683     return xstrdup (linkname);
2684
2685   bufsiz = linkbuf - path + 1;
2686   linkbuf = xmalloc (bufsiz + strlen (linkname) + 1);
2687   strncpy (linkbuf, path, bufsiz);
2688   strcpy (linkbuf + bufsiz, linkname);
2689   return linkbuf;
2690 }
2691 #endif
2692
2693 /* Return true if base_name (NAME) ends in `.' or `..'
2694    This is so we don't try to recurse on `././././. ...' */
2695
2696 static bool
2697 basename_is_dot_or_dotdot (const char *name)
2698 {
2699   char const *base = base_name (name);
2700   return DOT_OR_DOTDOT (base);
2701 }
2702
2703 /* Remove any entries from `files' that are for directories,
2704    and queue them to be listed as directories instead.
2705    `dirname' is the prefix to prepend to each dirname
2706    to make it correct relative to ls's working dir.
2707    If IGNORE_DOT_AND_DOT_DOT don't treat `.' and `..' as dirs.
2708    This is desirable when processing directories recursively.  */
2709
2710 static void
2711 extract_dirs_from_files (const char *dirname, bool ignore_dot_and_dot_dot)
2712 {
2713   register size_t i;
2714   register size_t j;
2715
2716   if (*dirname && LOOP_DETECT)
2717     {
2718       /* Insert a marker entry first.  When we dequeue this marker entry,
2719          we'll know that DIRNAME has been processed and may be removed
2720          from the set of active directories.  */
2721       queue_directory (NULL, dirname);
2722     }
2723
2724   /* Queue the directories last one first, because queueing reverses the
2725      order.  */
2726   for (i = files_index; i-- != 0; )
2727     if ((files[i].filetype == directory || files[i].filetype == arg_directory)
2728         && (!ignore_dot_and_dot_dot
2729             || !basename_is_dot_or_dotdot (files[i].name)))
2730       {
2731         if (files[i].name[0] == '/' || dirname[0] == 0)
2732           {
2733             queue_directory (files[i].name, files[i].linkname);
2734           }
2735         else
2736           {
2737             char *path = path_concat (dirname, files[i].name, NULL);
2738             queue_directory (path, files[i].linkname);
2739             free (path);
2740           }
2741         if (files[i].filetype == arg_directory)
2742           free (files[i].name);
2743       }
2744
2745   /* Now delete the directories from the table, compacting all the remaining
2746      entries.  */
2747
2748   for (i = 0, j = 0; i < files_index; i++)
2749     {
2750       if (files[i].filetype != arg_directory)
2751         {
2752           if (j < i)
2753             files[j] = files[i];
2754           ++j;
2755         }
2756     }
2757   files_index = j;
2758 }
2759
2760 /* Use strcoll to compare strings in this locale.  If an error occurs,
2761    report an error and longjmp to failed_strcoll.  */
2762
2763 static jmp_buf failed_strcoll;
2764
2765 static int
2766 xstrcoll (char const *a, char const *b)
2767 {
2768   int diff;
2769   errno = 0;
2770   diff = strcoll (a, b);
2771   if (errno)
2772     {
2773       error (0, errno, _("cannot compare file names %s and %s"),
2774              quote_n (0, a), quote_n (1, b));
2775       exit_status = EXIT_FAILURE;
2776       longjmp (failed_strcoll, 1);
2777     }
2778   return diff;
2779 }
2780
2781 /* Comparison routines for sorting the files.  */
2782
2783 typedef void const *V;
2784
2785 static inline int
2786 cmp_ctime (struct fileinfo const *a, struct fileinfo const *b,
2787            int (*cmp) (char const *, char const *))
2788 {
2789   int diff = CTIME_CMP (b->stat, a->stat);
2790   return diff ? diff : cmp (a->name, b->name);
2791 }
2792 static int compare_ctime (V a, V b) { return cmp_ctime (a, b, xstrcoll); }
2793 static int compstr_ctime (V a, V b) { return cmp_ctime (a, b, strcmp); }
2794 static int rev_cmp_ctime (V a, V b) { return compare_ctime (b, a); }
2795 static int rev_str_ctime (V a, V b) { return compstr_ctime (b, a); }
2796
2797 static inline int
2798 cmp_mtime (struct fileinfo const *a, struct fileinfo const *b,
2799            int (*cmp) (char const *, char const *))
2800 {
2801   int diff = MTIME_CMP (b->stat, a->stat);
2802   return diff ? diff : cmp (a->name, b->name);
2803 }
2804 static int compare_mtime (V a, V b) { return cmp_mtime (a, b, xstrcoll); }
2805 static int compstr_mtime (V a, V b) { return cmp_mtime (a, b, strcmp); }
2806 static int rev_cmp_mtime (V a, V b) { return compare_mtime (b, a); }
2807 static int rev_str_mtime (V a, V b) { return compstr_mtime (b, a); }
2808
2809 static inline int
2810 cmp_atime (struct fileinfo const *a, struct fileinfo const *b,
2811            int (*cmp) (char const *, char const *))
2812 {
2813   int diff = ATIME_CMP (b->stat, a->stat);
2814   return diff ? diff : cmp (a->name, b->name);
2815 }
2816 static int compare_atime (V a, V b) { return cmp_atime (a, b, xstrcoll); }
2817 static int compstr_atime (V a, V b) { return cmp_atime (a, b, strcmp); }
2818 static int rev_cmp_atime (V a, V b) { return compare_atime (b, a); }
2819 static int rev_str_atime (V a, V b) { return compstr_atime (b, a); }
2820
2821 static inline int
2822 cmp_size (struct fileinfo const *a, struct fileinfo const *b,
2823           int (*cmp) (char const *, char const *))
2824 {
2825   int diff = longdiff (b->stat.st_size, a->stat.st_size);
2826   return diff ? diff : cmp (a->name, b->name);
2827 }
2828 static int compare_size (V a, V b) { return cmp_size (a, b, xstrcoll); }
2829 static int compstr_size (V a, V b) { return cmp_size (a, b, strcmp); }
2830 static int rev_cmp_size (V a, V b) { return compare_size (b, a); }
2831 static int rev_str_size (V a, V b) { return compstr_size (b, a); }
2832
2833 static inline int
2834 cmp_version (struct fileinfo const *a, struct fileinfo const *b)
2835 {
2836   return strverscmp (a->name, b->name);
2837 }
2838 static int compare_version (V a, V b) { return cmp_version (a, b); }
2839 static int rev_cmp_version (V a, V b) { return compare_version (b, a); }
2840
2841 static inline int
2842 cmp_name (struct fileinfo const *a, struct fileinfo const *b,
2843           int (*cmp) (char const *, char const *))
2844 {
2845   return cmp (a->name, b->name);
2846 }
2847 static int compare_name (V a, V b) { return cmp_name (a, b, xstrcoll); }
2848 static int compstr_name (V a, V b) { return cmp_name (a, b, strcmp); }
2849 static int rev_cmp_name (V a, V b) { return compare_name (b, a); }
2850 static int rev_str_name (V a, V b) { return compstr_name (b, a); }
2851
2852 /* Compare file extensions.  Files with no extension are `smallest'.
2853    If extensions are the same, compare by filenames instead.  */
2854
2855 static inline int
2856 cmp_extension (struct fileinfo const *a, struct fileinfo const *b,
2857                int (*cmp) (char const *, char const *))
2858 {
2859   char const *base1 = strrchr (a->name, '.');
2860   char const *base2 = strrchr (b->name, '.');
2861   int diff = cmp (base1 ? base1 : "", base2 ? base2 : "");
2862   return diff ? diff : cmp (a->name, b->name);
2863 }
2864 static int compare_extension (V a, V b) { return cmp_extension (a, b, xstrcoll); }
2865 static int compstr_extension (V a, V b) { return cmp_extension (a, b, strcmp); }
2866 static int rev_cmp_extension (V a, V b) { return compare_extension (b, a); }
2867 static int rev_str_extension (V a, V b) { return compstr_extension (b, a); }
2868
2869 /* Sort the files now in the table.  */
2870
2871 static void
2872 sort_files (void)
2873 {
2874   int (*func) (V, V);
2875
2876   /* Try strcoll.  If it fails, fall back on strcmp.  We can't safely
2877      ignore strcoll failures, as a failing strcoll might be a
2878      comparison function that is not a total order, and if we ignored
2879      the failure this might cause qsort to dump core.  */
2880
2881   if (! setjmp (failed_strcoll))
2882     {
2883       switch (sort_type)
2884         {
2885         case sort_none:
2886           return;
2887         case sort_time:
2888           switch (time_type)
2889             {
2890             case time_ctime:
2891               func = sort_reverse ? rev_cmp_ctime : compare_ctime;
2892               break;
2893             case time_mtime:
2894               func = sort_reverse ? rev_cmp_mtime : compare_mtime;
2895               break;
2896             case time_atime:
2897               func = sort_reverse ? rev_cmp_atime : compare_atime;
2898               break;
2899             default:
2900               abort ();
2901             }
2902           break;
2903         case sort_name:
2904           func = sort_reverse ? rev_cmp_name : compare_name;
2905           break;
2906         case sort_extension:
2907           func = sort_reverse ? rev_cmp_extension : compare_extension;
2908           break;
2909         case sort_size:
2910           func = sort_reverse ? rev_cmp_size : compare_size;
2911           break;
2912         case sort_version:
2913           func = sort_reverse ? rev_cmp_version : compare_version;
2914           break;
2915         default:
2916           abort ();
2917         }
2918     }
2919   else
2920     {
2921       switch (sort_type)
2922         {
2923         case sort_time:
2924           switch (time_type)
2925             {
2926             case time_ctime:
2927               func = sort_reverse ? rev_str_ctime : compstr_ctime;
2928               break;
2929             case time_mtime:
2930               func = sort_reverse ? rev_str_mtime : compstr_mtime;
2931               break;
2932             case time_atime:
2933               func = sort_reverse ? rev_str_atime : compstr_atime;
2934               break;
2935             default:
2936               abort ();
2937             }
2938           break;
2939         case sort_name:
2940           func = sort_reverse ? rev_str_name : compstr_name;
2941           break;
2942         case sort_extension:
2943           func = sort_reverse ? rev_str_extension : compstr_extension;
2944           break;
2945         case sort_size:
2946           func = sort_reverse ? rev_str_size : compstr_size;
2947           break;
2948         default:
2949           abort ();
2950         }
2951     }
2952
2953   qsort (files, files_index, sizeof (struct fileinfo), func);
2954 }
2955
2956 /* List all the files now in the table.  */
2957
2958 static void
2959 print_current_files (void)
2960 {
2961   register size_t i;
2962
2963   switch (format)
2964     {
2965     case one_per_line:
2966       for (i = 0; i < files_index; i++)
2967         {
2968           print_file_name_and_frills (files + i);
2969           putchar ('\n');
2970         }
2971       break;
2972
2973     case many_per_line:
2974       print_many_per_line ();
2975       break;
2976
2977     case horizontal:
2978       print_horizontal ();
2979       break;
2980
2981     case with_commas:
2982       print_with_commas ();
2983       break;
2984
2985     case long_format:
2986       for (i = 0; i < files_index; i++)
2987         {
2988           print_long_format (files + i);
2989           DIRED_PUTCHAR ('\n');
2990         }
2991       break;
2992     }
2993 }
2994
2995 /* Return the expected number of columns in a long-format time stamp,
2996    or zero if it cannot be calculated.  */
2997
2998 static int
2999 long_time_expected_width (void)
3000 {
3001   static int width = -1;
3002
3003   if (width < 0)
3004     {
3005       time_t epoch = 0;
3006       struct tm const *tm = localtime (&epoch);
3007       char const *fmt = long_time_format[0];
3008       char initbuf[100];
3009       char *buf = initbuf;
3010       size_t bufsize = sizeof initbuf;
3011       size_t len;
3012
3013       for (;;)
3014         {
3015           *buf = '\1';
3016           len = nstrftime (buf, bufsize, fmt, tm, 0, 0);
3017           if (len || ! *buf)
3018             break;
3019           buf = alloca (bufsize *= 2);
3020         }
3021
3022       width = mbsnwidth (buf, len, 0);
3023       if (width < 0)
3024         width = 0;
3025     }
3026
3027   return width;
3028 }
3029
3030 /* Get the current time.  */
3031
3032 static void
3033 get_current_time (void)
3034 {
3035 #if HAVE_CLOCK_GETTIME && defined CLOCK_REALTIME
3036   {
3037     struct timespec timespec;
3038     if (clock_gettime (CLOCK_REALTIME, &timespec) == 0)
3039       {
3040         current_time = timespec.tv_sec;
3041         current_time_ns = timespec.tv_nsec;
3042         return;
3043       }
3044   }
3045 #endif
3046
3047   /* The clock does not have nanosecond resolution, so get the maximum
3048      possible value for the current time that is consistent with the
3049      reported clock.  That way, files are not considered to be in the
3050      future merely because their time stamps have higher resolution
3051      than the clock resolution.  */
3052
3053 #if HAVE_GETTIMEOFDAY
3054   {
3055     struct timeval timeval;
3056     if (gettimeofday (&timeval, NULL) == 0)
3057       {
3058         current_time = timeval.tv_sec;
3059         current_time_ns = timeval.tv_usec * 1000 + 999;
3060         return;
3061       }
3062   }
3063 #endif
3064
3065   current_time = time (NULL);
3066   current_time_ns = 999999999;
3067 }
3068
3069 /* Print the user or group name NAME, with numeric id ID, using a
3070    print width of WIDTH columns.  */
3071
3072 static void
3073 format_user_or_group (char const *name, unsigned long int id, int width)
3074 {
3075   size_t len;
3076
3077   if (name)
3078     {
3079       int width_gap = width - mbswidth (name, 0);
3080       int pad = MAX (0, width_gap);
3081       fputs (name, stdout);
3082       len = strlen (name) + pad;
3083
3084       do
3085         putchar (' ');
3086       while (pad--);
3087     }
3088   else
3089     {
3090       printf ("%*lu ", width, id);
3091       len = width;
3092     }
3093
3094   dired_pos += len + 1;
3095 }
3096
3097 /* Print the name or id of the user with id U, using a print width of
3098    WIDTH.  */
3099
3100 static void
3101 format_user (uid_t u, int width)
3102 {
3103   format_user_or_group (numeric_ids ? NULL : getuser (u), u, width);
3104 }
3105
3106 /* Likewise, for groups.  */
3107
3108 static void
3109 format_group (gid_t g, int width)
3110 {
3111   format_user_or_group (numeric_ids ? NULL : getgroup (g), g, width);
3112 }
3113
3114 /* Return the number of columns that format_user_or_group will print.  */
3115
3116 static int
3117 format_user_or_group_width (char const *name, unsigned long int id)
3118 {
3119   if (name)
3120     {
3121       int len = mbswidth (name, 0);
3122       return MAX (0, len);
3123     }
3124   else
3125     {
3126       char buf[INT_BUFSIZE_BOUND (unsigned long int)];
3127       sprintf (buf, "%lu", id);
3128       return strlen (buf);
3129     }
3130 }
3131
3132 /* Return the number of columns that format_user will print.  */
3133
3134 static int
3135 format_user_width (uid_t u)
3136 {
3137   return format_user_or_group_width (numeric_ids ? NULL : getuser (u), u);
3138 }
3139
3140 /* Likewise, for groups.  */
3141
3142 static int
3143 format_group_width (gid_t g)
3144 {
3145   return format_user_or_group_width (numeric_ids ? NULL : getgroup (g), g);
3146 }
3147
3148
3149 /* Print information about F in long format.  */
3150
3151 static void
3152 print_long_format (const struct fileinfo *f)
3153 {
3154   char modebuf[12];
3155   char init_bigbuf
3156     [LONGEST_HUMAN_READABLE + 1         /* inode */
3157      + LONGEST_HUMAN_READABLE + 1       /* size in blocks */
3158      + sizeof (modebuf) - 1 + 1         /* mode string */
3159      + INT_BUFSIZE_BOUND (uintmax_t)    /* st_nlink */
3160      + LONGEST_HUMAN_READABLE + 2       /* major device number */
3161      + LONGEST_HUMAN_READABLE + 1       /* minor device number */
3162      + 35 + 1   /* usual length of time/date -- may be longer; see below */
3163      ];
3164   char *buf = init_bigbuf;
3165   size_t bufsize = sizeof (init_bigbuf);
3166   size_t s;
3167   char *p;
3168   time_t when;
3169   int when_ns IF_LINT (= 0);
3170   struct tm *when_local;
3171
3172   /* Compute mode string.  On most systems, it's based on st_mode.
3173      On systems with migration (via the stat.st_dm_mode field), use
3174      the file's migrated status.  */
3175   mode_string (ST_DM_MODE (f->stat), modebuf);
3176
3177   modebuf[10] = (FILE_HAS_ACL (f) ? '+' : ' ');
3178   modebuf[11] = '\0';
3179
3180   switch (time_type)
3181     {
3182     case time_ctime:
3183       when = f->stat.st_ctime;
3184       when_ns = TIMESPEC_NS (f->stat.st_ctim);
3185       break;
3186     case time_mtime:
3187       when = f->stat.st_mtime;
3188       when_ns = TIMESPEC_NS (f->stat.st_mtim);
3189       break;
3190     case time_atime:
3191       when = f->stat.st_atime;
3192       when_ns = TIMESPEC_NS (f->stat.st_atim);
3193       break;
3194     }
3195
3196   p = buf;
3197
3198   if (print_inode)
3199     {
3200       char hbuf[INT_BUFSIZE_BOUND (uintmax_t)];
3201       sprintf (p, "%*s ", inode_number_width,
3202                umaxtostr (f->stat.st_ino, hbuf));
3203       p += inode_number_width + 1;
3204     }
3205
3206   if (print_block_size)
3207     {
3208       char hbuf[LONGEST_HUMAN_READABLE + 1];
3209       char const *blocks =
3210         human_readable (ST_NBLOCKS (f->stat), hbuf, human_output_opts,
3211                         ST_NBLOCKSIZE, output_block_size);
3212       int pad;
3213       for (pad = block_size_width - mbswidth (blocks, 0); 0 < pad; pad--)
3214         *p++ = ' ';
3215       while ((*p++ = *blocks++))
3216         continue;
3217       p[-1] = ' ';
3218     }
3219
3220   /* The last byte of the mode string is the POSIX
3221      "optional alternate access method flag".  */
3222   {
3223     char hbuf[INT_BUFSIZE_BOUND (uintmax_t)];
3224     sprintf (p, "%s %*s ", modebuf, nlink_width,
3225              umaxtostr (f->stat.st_nlink, hbuf));
3226   }
3227   p += sizeof modebuf + nlink_width + 1;
3228
3229   DIRED_INDENT ();
3230
3231   if (print_owner | print_group | print_author)
3232     {
3233       DIRED_FPUTS (buf, stdout, p - buf);
3234
3235       if (print_owner)
3236         format_user (f->stat.st_uid, owner_width);
3237
3238       if (print_group)
3239         format_group (f->stat.st_gid, group_width);
3240
3241       if (print_author)
3242         format_user (f->stat.st_author, author_width);
3243
3244       p = buf;
3245     }
3246
3247   if (S_ISCHR (f->stat.st_mode) || S_ISBLK (f->stat.st_mode))
3248     {
3249       char majorbuf[INT_BUFSIZE_BOUND (uintmax_t)];
3250       char minorbuf[INT_BUFSIZE_BOUND (uintmax_t)];
3251       int blanks_width = (file_size_width
3252                           - (major_device_number_width + 2
3253                              + minor_device_number_width));
3254       sprintf (p, "%*s, %*s ",
3255                major_device_number_width + MAX (0, blanks_width),
3256                umaxtostr (major (f->stat.st_rdev), majorbuf),
3257                minor_device_number_width,
3258                umaxtostr (minor (f->stat.st_rdev), minorbuf));
3259       p += file_size_width + 1;
3260     }
3261   else
3262     {
3263       char hbuf[LONGEST_HUMAN_READABLE + 1];
3264       char const *size =
3265         human_readable (unsigned_file_size (f->stat.st_size),
3266                         hbuf, human_output_opts, 1, file_output_block_size);
3267       int pad;
3268       for (pad = file_size_width - mbswidth (size, 0); 0 < pad; pad--)
3269         *p++ = ' ';
3270       while ((*p++ = *size++))
3271         continue;
3272       p[-1] = ' ';
3273     }
3274
3275   if ((when_local = localtime (&when)))
3276     {
3277       time_t six_months_ago;
3278       bool recent;
3279       char const *fmt;
3280
3281       /* If the file appears to be in the future, update the current
3282          time, in case the file happens to have been modified since
3283          the last time we checked the clock.  */
3284       if (current_time < when
3285           || (current_time == when && current_time_ns < when_ns))
3286         {
3287           /* Note that get_current_time calls gettimeofday which, on some non-
3288              compliant systems, clobbers the buffer used for localtime's result.
3289              But it's ok here, because we use a gettimeofday wrapper that
3290              saves and restores the buffer around the gettimeofday call.  */
3291           get_current_time ();
3292         }
3293
3294       /* Consider a time to be recent if it is within the past six
3295          months.  A Gregorian year has 365.2425 * 24 * 60 * 60 ==
3296          31556952 seconds on the average.  Write this value as an
3297          integer constant to avoid floating point hassles.  */
3298       six_months_ago = current_time - 31556952 / 2;
3299       recent = (six_months_ago <= when
3300                 && (when < current_time
3301                     || (when == current_time && when_ns <= current_time_ns)));
3302       fmt = long_time_format[recent];
3303
3304       for (;;)
3305         {
3306           char *newbuf;
3307           *p = '\1';
3308           s = nstrftime (p, buf + bufsize - p - 1, fmt,
3309                          when_local, 0, when_ns);
3310           if (s || ! *p)
3311             break;
3312           newbuf = alloca (bufsize *= 2);
3313           memcpy (newbuf, buf, p - buf);
3314           p = newbuf + (p - buf);
3315           buf = newbuf;
3316         }
3317
3318       p += s;
3319       *p++ = ' ';
3320
3321       /* NUL-terminate the string -- fputs (via DIRED_FPUTS) requires it.  */
3322       *p = '\0';
3323     }
3324   else
3325     {
3326       /* The time cannot be represented as a local time;
3327          print it as a huge integer number of seconds.  */
3328       char hbuf[INT_BUFSIZE_BOUND (intmax_t)];
3329       sprintf (p, "%*s ", long_time_expected_width (),
3330                (TYPE_SIGNED (time_t)
3331                 ? imaxtostr (when, hbuf)
3332                 : umaxtostr (when, hbuf)));
3333       p += strlen (p);
3334     }
3335
3336   DIRED_FPUTS (buf, stdout, p - buf);
3337   print_name_with_quoting (f->name, FILE_OR_LINK_MODE (f), f->linkok,
3338                            &dired_obstack);
3339
3340   if (f->filetype == symbolic_link)
3341     {
3342       if (f->linkname)
3343         {
3344           DIRED_FPUTS_LITERAL (" -> ", stdout);
3345           print_name_with_quoting (f->linkname, f->linkmode, f->linkok - 1,
3346                                    NULL);
3347           if (indicator_style != none)
3348             print_type_indicator (f->linkmode);
3349         }
3350     }
3351   else if (indicator_style != none)
3352     print_type_indicator (f->stat.st_mode);
3353 }
3354
3355 /* Output to OUT a quoted representation of the file name NAME,
3356    using OPTIONS to control quoting.  Produce no output if OUT is NULL.
3357    Store the number of screen columns occupied by NAME's quoted
3358    representation into WIDTH, if non-NULL.  Return the number of bytes
3359    produced.  */
3360
3361 static size_t
3362 quote_name (FILE *out, const char *name, struct quoting_options const *options,
3363             size_t *width)
3364 {
3365   char smallbuf[BUFSIZ];
3366   size_t len = quotearg_buffer (smallbuf, sizeof smallbuf, name, -1, options);
3367   char *buf;
3368   size_t displayed_width IF_LINT (= 0);
3369
3370   if (len < sizeof smallbuf)
3371     buf = smallbuf;
3372   else
3373     {
3374       buf = alloca (len + 1);
3375       quotearg_buffer (buf, len + 1, name, -1, options);
3376     }
3377
3378   if (qmark_funny_chars)
3379     {
3380 #if HAVE_MBRTOWC
3381       if (MB_CUR_MAX > 1)
3382         {
3383           char const *p = buf;
3384           char const *plimit = buf + len;
3385           char *q = buf;
3386           displayed_width = 0;
3387
3388           while (p < plimit)
3389             switch (*p)
3390               {
3391                 case ' ': case '!': case '"': case '#': case '%':
3392                 case '&': case '\'': case '(': case ')': case '*':
3393                 case '+': case ',': case '-': case '.': case '/':
3394                 case '0': case '1': case '2': case '3': case '4':
3395                 case '5': case '6': case '7': case '8': case '9':
3396                 case ':': case ';': case '<': case '=': case '>':
3397                 case '?':
3398                 case 'A': case 'B': case 'C': case 'D': case 'E':
3399                 case 'F': case 'G': case 'H': case 'I': case 'J':
3400                 case 'K': case 'L': case 'M': case 'N': case 'O':
3401                 case 'P': case 'Q': case 'R': case 'S': case 'T':
3402                 case 'U': case 'V': case 'W': case 'X': case 'Y':
3403                 case 'Z':
3404                 case '[': case '\\': case ']': case '^': case '_':
3405                 case 'a': case 'b': case 'c': case 'd': case 'e':
3406                 case 'f': case 'g': case 'h': case 'i': case 'j':
3407                 case 'k': case 'l': case 'm': case 'n': case 'o':
3408                 case 'p': case 'q': case 'r': case 's': case 't':
3409                 case 'u': case 'v': case 'w': case 'x': case 'y':
3410                 case 'z': case '{': case '|': case '}': case '~':
3411                   /* These characters are printable ASCII characters.  */
3412                   *q++ = *p++;
3413                   displayed_width += 1;
3414                   break;
3415                 default:
3416                   /* If we have a multibyte sequence, copy it until we
3417                      reach its end, replacing each non-printable multibyte
3418                      character with a single question mark.  */
3419                   {
3420                     mbstate_t mbstate;
3421                     memset (&mbstate, 0, sizeof mbstate);
3422                     do
3423                       {
3424                         wchar_t wc;
3425                         size_t bytes;
3426                         int w;
3427
3428                         bytes = mbrtowc (&wc, p, plimit - p, &mbstate);
3429
3430                         if (bytes == (size_t) -1)
3431                           {
3432                             /* An invalid multibyte sequence was
3433                                encountered.  Skip one input byte, and
3434                                put a question mark.  */
3435                             p++;
3436                             *q++ = '?';
3437                             displayed_width += 1;
3438                             break;
3439                           }
3440
3441                         if (bytes == (size_t) -2)
3442                           {
3443                             /* An incomplete multibyte character
3444                                at the end.  Replace it entirely with
3445                                a question mark.  */
3446                             p = plimit;
3447                             *q++ = '?';
3448                             displayed_width += 1;
3449                             break;
3450                           }
3451
3452                         if (bytes == 0)
3453                           /* A null wide character was encountered.  */
3454                           bytes = 1;
3455
3456                         w = wcwidth (wc);
3457                         if (w >= 0)
3458                           {
3459                             /* A printable multibyte character.
3460                                Keep it.  */
3461                             for (; bytes > 0; --bytes)
3462                               *q++ = *p++;
3463                             displayed_width += w;
3464                           }
3465                         else
3466                           {
3467                             /* An unprintable multibyte character.
3468                                Replace it entirely with a question
3469                                mark.  */
3470                             p += bytes;
3471                             *q++ = '?';
3472                             displayed_width += 1;
3473                           }
3474                       }
3475                     while (! mbsinit (&mbstate));
3476                   }
3477                   break;
3478               }
3479
3480           /* The buffer may have shrunk.  */
3481           len = q - buf;
3482         }
3483       else
3484 #endif
3485         {
3486           char *p = buf;
3487           char const *plimit = buf + len;
3488
3489           while (p < plimit)
3490             {
3491               if (! ISPRINT (to_uchar (*p)))
3492                 *p = '?';
3493               p++;
3494             }
3495           displayed_width = len;
3496         }
3497     }
3498   else if (width != NULL)
3499     {
3500 #if HAVE_MBRTOWC
3501       if (MB_CUR_MAX > 1)
3502         displayed_width = mbsnwidth (buf, len, 0);
3503       else
3504 #endif
3505         {
3506           char const *p = buf;
3507           char const *plimit = buf + len;
3508
3509           displayed_width = 0;
3510           while (p < plimit)
3511             {
3512               if (ISPRINT (to_uchar (*p)))
3513                 displayed_width++;
3514               p++;
3515             }
3516         }
3517     }
3518
3519   if (out != NULL)
3520     fwrite (buf, 1, len, out);
3521   if (width != NULL)
3522     *width = displayed_width;
3523   return len;
3524 }
3525
3526 static void
3527 print_name_with_quoting (const char *p, mode_t mode, int linkok,
3528                          struct obstack *stack)
3529 {
3530   if (print_with_color)
3531     print_color_indicator (p, mode, linkok);
3532
3533   if (stack)
3534     PUSH_CURRENT_DIRED_POS (stack);
3535
3536   dired_pos += quote_name (stdout, p, filename_quoting_options, NULL);
3537
3538   if (stack)
3539     PUSH_CURRENT_DIRED_POS (stack);
3540
3541   if (print_with_color)
3542     {
3543       process_signals ();
3544       prep_non_filename_text ();
3545     }
3546 }
3547
3548 static void
3549 prep_non_filename_text (void)
3550 {
3551   if (color_indicator[C_END].string != NULL)
3552     put_indicator (&color_indicator[C_END]);
3553   else
3554     {
3555       put_indicator (&color_indicator[C_LEFT]);
3556       put_indicator (&color_indicator[C_NORM]);
3557       put_indicator (&color_indicator[C_RIGHT]);
3558     }
3559 }
3560
3561 /* Print the file name of `f' with appropriate quoting.
3562    Also print file size, inode number, and filetype indicator character,
3563    as requested by switches.  */
3564
3565 static void
3566 print_file_name_and_frills (const struct fileinfo *f)
3567 {
3568   char buf[MAX (LONGEST_HUMAN_READABLE + 1, INT_BUFSIZE_BOUND (uintmax_t))];
3569
3570   if (print_inode)
3571     printf ("%*s ", format == with_commas ? 0 : inode_number_width,
3572             umaxtostr (f->stat.st_ino, buf));
3573
3574   if (print_block_size)
3575     printf ("%*s ", format == with_commas ? 0 : block_size_width,
3576             human_readable (ST_NBLOCKS (f->stat), buf, human_output_opts,
3577                             ST_NBLOCKSIZE, output_block_size));
3578
3579   print_name_with_quoting (f->name, FILE_OR_LINK_MODE (f), f->linkok, NULL);
3580
3581   if (indicator_style != none)
3582     print_type_indicator (f->stat.st_mode);
3583 }
3584
3585 static void
3586 print_type_indicator (mode_t mode)
3587 {
3588   char c;
3589
3590   if (S_ISREG (mode))
3591     {
3592       if (indicator_style == classify && (mode & S_IXUGO))
3593         c ='*';
3594       else
3595         c = 0;
3596     }
3597   else
3598     {
3599       if (S_ISDIR (mode))
3600         c = '/';
3601       else if (S_ISLNK (mode))
3602         c = '@';
3603       else if (S_ISFIFO (mode))
3604         c = '|';
3605       else if (S_ISSOCK (mode))
3606         c = '=';
3607       else if (S_ISDOOR (mode))
3608         c = '>';
3609       else
3610         c = 0;
3611     }
3612
3613   if (c)
3614     DIRED_PUTCHAR (c);
3615 }
3616
3617 static void
3618 print_color_indicator (const char *name, mode_t mode, int linkok)
3619 {
3620   int type = C_FILE;
3621   struct color_ext_type *ext;   /* Color extension */
3622   size_t len;                   /* Length of name */
3623
3624   /* Is this a nonexistent file?  If so, linkok == -1.  */
3625
3626   if (linkok == -1 && color_indicator[C_MISSING].string != NULL)
3627     {
3628       ext = NULL;
3629       type = C_MISSING;
3630     }
3631   else
3632     {
3633       if (S_ISDIR (mode))
3634         type = C_DIR;
3635       else if (S_ISLNK (mode))
3636         type = ((!linkok && color_indicator[C_ORPHAN].string)
3637                 ? C_ORPHAN : C_LINK);
3638       else if (S_ISFIFO (mode))
3639         type = C_FIFO;
3640       else if (S_ISSOCK (mode))
3641         type = C_SOCK;
3642       else if (S_ISBLK (mode))
3643         type = C_BLK;
3644       else if (S_ISCHR (mode))
3645         type = C_CHR;
3646       else if (S_ISDOOR (mode))
3647         type = C_DOOR;
3648
3649       if (type == C_FILE && (mode & S_IXUGO) != 0)
3650         type = C_EXEC;
3651
3652       /* Check the file's suffix only if still classified as C_FILE.  */
3653       ext = NULL;
3654       if (type == C_FILE)
3655         {
3656           /* Test if NAME has a recognized suffix.  */
3657
3658           len = strlen (name);
3659           name += len;          /* Pointer to final \0.  */
3660           for (ext = color_ext_list; ext != NULL; ext = ext->next)
3661             {
3662               if (ext->ext.len <= len
3663                   && strncmp (name - ext->ext.len, ext->ext.string,
3664                               ext->ext.len) == 0)
3665                 break;
3666             }
3667         }
3668     }
3669
3670   put_indicator (&color_indicator[C_LEFT]);
3671   put_indicator (ext ? &(ext->seq) : &color_indicator[type]);
3672   put_indicator (&color_indicator[C_RIGHT]);
3673 }
3674
3675 /* Output a color indicator (which may contain nulls).  */
3676 static void
3677 put_indicator (const struct bin_str *ind)
3678 {
3679   register size_t i;
3680   register const char *p;
3681
3682   p = ind->string;
3683
3684   for (i = ind->len; i != 0; --i)
3685     putchar (*(p++));
3686 }
3687
3688 static size_t
3689 length_of_file_name_and_frills (const struct fileinfo *f)
3690 {
3691   register size_t len = 0;
3692   size_t name_width;
3693   char buf[MAX (LONGEST_HUMAN_READABLE + 1, INT_BUFSIZE_BOUND (uintmax_t))];
3694
3695   if (print_inode)
3696     len += 1 + (format == with_commas
3697                 ? strlen (umaxtostr (f->stat.st_ino, buf))
3698                 : inode_number_width);
3699
3700   if (print_block_size)
3701     len += 1 + (format == with_commas
3702                 ? strlen (human_readable (ST_NBLOCKS (f->stat), buf,
3703                                           human_output_opts, ST_NBLOCKSIZE,
3704                                           output_block_size))
3705                 : block_size_width);
3706
3707   quote_name (NULL, f->name, filename_quoting_options, &name_width);
3708   len += name_width;
3709
3710   if (indicator_style != none)
3711     {
3712       mode_t filetype = f->stat.st_mode;
3713
3714       if (S_ISREG (filetype))
3715         {
3716           if (indicator_style == classify
3717               && (f->stat.st_mode & S_IXUGO))
3718             len += 1;
3719         }
3720       else if (S_ISDIR (filetype)
3721                || S_ISLNK (filetype)
3722                || S_ISFIFO (filetype)
3723                || S_ISSOCK (filetype)
3724                || S_ISDOOR (filetype)
3725                )
3726         len += 1;
3727     }
3728
3729   return len;
3730 }
3731
3732 static void
3733 print_many_per_line (void)
3734 {
3735   size_t row;                   /* Current row.  */
3736   size_t cols = calculate_columns (true);
3737   struct column_info const *line_fmt = &column_info[cols - 1];
3738
3739   /* Calculate the number of rows that will be in each column except possibly
3740      for a short column on the right.  */
3741   size_t rows = files_index / cols + (files_index % cols != 0);
3742
3743   for (row = 0; row < rows; row++)
3744     {
3745       size_t col = 0;
3746       size_t filesno = row;
3747       size_t pos = 0;
3748
3749       /* Print the next row.  */
3750       while (1)
3751         {
3752           size_t name_length = length_of_file_name_and_frills (files + filesno);
3753           size_t max_name_length = line_fmt->col_arr[col++];
3754           print_file_name_and_frills (files + filesno);
3755
3756           filesno += rows;
3757           if (filesno >= files_index)
3758             break;
3759
3760           indent (pos + name_length, pos + max_name_length);
3761           pos += max_name_length;
3762         }
3763       putchar ('\n');
3764     }
3765 }
3766
3767 static void
3768 print_horizontal (void)
3769 {
3770   size_t filesno;
3771   size_t pos = 0;
3772   size_t cols = calculate_columns (false);
3773   struct column_info const *line_fmt = &column_info[cols - 1];
3774   size_t name_length = length_of_file_name_and_frills (files);
3775   size_t max_name_length = line_fmt->col_arr[0];
3776
3777   /* Print first entry.  */
3778   print_file_name_and_frills (files);
3779
3780   /* Now the rest.  */
3781   for (filesno = 1; filesno < files_index; ++filesno)
3782     {
3783       size_t col = filesno % cols;
3784
3785       if (col == 0)
3786         {
3787           putchar ('\n');
3788           pos = 0;
3789         }
3790       else
3791         {
3792           indent (pos + name_length, pos + max_name_length);
3793           pos += max_name_length;
3794         }
3795
3796       print_file_name_and_frills (files + filesno);
3797
3798       name_length = length_of_file_name_and_frills (files + filesno);
3799       max_name_length = line_fmt->col_arr[col];
3800     }
3801   putchar ('\n');
3802 }
3803
3804 static void
3805 print_with_commas (void)
3806 {
3807   size_t filesno;
3808   size_t pos = 0;
3809
3810   for (filesno = 0; filesno < files_index; filesno++)
3811     {
3812       size_t len = length_of_file_name_and_frills (files + filesno);
3813
3814       if (filesno != 0)
3815         {
3816           char separator;
3817
3818           if (pos + len + 2 < line_length)
3819             {
3820               pos += 2;
3821               separator = ' ';
3822             }
3823           else
3824             {
3825               pos = 0;
3826               separator = '\n';
3827             }
3828
3829           putchar (',');
3830           putchar (separator);
3831         }
3832
3833       print_file_name_and_frills (files + filesno);
3834       pos += len;
3835     }
3836   putchar ('\n');
3837 }
3838
3839 /* Assuming cursor is at position FROM, indent up to position TO.
3840    Use a TAB character instead of two or more spaces whenever possible.  */
3841
3842 static void
3843 indent (size_t from, size_t to)
3844 {
3845   while (from < to)
3846     {
3847       if (tabsize != 0 && to / tabsize > (from + 1) / tabsize)
3848         {
3849           putchar ('\t');
3850           from += tabsize - from % tabsize;
3851         }
3852       else
3853         {
3854           putchar (' ');
3855           from++;
3856         }
3857     }
3858 }
3859
3860 /* Put DIRNAME/NAME into DEST, handling `.' and `/' properly.  */
3861 /* FIXME: maybe remove this function someday.  See about using a
3862    non-malloc'ing version of path_concat.  */
3863
3864 static void
3865 attach (char *dest, const char *dirname, const char *name)
3866 {
3867   const char *dirnamep = dirname;
3868
3869   /* Copy dirname if it is not ".".  */
3870   if (dirname[0] != '.' || dirname[1] != 0)
3871     {
3872       while (*dirnamep)
3873         *dest++ = *dirnamep++;
3874       /* Add '/' if `dirname' doesn't already end with it.  */
3875       if (dirnamep > dirname && dirnamep[-1] != '/')
3876         *dest++ = '/';
3877     }
3878   while (*name)
3879     *dest++ = *name++;
3880   *dest = 0;
3881 }
3882
3883 /* Allocate enough column info suitable for the current number of
3884    files and display columns, and initialize the info to represent the
3885    narrowest possible columns.  */
3886
3887 static void
3888 init_column_info (void)
3889 {
3890   size_t i;
3891   size_t max_cols = MIN (max_idx, files_index);
3892
3893   /* Currently allocated columns in column_info.  */
3894   static size_t column_info_alloc;
3895
3896   if (column_info_alloc < max_cols)
3897     {
3898       size_t new_column_info_alloc;
3899       size_t *p;
3900
3901       if (max_cols < max_idx / 2)
3902         {
3903           /* The number of columns is far less than the display width
3904              allows.  Grow the allocation, but only so that it's
3905              double the current requirements.  If the display is
3906              extremely wide, this avoids allocating a lot of memory
3907              that is never needed.  */
3908           column_info = xnrealloc (column_info, max_cols,
3909                                    2 * sizeof *column_info);
3910           new_column_info_alloc = 2 * max_cols;
3911         }
3912       else
3913         {
3914           column_info = xnrealloc (column_info, max_idx, sizeof *column_info);
3915           new_column_info_alloc = max_idx;
3916         }
3917
3918       /* Allocate the new size_t objects by computing the triangle
3919          formula n * (n + 1) / 2, except that we don't need to
3920          allocate the part of the triangle that we've already
3921          allocated.  Check for address arithmetic overflow.  */
3922       {
3923         size_t column_info_growth = new_column_info_alloc - column_info_alloc;
3924         size_t s = column_info_alloc + 1 + new_column_info_alloc;
3925         size_t t = s * column_info_growth;
3926         if (s < new_column_info_alloc || t / column_info_growth != s)
3927           xalloc_die ();
3928         p = xnmalloc (t / 2, sizeof *p);
3929       }
3930
3931       /* Grow the triangle by parceling out the cells just allocated.  */
3932       for (i = column_info_alloc; i < new_column_info_alloc; i++)
3933         {
3934           column_info[i].col_arr = p;
3935           p += i + 1;
3936         }
3937
3938       column_info_alloc = new_column_info_alloc;
3939     }
3940
3941   for (i = 0; i < max_cols; ++i)
3942     {
3943       size_t j;
3944
3945       column_info[i].valid_len = true;
3946       column_info[i].line_len = (i + 1) * MIN_COLUMN_WIDTH;
3947       for (j = 0; j <= i; ++j)
3948         column_info[i].col_arr[j] = MIN_COLUMN_WIDTH;
3949     }
3950 }
3951
3952 /* Calculate the number of columns needed to represent the current set
3953    of files in the current display width.  */
3954
3955 static size_t
3956 calculate_columns (bool by_columns)
3957 {
3958   size_t filesno;               /* Index into files.  */
3959   size_t cols;                  /* Number of files across.  */
3960
3961   /* Normally the maximum number of columns is determined by the
3962      screen width.  But if few files are available this might limit it
3963      as well.  */
3964   size_t max_cols = MIN (max_idx, files_index);
3965
3966   init_column_info ();
3967
3968   /* Compute the maximum number of possible columns.  */
3969   for (filesno = 0; filesno < files_index; ++filesno)
3970     {
3971       size_t name_length = length_of_file_name_and_frills (files + filesno);
3972       size_t i;
3973
3974       for (i = 0; i < max_cols; ++i)
3975         {
3976           if (column_info[i].valid_len)
3977             {
3978               size_t idx = (by_columns
3979                             ? filesno / ((files_index + i) / (i + 1))
3980                             : filesno % (i + 1));
3981               size_t real_length = name_length + (idx == i ? 0 : 2);
3982
3983               if (column_info[i].col_arr[idx] < real_length)
3984                 {
3985                   column_info[i].line_len += (real_length
3986                                               - column_info[i].col_arr[idx]);
3987                   column_info[i].col_arr[idx] = real_length;
3988                   column_info[i].valid_len = (column_info[i].line_len
3989                                               < line_length);
3990                 }
3991             }
3992         }
3993     }
3994
3995   /* Find maximum allowed columns.  */
3996   for (cols = max_cols; 1 < cols; --cols)
3997     {
3998       if (column_info[cols - 1].valid_len)
3999         break;
4000     }
4001
4002   return cols;
4003 }
4004
4005 void
4006 usage (int status)
4007 {
4008   if (status != EXIT_SUCCESS)
4009     fprintf (stderr, _("Try `%s --help' for more information.\n"),
4010              program_name);
4011   else
4012     {
4013       printf (_("Usage: %s [OPTION]... [FILE]...\n"), program_name);
4014       fputs (_("\
4015 List information about the FILEs (the current directory by default).\n\
4016 Sort entries alphabetically if none of -cftuSUX nor --sort.\n\
4017 \n\
4018 "), stdout);
4019       fputs (_("\
4020 Mandatory arguments to long options are mandatory for short options too.\n\
4021 "), stdout);
4022       fputs (_("\
4023   -a, --all                  do not ignore entries starting with .\n\
4024   -A, --almost-all           do not list implied . and ..\n\
4025       --author               with -l, print the author of each file\n\
4026   -b, --escape               print octal escapes for nongraphic characters\n\
4027 "), stdout);
4028       fputs (_("\
4029       --block-size=SIZE      use SIZE-byte blocks\n\
4030   -B, --ignore-backups       do not list implied entries ending with ~\n\
4031   -c                         with -lt: sort by, and show, ctime (time of last\n\
4032                                modification of file status information)\n\
4033                                with -l: show ctime and sort by name\n\
4034                                otherwise: sort by ctime\n\
4035 "), stdout);
4036       fputs (_("\
4037   -C                         list entries by columns\n\
4038       --color[=WHEN]         control whether color is used to distinguish file\n\
4039                                types.  WHEN may be `never', `always', or `auto'\n\
4040   -d, --directory            list directory entries instead of contents,\n\
4041                                and do not dereference symbolic links\n\
4042   -D, --dired                generate output designed for Emacs' dired mode\n\
4043 "), stdout);
4044       fputs (_("\
4045   -f                         do not sort, enable -aU, disable -lst\n\
4046   -F, --classify             append indicator (one of */=@|) to entries\n\
4047       --format=WORD          across -x, commas -m, horizontal -x, long -l,\n\
4048                                single-column -1, verbose -l, vertical -C\n\
4049       --full-time            like -l --time-style=full-iso\n\
4050 "), stdout);
4051       fputs (_("\
4052   -g                         like -l, but do not list owner\n\
4053   -G, --no-group             like -l, but do not list group\n\
4054   -h, --human-readable       with -l, print sizes in human readable format\n\
4055                                (e.g., 1K 234M 2G)\n\
4056       --si                   likewise, but use powers of 1000 not 1024\n\
4057   -H, --dereference-command-line\n\
4058                              follow symbolic links listed on the command line\n\
4059       --dereference-command-line-symlink-to-dir\n\
4060                              follow each command line symbolic link\n\
4061                              that points to a directory\n\
4062       --hide=PATTERN         do not list implied entries matching shell PATTERN\n\
4063                                (overridden by -a or -A)\n\
4064 "), stdout);
4065       fputs (_("\
4066       --indicator-style=WORD append indicator with style WORD to entry names:\n\
4067                                none (default), classify (-F), file-type (-p)\n\
4068   -i, --inode                with -l, print the index number of each file\n\
4069   -I, --ignore=PATTERN       do not list implied entries matching shell PATTERN\n\
4070   -k                         like --block-size=1K\n\
4071 "), stdout);
4072       fputs (_("\
4073   -l                         use a long listing format\n\
4074   -L, --dereference          when showing file information for a symbolic\n\
4075                                link, show information for the file the link\n\
4076                                references rather than for the link itself\n\
4077   -m                         fill width with a comma separated list of entries\n\
4078 "), stdout);
4079       fputs (_("\
4080   -n, --numeric-uid-gid      like -l, but list numeric UIDs and GIDs\n\
4081   -N, --literal              print raw entry names (don't treat e.g. control\n\
4082                                characters specially)\n\
4083   -o                         like -l, but do not list group information\n\
4084   -p, --file-type            append indicator (one of /=@|) to entries\n\
4085 "), stdout);
4086       fputs (_("\
4087   -q, --hide-control-chars   print ? instead of non graphic characters\n\
4088       --show-control-chars   show non graphic characters as-is (default\n\
4089                              unless program is `ls' and output is a terminal)\n\
4090   -Q, --quote-name           enclose entry names in double quotes\n\
4091       --quoting-style=WORD   use quoting style WORD for entry names:\n\
4092                                literal, locale, shell, shell-always, c, escape\n\
4093 "), stdout);
4094       fputs (_("\
4095   -r, --reverse              reverse order while sorting\n\
4096   -R, --recursive            list subdirectories recursively\n\
4097   -s, --size                 with -l, print size of each file, in blocks\n\
4098 "), stdout);
4099       fputs (_("\
4100   -S                         sort by file size\n\
4101       --sort=WORD            extension -X, none -U, size -S, time -t,\n\
4102                              version -v, status -c, time -t, atime -u,\n\
4103                              access -u, use -u\n\
4104       --time=WORD            with -l, show time as WORD instead of modification\n\
4105                              time: atime, access, use, ctime or status; use\n\
4106                              specified time as sort key if --sort=time\n\
4107 "), stdout);
4108       fputs (_("\
4109       --time-style=STYLE     with -l, show times using style STYLE:\n\
4110                              full-iso, long-iso, iso, locale, +FORMAT.\n\
4111                              FORMAT is interpreted like `date'; if FORMAT is\n\
4112                              FORMAT1<newline>FORMAT2, FORMAT1 applies to\n\
4113                              non-recent files and FORMAT2 to recent files;\n\
4114                              if STYLE is prefixed with `posix-', STYLE\n\
4115                              takes effect only outside the POSIX locale\n\
4116   -t                         sort by modification time\n\
4117   -T, --tabsize=COLS         assume tab stops at each COLS instead of 8\n\
4118 "), stdout);
4119       fputs (_("\
4120   -u                         with -lt: sort by, and show, access time\n\
4121                                with -l: show access time and sort by name\n\
4122                                otherwise: sort by access time\n\
4123   -U                         do not sort; list entries in directory order\n\
4124   -v                         sort by version\n\
4125 "), stdout);
4126       fputs (_("\
4127   -w, --width=COLS           assume screen width instead of current value\n\
4128   -x                         list entries by lines instead of by columns\n\
4129   -X                         sort alphabetically by entry extension\n\
4130   -1                         list one file per line\n\
4131 "), stdout);
4132       fputs (HELP_OPTION_DESCRIPTION, stdout);
4133       fputs (VERSION_OPTION_DESCRIPTION, stdout);
4134       fputs (_("\n\
4135 SIZE may be (or may be an integer optionally followed by) one of following:\n\
4136 kB 1000, K 1024, MB 1000*1000, M 1024*1024, and so on for G, T, P, E, Z, Y.\n\
4137 "), stdout);
4138       fputs (_("\
4139 \n\
4140 By default, color is not used to distinguish types of files.  That is\n\
4141 equivalent to using --color=none.  Using the --color option without the\n\
4142 optional WHEN argument is equivalent to using --color=always.  With\n\
4143 --color=auto, color codes are output only if standard output is connected\n\
4144 to a terminal (tty).\n\
4145 "), stdout);
4146       printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
4147     }
4148   exit (status);
4149 }