locate-dominating-file calls `stat' too eagerly

locate-dominating-file calls `stat' too eagerly

[Eli Zaretskii]

This fragment from locate-dominating-file:

      (while (and dir
                  ;; As a heuristic, we stop looking up the hierarchy of
                  ;; directories as soon as we find a directory belonging to
                  ;; another user.  This should save us from looking in
                  ;; things like /net and /afs.  This assumes that all the
                  ;; files inside a project belong to the same user.
                  (let ((prev-user user))
                    (setq user (nth 2 (file-attributes dir)))
                    (or (null prev-user) (equal user prev-user))))
        (if (setq files (and (file-directory-p dir)
                             (directory-files dir 'full regexp)))
            (throw 'found (car files))
          (if (equal dir
                     (setq dir (file-name-directory
                                (directory-file-name dir))))
              (setq dir nil))))

repeatedly calls file-directory-p, even after file-directory-p already
returned non-nil, which means that thereafter anything that
file-name-directory returns will also necessarily be a directory.
That looks like inefficiency, doesn't it?  Here's the modification I
propose:

    (let ((user nil)
          ;; Abbreviate, so as to stop when we cross ~/.
          (dir (abbreviate-file-name (file-name-as-directory file)))
          files dir-seen)
      (while (and dir
                  ;; As a heuristic, we stop looking up the hierarchy of
                  ;; directories as soon as we find a directory belonging to
                  ;; another user.  This should save us from looking in
                  ;; things like /net and /afs.  This assumes that all the
                  ;; files inside a project belong to the same user.
                  (let ((prev-user user))
                    (setq user (nth 2 (file-attributes dir)))
                    (or (null prev-user) (equal user prev-user))))
        (if (setq files (and (or dir-seen 
				 (setq dir-seen (file-directory-p dir)))
                             (directory-files dir 'full regexp)))
            (throw 'found (car files))
          (if (equal dir
                     (setq dir (file-name-directory
                                (directory-file-name dir))))
              (setq dir nil))))

Does anyone see any problems with that, on any platform?

Re: locate-dominating-file calls `stat' too eagerly

[Stefan Monnier]

> This fragment from locate-dominating-file:
>       (while (and dir
>                   ;; As a heuristic, we stop looking up the hierarchy of
>                   ;; directories as soon as we find a directory belonging to
>                   ;; another user.  This should save us from looking in
>                   ;; things like /net and /afs.  This assumes that all the
>                   ;; files inside a project belong to the same user.
>                   (let ((prev-user user))
>                     (setq user (nth 2 (file-attributes dir)))
>                     (or (null prev-user) (equal user prev-user))))
>         (if (setq files (and (file-directory-p dir)
>                              (directory-files dir 'full regexp)))
>             (throw 'found (car files))
>           (if (equal dir
>                      (setq dir (file-name-directory
>                                 (directory-file-name dir))))
>               (setq dir nil))))

> repeatedly calls file-directory-p, even after file-directory-p already
> returned non-nil, which means that thereafter anything that
> file-name-directory returns will also necessarily be a directory.
> That looks like inefficiency, doesn't it?  Here's the modification I
> propose:

Wouldn't it be simpler to wrap the `directroy-files' call inside
a condition-case and drop the file-directory-p altogether?


        Stefan

Re: locate-dominating-file calls `stat' too eagerly

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Mon, 29 Sep 2008 10:06:54 -0400
> 
> Wouldn't it be simpler to wrap the `directroy-files' call inside
> a condition-case and drop the file-directory-p altogether?

That would work as well, but I'm not sure about the ``simpler'' part.
The code is already pretty convoluted, and I'm not sure why.  All it
needs to do is (1) to find an existing parent directory of its
argument FILE by chopping directories from the end until it finds an
existing one, and (2) go up the tree of existing directories until it
finds one whose owner is different.  This looks like 2 separate loops
to me, but the code for some reason insists on doing it in a single
loop.

How about this:

(defun locate-dominating-file (file regexp)
  "Look up the directory hierarchy from FILE for a file matching REGEXP."
  ;; If FILE does not exist, find its parent directory that does.
  (or (file-exists-p file)
      (while (and file (not (file-directory-p file)))
        (setq file (file-name-directory (directory-file-name file)))))
  (catch 'found
    (let ((user (nth 2 (file-attributes file)))
          ;; Abbreviate, so as to stop when we cross ~/.
          (dir (abbreviate-file-name (file-name-as-directory file)))
          files)
      (while (and dir
                  ;; As a heuristic, we stop looking up the hierarchy of
                  ;; directories as soon as we find a directory belonging to
                  ;; another user.  This should save us from looking in
                  ;; things like /net and /afs.  This assumes that all the
                  ;; files inside a project belong to the same user.
                  (let ((prev-user user))
                    (setq user (nth 2 (file-attributes dir)))
                    (equal user prev-user)))
        (if (setq files (directory-files dir 'full regexp))
            (throw 'found (car files))
          (if (equal dir
                     (setq dir (file-name-directory
                                (directory-file-name dir))))
              (setq dir nil))))
      nil)))

And btw, won't the user test cover the case of crossing ~/ as well?
If so, we don't need to abbreviate-file-name, which then incurs
further overhead inside expand-file-name.

Re: locate-dominating-file calls `stat' too eagerly

[Stefan Monnier]

> That would work as well, but I'm not sure about the ``simpler'' part.

It's definitely a simpler change, which means it's probably safer.

> The code is already pretty convoluted, and I'm not sure why.  All it
> needs to do is (1) to find an existing parent directory of its
> argument FILE by chopping directories from the end until it finds an
> existing one, and (2) go up the tree of existing directories until it
> finds one whose owner is different.  This looks like 2 separate loops
> to me, but the code for some reason insists on doing it in a single
> loop.

I think it's mostly a historical accident, but it's also so that both
loops get the other's fixes.

> How about this:

> (defun locate-dominating-file (file regexp)
>   "Look up the directory hierarchy from FILE for a file matching REGEXP."
>   ;; If FILE does not exist, find its parent directory that does.
>   (or (file-exists-p file)
>       (while (and file (not (file-directory-p file)))
>         (setq file (file-name-directory (directory-file-name file)))))

In some corner cases, this can infloop.
That's why we do (if (equal dir (setq dir ...)) ...) test in the
main loop.
IIRC I wrote pretty much the above loop at some point and when faced
with those issues I figured it was preferable to reuse the main loop so
as to reuse all the experience it embodies.

> And btw, won't the user test cover the case of crossing ~/ as well?

In 99% of the cases, yes.

> If so, we don't need to abbreviate-file-name, which then incurs
> further overhead inside expand-file-name.

This overhead should be negligible.  Furthermore, I'm not sure whether
we'll keep the user-test since it is incompatible with some (rare)
usage patterns.


        Stefan

Re: locate-dominating-file calls `stat' too eagerly

[Eli Zaretskii]

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: emacs-devel@gnu.org
> Date: Mon, 29 Sep 2008 12:19:15 -0400
> 
> > (defun locate-dominating-file (file regexp)
> >   "Look up the directory hierarchy from FILE for a file matching REGEXP."
> >   ;; If FILE does not exist, find its parent directory that does.
> >   (or (file-exists-p file)
> >       (while (and file (not (file-directory-p file)))
> >         (setq file (file-name-directory (directory-file-name file)))))
> 
> In some corner cases, this can infloop.

What are those cases?  I think we need to describe them in a comment
there.

> > And btw, won't the user test cover the case of crossing ~/ as well?
> 
> In 99% of the cases, yes.

What are the remaining 1%?  Again, I think they should be mentioned in
comments.

Re: locate-dominating-file calls `stat' too eagerly

[Stefan Monnier]

>> > (defun locate-dominating-file (file regexp)
>> >   "Look up the directory hierarchy from FILE for a file matching REGEXP."
>> >   ;; If FILE does not exist, find its parent directory that does.
>> >   (or (file-exists-p file)
>> >       (while (and file (not (file-directory-p file)))
>> >         (setq file (file-name-directory (directory-file-name file)))))
>> In some corner cases, this can infloop.
> What are those cases?  I think we need to describe them in a comment
> there.

Can't remember, sadly.

>> > And btw, won't the user test cover the case of crossing ~/ as well?
>> In 99% of the cases, yes.
> What are the remaining 1%?  Again, I think they should be mentioned in
> comments.

These are too obvious to be worth mentioning: when the user owns ~/..
The most common such case I can think of is when the user is `root'.


        Stefan

Re: locate-dominating-file calls `stat' too eagerly

[Eli Zaretskii]

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: emacs-devel@gnu.org
> Date: Mon, 29 Sep 2008 16:45:22 -0400
> 
> >> > (defun locate-dominating-file (file regexp)
> >> >   "Look up the directory hierarchy from FILE for a file matching REGEXP."
> >> >   ;; If FILE does not exist, find its parent directory that does.
> >> >   (or (file-exists-p file)
> >> >       (while (and file (not (file-directory-p file)))
> >> >         (setq file (file-name-directory (directory-file-name file)))))
> >> In some corner cases, this can infloop.
> > What are those cases?  I think we need to describe them in a comment
> > there.
> 
> Can't remember, sadly.

Were they reported to one of the mailing lists?  Should I search the
archives?

Re: locate-dominating-file calls `stat' too eagerly

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Mon, 29 Sep 2008 10:06:54 -0400
> 
> Wouldn't it be simpler to wrap the `directroy-files' call inside
> a condition-case and drop the file-directory-p altogether?

I installed a change to do that.

Re: locate-dominating-file calls `stat' too eagerly

[Stefan Monnier]

>> >> > (defun locate-dominating-file (file regexp)
>> >> >   "Look up the directory hierarchy from FILE for a file matching REGEXP."
>> >> >   ;; If FILE does not exist, find its parent directory that does.
>> >> >   (or (file-exists-p file)
>> >> >       (while (and file (not (file-directory-p file)))
>> >> >         (setq file (file-name-directory (directory-file-name file)))))
>> >> In some corner cases, this can infloop.
>> > What are those cases?  I think we need to describe them in a comment
>> > there.
>> Can't remember, sadly.
> Were they reported to one of the mailing lists?  Should I search the
> archives?

I have the vague feeling that it was reported to the list, indeed.
But I wouldn't spend too much time on it,


        Stefan

Re: locate-dominating-file calls `stat' too eagerly

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Tue, 30 Sep 2008 10:02:41 -0400
> 
> >> >> In some corner cases, this can infloop.
> >> > What are those cases?  I think we need to describe them in a comment
> >> > there.
> >> Can't remember, sadly.
> > Were they reported to one of the mailing lists?  Should I search the
> > archives?
> 
> I have the vague feeling that it was reported to the list, indeed.
> But I wouldn't spend too much time on it,

I didn't.