What does all-completions with COLLECTION == obarray return?

What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Hello,

in emacs -Q,

(cons
 (length obarray)
 (length (all-completions "" obarray)))

    ==> (1511 . 15039)

I don't understand why the second value is so much larger than the
first.  I would expect as many completions as interned symbols.


Some background:

In helm, we've found a really weird bug.  If you repeatedly evaluate,
with helm-mode on, the following:

--8<---------------cut here---------------start------------->8---
(let* ((hi-lock-face-defaults
        (list
         "hi-yellow"
         "hi-pink"
         "hi-green"
         "hi-blue"
         "hi-black-b"
         "hi-blue-b"
         "hi-red-b"
         "hi-green-b"
         "hi-black-hb")))
  (completing-read
   (format "Highlight using face (default %s): "
           (car hi-lock-face-defaults))
   (all-completions "" obarray)
   'facep t nil 'face-name-history hi-lock-face-defaults))
--8<---------------cut here---------------end--------------->8---

(just say C-g at each prompt), after ten or so iterations, it gets slow,
every time it takes twice as long as before until the prompt appears.
Soon it gets completely unusable freezing Emacs for a minute.

I debugged this and found out that after performing this test,
(all-completions "" obarray) does return a list with ~ a million
elements.  Since we use all-completions to create a candidate list for
completion, we have a million candidates then, and this is what makes
Helm slow.

(length (all-completions "" obarray)) seems to grow exponentially for
every iteration of the above code, but obarray remains constant in size.

What could be happening here?


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

>  (length obarray)

Doesn't do what you think.  An obarray is a vector, and this just
returns the number of buckets in the hash-table.

Check "grep 1511 src/*.[ch]".


        Stefan

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

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

> >  (length obarray)
>
> Doesn't do what you think.  An obarray is a vector, and this just
> returns the number of buckets in the hash-table.

Thanks, my imagination of obarray was indeed wrong.

I continued debugging, and found out that when following the recipe in
helm I posted, the obarray seems to be filled with more and more symbols
- with only a few names.

I wrote this test function:

