Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Stefan Monnier]

Hello people?

Maybe Eric is not following Emacs development very closely, but he's not
a complete idiot either.  So if you think he got his function wrong,
I think it's a bit presumptuous to think you can be sure your version
will be "the right one" without even discussing it on emacs-devel.

> +(defun directory-files-recursively (dir match &optional include-directories)
> +  "Return all files under DIR that have file names matching MATCH (a regexp).
> +This function works recursively.  Files are returned in \"depth first\"
> +and alphabetical order.
> +If INCLUDE-DIRECTORIES, also include directories that have matching names."

Eric's version allows precise control those subdirectories in which we
want to recurse and those in which we don't.  This is a very
important functionality.

> +  (let ((result nil)
> +	(files nil))
> +    (dolist (file (directory-files dir t))
> +      (let ((leaf (file-name-nondirectory file)))
> +	(unless (member leaf '("." ".."))
> +	  (if (file-directory-p file)

And here you make the same mistake that I already pointed out to Eric:
using directory-files followed by file-directory-p on each file is about
10 times slower than using file-name-all-completions and checking the
presence of a final / instead.


        Stefan

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Eric's version allows precise control those subdirectories in which we
> want to recurse and those in which we don't.  This is a very
> important functionality.

Oh, I missed that.  It was buried rather far down in the doc string...

> And here you make the same mistake that I already pointed out to Eric:
> using directory-files followed by file-directory-p on each file is about
> 10 times slower than using file-name-all-completions and checking the
> presence of a final / instead.

I peeked quickly at 

---
(file-name-all-completions FILE DIRECTORY)

Return a list of all completions of file name FILE in directory DIRECTORY.
These are all file names in directory DIRECTORY which begin with FILE.
---

and it was not immediately obvious to me how this would help here.  Can
FILE be "" to get all files in a directory?  I guess so.

I've now rewritten the function to use that instead.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> I've now rewritten the function to use that instead.

Perhaps there should be a utility function for

(char-equal (aref file (1- (length file))) ?/)

It's not very idiomatic.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> Perhaps there should be a utility function for
>
> (char-equal (aref file (1- (length file))) ?/)
>
> It's not very idiomatic.

How about `directory-file-name-p'?  Which would basically be just that,
as well as a length check.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Leo Liu]

On 2014-12-10 06:09 +0100, Lars Magne Ingebrigtsen wrote:
> (char-equal (aref file (1- (length file))) ?/)

(string-suffix-p "/" ...)

Leo

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Andreas Schwab]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> Lars Magne Ingebrigtsen <larsi@gnus.org> writes:
>
>> I've now rewritten the function to use that instead.
>
> Perhaps there should be a utility function for
>
> (char-equal (aref file (1- (length file))) ?/)
>
> It's not very idiomatic.

Because it is useless and needs to be deleted.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Stefan Monnier]

> How about `directory-file-name-p'?

I think I'd prefer directory-name-p.


        Stefan

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Thierry Volpiatto]

BTW It seems your new function `directory-files-recursively' is
following symlinks and infloop, it should not IMHO.

-- 
Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997 

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:

> BTW It seems your new function `directory-files-recursively' is
> following symlinks and infloop, it should not IMHO.

It shouldn't, so I have to stick a `file-symlink-p' in there, I think.

Stefan, is `file-name-all-completions'+`file-symlink-p' still 10x faster
than `directory-files'+`file-directory-p'?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Stefan Monnier]

> Stefan, is `file-name-all-completions'+`file-symlink-p' still 10x faster
> than `directory-files'+`file-directory-p'?

As long as the file-symlink-p call is only made for directories, it
shouldn't affect the speed very much.


        Stefan

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Thierry Volpiatto]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Stefan, is `file-name-all-completions'+`file-symlink-p' still 10x faster
>> than `directory-files'+`file-directory-p'?
>
> As long as the file-symlink-p call is only made for directories, it
> shouldn't affect the speed very much.

I am not sure the speed is 10X faster vs directory-files, especially
when sorting the resulting list of `file-name-all-completions'.

Also it seems the function is still inflooping even with the check of
file-symlink-p (a bug of file-name-all-completions ?).

My own function is working fine using (directory-files+file-attributes)
with decent performances, but if I try to use 
(file-name-all-completions+check "/$") it infloop also.

PS: Sorry if I sent two mails off list.

-- 
Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997 

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:

> Also it seems the function is still inflooping even with the check of
> file-symlink-p (a bug of file-name-all-completions ?).

Do you know what causes this loop?  Some kind of symlink that
`file-name-all-completions' handles incorrectly or something?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:

> I am not sure the speed is 10X faster vs directory-files, especially
> when sorting the resulting list of `file-name-all-completions'.

I benchmarked a bit with

# for i in `seq 1 3`; do echo $i > /proc/sys/vm/drop_caches; done

in between each run to flush the cache.  This is on a machine with an
SSD.

`file-name-all-completions' version:

(benchmark-run 1 (length (directory-files-recursively "~/" "ChangeLog")))
=> (38.707872137 204 2.599332819999997)

`directory-files' + `file-directory-p' version:

(benchmark-run 1 (length (directory-files-recursively-dir "~/" "ChangeLog")))
=> (89.957997652 1483 25.952981247000064)

So it's faster.  The difference is probably more significant on a
mechanical disk.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:

> My own function is working fine using (directory-files+file-attributes)
> with decent performances, but if I try to use 
> (file-name-all-completions+check "/$") it infloop also.

The infloop is due to this:

(file-symlink-p (expand-file-name "zot/" "/tmp/foo2/"))
=> nil

(file-symlink-p (expand-file-name "zot" "/tmp/foo2/"))
=> "/tmp/"

I'll check in a fix.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Lars Magne Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> How about `directory-file-name-p'?
>
> I think I'd prefer directory-name-p.

Ok; added.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Thierry Volpiatto]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:
>
>> Also it seems the function is still inflooping even with the check of
>> file-symlink-p (a bug of file-name-all-completions ?).
>
> Do you know what causes this loop?

No.

> Some kind of symlink that `file-name-all-completions' handles
> incorrectly or something?

I guess so.

 I will try to investigate next week if possible, I really
would like to use `file-name-all-completions' for my recurse function, but
it fail on this special directory.

-- 
Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997 

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Stefan Monnier]

>> I think I'd prefer directory-name-p.
> Ok; added.

Thanks,


        Stefan

Re: [Emacs-diffs] master 11cf3e9: Implement a new function directory-files-recursively

[Thierry Volpiatto]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:
>
>> Also it seems the function is still inflooping even with the check of
>> file-symlink-p (a bug of file-name-all-completions ?).
>
> Do you know what causes this loop?  Some kind of symlink that
> `file-name-all-completions' handles incorrectly or something?

Ok I found the bug.
To reproduce:
mkdir -p ~/tmp/test/test1/test2/
touch ~/tmp/test/test1/test2/foo.txt
ln -s ~/tmp/test/ ~/tmp/test/test

(directory-files-recursively "~/tmp/test" "")
=>
--8<---------------cut here---------------start------------->8---
Debugger entered--Lisp error: (file-error "Opening directory" "trop de niveaux de liens symboliques" "/home/thierry/tmp/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/")
  file-name-all-completions("" "/home/thierry/tmp/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/")
  (sort (file-name-all-completions "" dir) (quote string<))
  (let ((--dolist-tail-- (sort (file-name-all-completions "" dir) (quote string<)))) (while --dolist-tail-- (let ((file (car --dolist-tail--))) (if (member file (quote ("./" "../"))) nil (if (= (aref file (1- ...)) 47) (let ((path ...)) (if (file-symlink-p path) nil (setq result ...)) (if (and include-directories ...) (progn ...))) (if (string-match match file) (progn (setq files ...))))) (setq --dolist-tail-- (cdr --dolist-tail--)))))
  (let ((result nil) (files nil)) (let ((--dolist-tail-- (sort (file-name-all-completions "" dir) (quote string<)))) (while --dolist-tail-- (let ((file (car --dolist-tail--))) (if (member file (quote ("./" "../"))) nil (if (= (aref file ...) 47) (let (...) (if ... nil ...) (if ... ...)) (if (string-match match file) (progn ...)))) (setq --dolist-tail-- (cdr --dolist-tail--))))) (nconc result (nreverse files)))
  directory-files-recursively("/home/thierry/tmp/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/test/" "" nil)
  (nconc result (directory-files-recursively path match include-directories))
  (setq result (nconc result (directory-files-recursively path match include-directories)))
  (if (file-symlink-p path) nil (setq result (nconc result (directory-files-recursively path match include-directories))))
  (let ((path (expand-file-name file dir))) (if (file-symlink-p path) nil (setq result (nconc result (directory-files-recursively path match include-directories)))) (if (and include-directories (string-match match (substring file 0 (1- (length file))))) (progn (setq result (nconc result (list path))))))
  (if (= (aref file (1- (length file))) 47) (let ((path (expand-file-name file dir))) (if (file-symlink-p path) nil (setq result (nconc result (directory-files-recursively path match include-directories)))) (if (and include-directories (string-match match (substring file 0 (1- (length file))))) (progn (setq result (nconc result (list path)))))) (if (string-match match file) (progn (setq files (cons (expand-file-name file dir) files)))))
  (if (member file (quote ("./" "../"))) nil (if (= (aref file (1- (length file))) 47) (let ((path (expand-file-name file dir))) (if (file-symlink-p path) nil (setq result (nconc result (directory-files-recursively path match include-directories)))) (if (and include-directories (string-match match (substring file 0 (1- ...)))) (progn (setq result (nconc result (list path)))))) (if (string-match match file) (progn (setq files (cons (expand-file-name file dir) files))))))
  (let ((file (car --dolist-tail--))) (if (member file (quote ("./" "../"))) nil (if (= (aref file (1- (length file))) 47) (let ((path (expand-file-name file dir))) (if (file-symlink-p path) nil (setq result (nconc result (directory-files-recursively path match include-directories)))) (if (and include-directories (string-match match (substring file 0 ...))) (progn (setq result (nconc result ...))))) (if (string-match match file) (progn (setq files (cons (expand-file-name file dir) files)))))) (setq --dolist-tail-- (cdr --dolist-tail--)))
  (while --dolist-tail-- (let ((file (car --dolist-tail--))) (if (member file (quote ("./" "../"))) nil (if (= (aref file (1- (length file))) 47) (let ((path (expand-file-name file dir))) (if (file-symlink-p path) nil (setq result (nconc result ...))) (if (and include-directories (string-match match ...)) (progn (setq result ...)))) (if (string-match match file) (progn (setq files (cons ... files)))))) (setq --dolist-tail-- (cdr --dolist-tail--))))
  (let ((--dolist-tail-- (sort (file-name-all-completions "" dir) (quote string<)))) (while --dolist-tail-- (let ((file (car --dolist-tail--))) (if (member file (quote ("./" "../"))) nil (if (= (aref file (1- ...)) 47) (let ((path ...)) (if (file-symlink-p path) nil (setq result ...)) (if (and include-directories ...) (progn ...))) (if (string-match match file) (progn (setq files ...))))) (setq --dolist-tail-- (cdr --dolist-tail--)))))
  (let ((result nil) (files nil)) (let ((--dolist-tail-- (sort (file-name-all-completions "" dir) (quote string<)))) (while --dolist-tail-- (let ((file (car --dolist-tail--))) (if (member file (quote ("./" "../"))) nil (if (= (aref file ...) 47) (let (...) (if ... nil ...) (if ... ...)) (if (string-match match file) (progn ...)))) (setq --dolist-tail-- (cdr --dolist-tail--))))) (nconc result (nreverse files)))
--8<---------------cut here---------------end--------------->8---

Now patch directory-files-recursively:

--8<---------------cut here---------------start------------->8---
diff --git a/lisp/files.el b/lisp/files.el
index 40972d4..ae55b1f 100644
--- a/lisp/files.el
+++ b/lisp/files.el
@@ -774,7 +774,7 @@ If INCLUDE-DIRECTORIES, also include directories that have matching names."
 	(if (= (aref file (1- (length file))) ?/)
 	    (let ((path (expand-file-name file dir)))
 	      ;; Don't follow symlinks to other directories.
-	      (unless (file-symlink-p path)
+	      (unless (file-symlink-p (directory-file-name path))
 		(setq result (nconc result (directory-files-recursively
 					    path match include-directories))))
 	      (when (and include-directories
--8<---------------cut here---------------end--------------->8---


(directory-files-recursively "~/tmp/test" "")
=>
("/home/thierry/tmp/test/test1/test2/foo.txt")

-- 
Thierry
Get my Gnupg key:
gpg --keyserver pgp.mit.edu --recv-keys 59F29997