--8<---------------cut here---------------start------------->8---
(defun my-find-doubles ()
  (let ((table (make-hash-table :size 65000 :test #'equal)))
    (mapatoms (lambda (symbol) (if (gethash (symbol-name symbol) table)
                              (message "%S" (symbol-name symbol))
                            (puthash (symbol-name symbol) t table))))))
--8<---------------cut here---------------end--------------->8---

I would expect that whenever it gets called, it produces no output.

Before running the recipe, it indeed prints nothing.  But after the
first time:

"Bahá'í Date"
"Insert Bahá'í"
"…"

These three symbol names all include non-ascii chars, sorry if they
should have been posted incorrectly.

The effect seems to be exponential or worse, soon I see:


"Bahá'í Date" [8191 times]
"Insert Bahá'í" [8191 times]
"…" [8191 times]

after a few more trials.

What could be happening here?


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

> I continued debugging, and found out that when following the recipe in
> helm I posted, the obarray seems to be filled with more and more symbols
> - with only a few names.

The recipe seems to do something nasty to the obarray.  But I don't
recall seeing this recipe.  Could you resend it?


        Stefan

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> The recipe seems to do something nasty to the obarray.  But I don't
> recall seeing this recipe.  Could you resend it?

It was just this:

--8<---------------cut here---------------start------------->8---
(let* ((hi-lock-face-defaults
        (list
         "hi-yellow"
         "hi-pink"
         "hi-green"
         "hi-blue"
         "hi-black-b"
         "hi-blue-b"
         "hi-red-b"
         "hi-green-b"
         "hi-black-hb")))
  (completing-read
   (format "Highlight using face (default %s): "
           (car hi-lock-face-defaults))
   (all-completions "" obarray)
   'facep t nil 'face-name-history hi-lock-face-defaults))
--8<---------------cut here---------------end--------------->8---

with helm-mode on.

AFAICT we don't try to manipulate obarray directly (of course).  What
nasty things could we be doing?


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

>> The recipe seems to do something nasty to the obarray.  But I don't
>> recall seeing this recipe.  Could you resend it?

> It was just this:

> --8<---------------cut here---------------start------------->8---
> (let* ((hi-lock-face-defaults
>         (list
>          "hi-yellow"
>          "hi-pink"
>          "hi-green"
>          "hi-blue"
>          "hi-black-b"
>          "hi-blue-b"
>          "hi-red-b"
>          "hi-green-b"
>          "hi-black-hb")))
>   (completing-read
>    (format "Highlight using face (default %s): "
>            (car hi-lock-face-defaults))
>    (all-completions "" obarray)
>    'facep t nil 'face-name-history hi-lock-face-defaults))
> --8<---------------cut here---------------end--------------->8---

This code looks OK (though I'd pass obarray directly without going
through all-completions).

> with helm-mode on.
> AFAICT we don't try to manipulate obarray directly (of course).  What
> nasty things could we be doing?

I don't know.  I expected the recipe to demonstrate the kinds of
problems you're seeing, so I guess I lack other parts of the recipe.


        Stefan

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

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

> I don't know.  I expected the recipe to demonstrate the kinds of
> problems you're seeing, so I guess I lack other parts of the recipe.

The "other parts" were just that if you repeat the recipe eight times or
so, Emacs gets slower an then freezes for longer and longer periods
before the minibuffer appears, and that is because obarray grows so
massively.  All that in a minimal helm environment - helm.sh, if it says
something to you.

The answer must be in the implementation of helminized completing read,
but I could not find something obviously unorthodox in the code wrt
obarray.

I'll try to step through the code and find out where something gets
actually added to obarray.


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I'll try to step through the code and find out where something gets
> actually added to obarray.

I was lucky and could condense a recipe for emacs -Q out of the Helm
code we use:

--8<---------------cut here---------------start------------->8---
(progn
  (intern "Bahá'í Date") ;this happens when requiring org
  (let* ((collection (all-completions "" obarray))
         (test #'facep)
         (predicate `(lambda (elm)
                       (condition-case err
                           (if (eq (quote ,test) 'commandp)
                               (funcall (quote ,test) (intern elm))
                             (funcall (quote ,test) elm))
                         (wrong-type-argument
                          (funcall (quote ,test) (intern elm)))))))
    (ignore (all-completions "" collection predicate))
    ;; Test if "Bahá'í Date" is the name of more than one interned symbol
    (when (let ((i 0))
            (catch 'done
              (mapatoms (lambda (s) (when (string= (symbol-name s) "Bahá'í Date")
                                 (if (< i 1) (setq i 1) (throw 'done t)))))
              nil))
      (message "Gotcha!"))))
--8<---------------cut here---------------end--------------->8---

Copy this into scratch in emacs -Q and hit C-x C-e.  I get "Gotcha!",
meaning that after evaluation, there is more than one interned symbol
named "Bahá'í Date".

I guess this should not happen, so it is a bug in Emacs in think.


Thanks,

Michael.
 

bug#20334: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

> I guess this should not happen, so it is a bug in Emacs in think.

Indeed.  Thanks for the test case.  I reduced it to:

   (progn
     (intern "Bahá'í Date") ;this happens when requiring org
     (facep "Bahá'í Date")
     ;; Test if "Bahá'í Date" is the name of more than one interned symbol
     (let ((ss nil))
       (mapatoms (lambda (s) (when (string= (symbol-name s) "Bahá'í Date")
   			    (push s ss)))
   	      nil)
       (length ss)))

So the patch below fixes it, but it points at a problem in the
C function `intern' which I haven't tracked down yet.


        Stefan


diff --git a/src/xfaces.c b/src/xfaces.c
index 9f8a816..d079be8 100644
--- a/src/xfaces.c
+++ b/src/xfaces.c
@@ -1822,7 +1822,8 @@ resolve_face_name (Lisp_Object face_name, bool signal_p)
   Lisp_Object tortoise, hare;
 
   if (STRINGP (face_name))
-    face_name = intern (SSDATA (face_name));
+    /* face_name = intern (SSDATA (face_name)); */
+    face_name = Fintern (face_name, Qnil);
 
   if (NILP (face_name) || !SYMBOLP (face_name))
     return face_name;

bug#20334: What does all-completions with COLLECTION == obarray return?

[Andreas Schwab]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> So the patch below fixes it, but it points at a problem in the
> C function `intern' which I haven't tracked down yet.

The C function only works with ASCII-only strings.

  Lisp_Object tem = oblookup (obarray, str, len, len);

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."

bug#20334: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

>    (progn
>      (intern "Bahá'í Date") ;this happens when requiring org
>      (facep "Bahá'í Date")
>      ;; Test if "Bahá'í Date" is the name of more than one interned symbol
>      (let ((ss nil))
>        (mapatoms (lambda (s) (when (string= (symbol-name s) "Bahá'í Date")
>    			    (push s ss)))
>    	      nil)
>        (length ss)))

I installed the patch below which should fix this problem.  Thanks.


        Stefan


diff --git a/src/lread.c b/src/lread.c
index 050e43e..fa9a63e 100644
--- a/src/lread.c
+++ b/src/lread.c
@@ -3778,8 +3778,11 @@ intern_1 (const char *str, ptrdiff_t len)
   Lisp_Object obarray = check_obarray (Vobarray);
   Lisp_Object tem = oblookup (obarray, str, len, len);
 
-  return SYMBOLP (tem) ? tem : intern_driver (make_string (str, len),
-					      obarray, tem);
+  return (SYMBOLP (tem) ? tem
+	  /* The above `oblookup' was done on the basis of nchars==nbytes, so
+	     the string has to be unibyte.  */
+	  : intern_driver (make_unibyte_string (str, len),
+			   obarray, tem));
 }
 
 Lisp_Object
diff --git a/src/xfaces.c b/src/xfaces.c
index b269722..d198c4b 100644
--- a/src/xfaces.c
+++ b/src/xfaces.c
@@ -1822,7 +1822,7 @@ resolve_face_name (Lisp_Object face_name, bool signal_p)
   Lisp_Object tortoise, hare;
 
   if (STRINGP (face_name))
-    face_name = intern (SSDATA (face_name));
+    face_name = Fintern (face_name, Qnil);
 
   if (NILP (face_name) || !SYMBOLP (face_name))
     return face_name;
diff --git a/test/indent/perl.perl b/test/indent/perl.perl
index 00ef312..ea48754 100755
--- a/test/indent/perl.perl
+++ b/test/indent/perl.perl
@@ -5,6 +5,15 @@ sub add_funds($) {
     return 0;
 }
 
+my $hash = {
+    foo => 'bar',
+    format => 'some',
+};
+
+sub some_code {
+    print "will not indent :(";
+};
+
 use v5.14;
 
 my $str= <<END;

bug#20334: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> I installed the patch below which should fix this problem.  Thanks.

It fixed my test case as well as the original issue in Helm.  Thanks!


P.S.: Your commit includes a change to test/indent/perl.perl that seems
unrelated to this issue.


Thanks again,

Michael.