fix for bug 10994 breaks ido customizations in major way

fix for bug 10994 breaks ido customizations in major way

[Le Wang]

[-- Attachment #1: Type: text/plain, Size: 549 bytes --]

bug:
http://emacs.1067599.n5.nabble.com/bug-10994-23-3-ido-mode-ido-next-match-ido-prev-match-work-wrong-with-same-elements-td300.html

The committed fix converts equal to eq, causing any plugin that propertizes
the completion list to hang Emacs.

This bug is filed as: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=14334

The original bug report is essentially this:

(ido-completing-read "dat is whrong -> " '("2" "3" "3" "3" "4" "5"))

What's the expected behaviour in this case?  Shouldn't the duplicates from
the list just be removed?



-- 
Le

[-- Attachment #2: Type: text/html, Size: 1407 bytes --]

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-03 01:57 +0800, Le Wang wrote:
> bug:
> http://emacs.1067599.n5.nabble.com/bug-10994-23-3-ido-mode-ido-next-match-ido-prev-match-work-wrong-with-same-elements-td300.html
>
> The committed fix converts equal to eq, causing any plugin that propertizes
> the completion list to hang Emacs.
>
> This bug is filed as: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=14334
>
> The original bug report is essentially this:
>
> (ido-completing-read "dat is whrong -> " '("2" "3" "3" "3" "4" "5"))
>
> What's the expected behaviour in this case?  Shouldn't the duplicates from
> the list just be removed?

I put in the fix. It was based on how ido-matches are built from
ido-cur-list. So it fixes the bug.

I am not sure what new things you are doing with ido you will have to
look into this yourself..

Ideally ido should not modified the list fed to it. i.e.

(ido-completing-read "dat is whrong -> " '("2" "3" "3" "3" "4" "5"))

should be able to rotate for- band backwards without removing the dups.
It would be odd-looking if a user supply one list and ido display
another.

Cheers,
Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

[-- Attachment #1: Type: text/plain, Size: 1771 bytes --]

I sent this off list by accident.

On Fri, May 3, 2013 at 12:13 PM, Leo Liu <sdl.web@gmail.com> wrote:

> On 2013-05-03 01:57 +0800, Le Wang wrote:
> > bug:
> >
> http://emacs.1067599.n5.nabble.com/bug-10994-23-3-ido-mode-ido-next-match-ido-prev-match-work-wrong-with-same-elements-td300.html
> >
> > The committed fix converts equal to eq, causing any plugin that
> propertizes
> > the completion list to hang Emacs.
> >
> > This bug is filed as: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=14334
> >
> > The original bug report is essentially this:
> >
> > (ido-completing-read "dat is whrong -> " '("2" "3" "3" "3" "4" "5"))
> >
> > What's the expected behaviour in this case?  Shouldn't the duplicates
> from
> > the list just be removed?
>
> I put in the fix. It was based on how ido-matches are built from
> ido-cur-list. So it fixes the bug.
>

> I am not sure what new things you are doing with ido you will have to
> look into this yourself..
>

There are a few ido customizations floating around that propertizes text.
 This will break all of them.  I don't think this fix is acceptable.


> Ideally ido should not modified the list fed to it. i.e.


 That's not happening.  The list passed to ido is not modified.
 ido-set-matches-1 returns a newlist,

(ido-completing-read "dat is whrong -> " '("2" "3" "3" "3" "4" "5"))
>
> should be able to rotate for- band backwards without removing the dups.
> It would be odd-looking if a user supply one list and ido display
> another.
>

I asked for a use-case of a completion list with duplicate strings.   Do
you have one?

If I do a completing read outside of ido from "emacs -Q" duplicates are not
shown.

I tried

    (completing-read ": " '("a" "ab" "a"))

when I press <tab> only two items are shown.


-- 
Le

[-- Attachment #2: Type: text/html, Size: 3994 bytes --]

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-03 20:49 +0800, Le Wang wrote:
> There are a few ido customizations floating around that propertizes text.
>  This will break all of them.  I don't think this fix is acceptable.

That I wouldn't know. I only know what is in emacs and that the fix has
been in use for a while.  Feel free to propose a different fix.

Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

[-- Attachment #1.1: Type: text/plain, Size: 468 bytes --]

On Sat, May 4, 2013 at 4:33 AM, Leo Liu <sdl.web@gmail.com> wrote:

> On 2013-05-03 20:49 +0800, Le Wang wrote:
> > There are a few ido customizations floating around that propertizes text.
> >  This will break all of them.  I don't think this fix is acceptable.
>
> That I wouldn't know. I only know what is in emacs and that the fix has
> been in use for a while.  Feel free to propose a different fix
>

Sure, I've attached a patch that deletes duplicates.

-- 
Le

[-- Attachment #1.2: Type: text/html, Size: 920 bytes --]

[-- Attachment #2: ido-remove-dups.diff --]
[-- Type: application/octet-stream, Size: 794 bytes --]

diff --git a/lisp/ido.el b/lisp/ido.el
index bedf00e..eb42f4e 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3159,8 +3159,7 @@ Use `eq' for comparison."
 	(sofar nil))
     (while (not ret)
       (setq next (car items))
-      ;; Use `eq' to avoid bug http://debbugs.gnu.org/10994
-      (if (eq next elem)
+      (if (equal next elem)
 	  (setq ret (append items (nreverse sofar)))
 	;; else
 	(progn
@@ -3462,7 +3461,7 @@ This is to make them appear as if they were \"virtual buffers\"."
   ;; Return the current list of choices.
   ;; If DEFAULT is non-nil, and corresponds to an element of choices,
   ;; it is put to the start of the list.
-  (let ((ido-temp-list ido-choice-list))
+  (let ((ido-temp-list (delete-dups ido-choice-list)))
     (if default
 	(progn
 	  (setq ido-temp-list

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

Le Wang <l26wang@gmail.com> writes:

> On Sat, May 4, 2013 at 4:33 AM, Leo Liu <sdl.web@gmail.com> wrote:
>
>> On 2013-05-03 20:49 +0800, Le Wang wrote:
>> > There are a few ido customizations floating around that propertizes text.
>> >  This will break all of them.  I don't think this fix is acceptable.
>>
>> That I wouldn't know. I only know what is in emacs and that the fix has
>> been in use for a while.  Feel free to propose a different fix
>>
>
> Sure, I've attached a patch that deletes duplicates.

This change introduces a serious slowdown which is noticeable for large
candidate lists (try with 10000 elements.) The slowdown happens on every
invocation.

It is obvious that having duplicate candidates makes no sense, but at
the same time scanning the list in advance for all duplicates is
expensive. I'll suggest detecting and removing the duplicates on the
navigation functions, maybe just the adjacent duplicates (using the list
as a ring.)

Another "fix" could be to require a duplicate-free list for
ido-complete.

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

[-- Attachment #1.1: Type: text/plain, Size: 605 bytes --]

On Sat, May 4, 2013 at 4:58 PM, Óscar Fuentes <ofv@wanadoo.es> wrote:

> This change introduces a serious slowdown which is noticeable for large
> candidate lists (try with 10000 elements.) The slowdown happens on every
> invocation.
>
> It is obvious that having duplicate candidates makes no sense, but at
> the same time scanning the list in advance for all duplicates is
> expensive.


The only way to introduce list with dupes is ido-completing-read (i.e. it's
not an issue for files and buffers), so I think it's okay to remove dupes
just once on entry.

Patch atached.


-- 
Le

[-- Attachment #1.2: Type: text/html, Size: 1083 bytes --]

[-- Attachment #2: ido-remove-dups2.diff --]
[-- Type: application/octet-stream, Size: 814 bytes --]

diff --git a/lisp/ido.el b/lisp/ido.el
index bedf00e..15e280e 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3159,8 +3159,7 @@ Use `eq' for comparison."
 	(sofar nil))
     (while (not ret)
       (setq next (car items))
-      ;; Use `eq' to avoid bug http://debbugs.gnu.org/10994
-      (if (eq next elem)
+      (if (equal next elem)
 	  (setq ret (append items (nreverse sofar)))
 	;; else
 	(progn
@@ -4795,7 +4794,7 @@ DEF, if non-nil, is the default value."
 	(ido-directory-nonreadable nil)
 	(ido-directory-too-big nil)
 	(ido-context-switch-command 'ignore)
-	(ido-choice-list choices))
+        (ido-choice-list (delete-dups choices)))
     ;; Initialize ido before invoking ido-read-internal
     (ido-common-initialization)
     (ido-read-internal 'list prompt hist def require-match initial-input)))

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

Le Wang <l26wang@gmail.com> writes:

> The only way to introduce list with dupes is ido-completing-read (i.e. it's
> not an issue for files and buffers), so I think it's okay to remove dupes
> just once on entry.
>
> Patch atached.

diff --git a/lisp/ido.el b/lisp/ido.el
index bedf00e..15e280e 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3159,8 +3159,7 @@ Use `eq' for comparison."
 	(sofar nil))
     (while (not ret)
       (setq next (car items))
-      ;; Use `eq' to avoid bug http://debbugs.gnu.org/10994
-      (if (eq next elem)
+      (if (equal next elem)
 	  (setq ret (append items (nreverse sofar)))
 	;; else
 	(progn
@@ -4795,7 +4794,7 @@ DEF, if non-nil, is the default value."
 	(ido-directory-nonreadable nil)
 	(ido-directory-too-big nil)
 	(ido-context-switch-command 'ignore)
-	(ido-choice-list choices))
+        (ido-choice-list (delete-dups choices)))
     ;; Initialize ido before invoking ido-read-internal
     (ido-common-initialization)
     (ido-read-internal 'list prompt hist def require-match initial-input)))

Tried it and seems to work fine for both flx and the original ido bug
report about C-s/C-r with duplicates.

Leo, what do you think?

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-05 18:57 +0800, Óscar Fuentes wrote:
> Tried it and seems to work fine for both flx and the original ido bug
> report about C-s/C-r with duplicates.
>
> Leo, what do you think?

What is the performance like? delete-dups can be slow.

Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

Leo Liu <sdl.web@gmail.com> writes:

> On 2013-05-05 18:57 +0800, Óscar Fuentes wrote:
>> Tried it and seems to work fine for both flx and the original ido bug
>> report about C-s/C-r with duplicates.
>>
>> Leo, what do you think?
>
> What is the performance like? delete-dups can be slow.

Starting with 10000 candidates, ido flex matching enabled and flx
disabled, I see no responsiveness degradation while randomly typing
chars.

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-05 20:20 +0800, Óscar Fuentes wrote:
> Starting with 10000 candidates, ido flex matching enabled and flx
> disabled, I see no responsiveness degradation while randomly typing
> chars.

In my emacs -q, eval the following:

(let ((choices))
  (mapatoms (lambda (a)
              (when (or (boundp a) (fboundp a))
		(push (symbol-name a) choices))))
  (benchmark-run 10 (delete-dups choices)))

gives me: (19.909896999999997 0 0.0)

So on average there is 2 seconds delay in a MacBook with 2.0G x 2 CPU.

CHOICES is 10321 long in my case.

Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

Leo Liu <sdl.web@gmail.com> writes:

> On 2013-05-05 20:20 +0800, Óscar Fuentes wrote:
>> Starting with 10000 candidates, ido flex matching enabled and flx
>> disabled, I see no responsiveness degradation while randomly typing
>> chars.
>
> In my emacs -q, eval the following:
>
> (let ((choices))
>   (mapatoms (lambda (a)
>               (when (or (boundp a) (fboundp a))
> 		(push (symbol-name a) choices))))
>   (benchmark-run 10 (delete-dups choices)))
>
> gives me: (19.909896999999997 0 0.0)
>
> So on average there is 2 seconds delay in a MacBook with 2.0G x 2 CPU.
>
> CHOICES is 10321 long in my case.

I ran your test code on my Emacs session and the result was

(126.326822296 0 0.0)

being `choices' 26959 items long, which is fairly consistent with your
observations and with the O(n^2) complexity of delete-dups. However,
executing ido-completing-read with a list of 10530 strings (without
duplicates and on a CPU that seems to be similar to yours on
performance) takes 0.72 seconds, which is way faster than the 2 seconds
you observe for the list of symbols of similar size. So it seems that
delete-dups is faster for strings than symbols.

I agree that using delete-dups is not the ideal solution due to
performance concerns, but the current state breaks a quite convenient
usage pattern (i.e. use text properties for carrying extra information
about candidates) on a way that renders the machine to its knees.

IMHO incurring a performance penalty on huge lists is well worth the
pain in this case.

Re: fix for bug 10994 breaks ido customizations in major way

[Stephen J. Turnbull]

Óscar Fuentes writes:

 > So it seems that delete-dups is faster for strings than symbols.

My interpretation is different: something is broken in the benchmarks
(or in the estimate that the CPUs are of comparable performance).

Comparing symbols for equality is a pointer comparison.  Comparing
strings for equality is a pointer comparison, followed by more work
(some variation on a memcmp) in case of failure.

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

"Stephen J. Turnbull" <stephen@xemacs.org> writes:

> Óscar Fuentes writes:
>
>  > So it seems that delete-dups is faster for strings than symbols.
>
> My interpretation is different: something is broken in the benchmarks
> (or in the estimate that the CPUs are of comparable performance).

I estimated that the CPUs are of similar performance because Leo reports
2 seconds for 10321 items and here it takes 12.5 seconds for 27000
items. Then items count ratio is 27000/10321 = 2.6, time ratio is 12.5/2
= 6.25 and the expected time ratio given O(n^2) complexity for the same
CPU is 2.6^2 = 6.76.

However,

(let ((choices))
  (dotimes (i 10321)
    (push (make-symbol (format "s%d" i)) choices))
  (benchmark-run 10 (delete-dups choices)))

takes 6.26 seconds which is quite faster than the 19.9 seconds reported
by Leo. Maybe a L2 cache effect (2.4GHz Intel Q6600 with 4 MB L2 cache
for each pair of cores.)

> Comparing symbols for equality is a pointer comparison.  Comparing
> strings for equality is a pointer comparison, followed by more work
> (some variation on a memcmp) in case of failure.

Yep. A similar benchmark with strings instead of symbols:

(let ((choices))
  (dotimes (i 10321)
    (push (format "%d" i) choices))
  (benchmark-run 10 (delete-dups choices)))

takes 15.2 seconds, 1.5 per iteration.

Now, why delete-dups takes just 0.7 seconds for a list of strings a bit
*larger* than the one used above? The only difference is that those
strings follow the pattern directory/filename (it's the output of `git
ls-files')

However, the real issue being discussed here is if avoiding the overhead
of delete-dups on ido-completing-read warrants breaking some extensions
on a catastrophic way.

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

[-- Attachment #1: Type: text/plain, Size: 476 bytes --]

On Sun, May 5, 2013 at 11:26 PM, Óscar Fuentes <ofv@wanadoo.es> wrote:
>
> However, the real issue being discussed here is if avoiding the overhead
> of delete-dups on ido-completing-read warrants breaking some extensions
> on a catastrophic way.


Upon further reflection, I realized that #10994 is only triggered by
runs of the same string.

I've attached a patch that removes runs without calling delete-dups.
Rough testing indicates it's fast.  :)


--
Le

[-- Attachment #2: ido-remove-dups3.diff --]
[-- Type: application/octet-stream, Size: 1514 bytes --]

diff --git a/lisp/ido.el b/lisp/ido.el
index bedf00e..73ab39e 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3159,8 +3159,7 @@ Use `eq' for comparison."
 	(sofar nil))
     (while (not ret)
       (setq next (car items))
-      ;; Use `eq' to avoid bug http://debbugs.gnu.org/10994
-      (if (eq next elem)
+      (if (equal next elem)
 	  (setq ret (append items (nreverse sofar)))
 	;; else
 	(progn
@@ -3787,7 +3786,7 @@ This is to make them appear as if they were \"virtual buffers\"."
 	   (if (string-match re name)
 	       (setq matches (cons item matches)))))
        items))
-    matches))
+    (ido-delete-runs matches)))
 
 
 (defun ido-set-matches ()
@@ -4678,6 +4677,25 @@ For details of keybindings, see `ido-find-file'."
 			      ido-temp-list))))
     (ido-to-end summaries)))
 
+
+(defun ido-delete-runs (list)
+  "Delete consecutive runs of same item in list.
+Comparison done with `equal'.  Runs may loop back on to the first
+item, in which case, the ending items are deleted."
+  (let ((tail list)
+        before-last-run)
+    (while tail
+      (if (consp (cdr tail))
+          (if (equal (car tail) (cadr tail))
+              (setcdr tail (cddr tail))
+            (setq before-last-run tail)
+            (setq tail (cdr tail)))
+        (setq tail (cdr tail))))
+    (when (and before-last-run
+               (equal (car list) (cadr before-last-run)))
+      (setcdr before-last-run nil)))
+  list)
+
 ;;; Helper functions for other programs
 
 (put 'dired-do-rename 'ido 'ignore)

Re: fix for bug 10994 breaks ido customizations in major way

[Vitalie Spinu]

 >> Le Wang <l26wang@gmail.com>
 >> on Sat, 4 May 2013 15:00:24 +0800 wrote:

 > On Sat, May 4, 2013 at 4:33 AM, Leo Liu <sdl.web@gmail.com> wrote:
 >> On 2013-05-03 20:49 +0800, Le Wang wrote:
 >> > There are a few ido customizations floating around that propertizes text.
 >> >  This will break all of them.  I don't think this fix is acceptable.
 >> 

What do you mean by "break"? 

When propertied strings are used, they are used for a reason - to carry
additional information. 

There are plenty of applications that might need same strings but with
different meaning. For example ido for tag or imenu navigation, there
might be several locations where a symbol is used/defined. Help topics
might have same name but be in different files/packages. Same file-names
in different directories. Same index entry but different locations, etc.

 >> That I wouldn't know. I only know what is in emacs and that the fix has
 >> been in use for a while.  Feel free to propose a different fix
 >> 

 > Sure, I've attached a patch that deletes duplicates.


Currently 

(let ((t1 (propertize "aaa" 'aaa 12))
      (t2 (propertize "aaa" 'aaa 11)))
  (ido-completing-read "?: " (list t1 t2 "sfd")))

works as expected. And the above patch breaks that.

    Vitalie

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

Vitalie Spinu <spinuvit@gmail.com> writes:

[snip]

>  > Sure, I've attached a patch that deletes duplicates.
>
>
> Currently 
>
> (let ((t1 (propertize "aaa" 'aaa 12))
>       (t2 (propertize "aaa" 'aaa 11)))
>   (ido-completing-read "?: " (list t1 t2 "sfd")))
>
> works as expected. And the above patch breaks that.

How does the user differentiate two candidates with the same text?

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

On Tue, May 7, 2013 at 6:49 AM, Vitalie Spinu <spinuvit@gmail.com> wrote:
>  >> Le Wang <l26wang@gmail.com>
>  >> on Sat, 4 May 2013 15:00:24 +0800 wrote:
>
>  > On Sat, May 4, 2013 at 4:33 AM, Leo Liu <sdl.web@gmail.com> wrote:
>  >> On 2013-05-03 20:49 +0800, Le Wang wrote:
>  >> > There are a few ido customizations floating around that propertizes text.
>  >> >  This will break all of them.  I don't think this fix is acceptable.
>  >>
>
> What do you mean by "break"?
>
> When propertied strings are used, they are used for a reason - to carry
> additional information.
>
> There are plenty of applications that might need same strings but with
> different meaning.

No there aren't.  Because this was completely broken in 24.3.1 until
the fix was checked in for 10994.

> For example ido for tag or imenu navigation, there
> might be several locations where a symbol is used/defined.

This is a good reason for including a line#, class, etc.  Why only
text-properties?

Your examples are contrived and not in the wild at all.  I say again,
only HEAD has the ability to handle repeated runs of strings.

BUT the cost of adding this functionality is breaking packages that
add text properties ... Packages that actually __exist__.

> Currently
>
> (let ((t1 (propertize "aaa" 'aaa 12))
>       (t2 (propertize "aaa" 'aaa 11)))
>   (ido-completing-read "?: " (list t1 t2 "sfd")))
>
> works as expected. And the above patch breaks that.

That would be a horrible UI.  Luckily AFAICT, it hasn't happened.
That's why I say there is no actual valid use-case for repeating the
same string in completions.

--
Le

Re: fix for bug 10994 breaks ido customizations in major way

[Vitalie Spinu]

 >> Le Wang <l26wang@gmail.com>
 >> on Tue, 7 May 2013 17:35:23 +0800 wrote:

 >> There are plenty of applications that might need same strings but with
 >> different meaning.

 > No there aren't.  Because this was completely broken in 24.3.1 until
 > the fix was checked in for 10994.

Yes, I was bearing the behavior before, as everyone else did, because it
wasn't happening too often. 

 >> For example ido for tag or imenu navigation, there
 >> might be several locations where a symbol is used/defined.

 > This is a good reason for including a line#, class, etc.  Why only
 > text-properties?

Because it does require quite a fair amount of prepossessing and also
post-processing. I think users are quite fine to see 2-3 strings and
they understand, depending on the context, what repeated string
signify. 

 > Your examples are contrived and not in the wild at all.  I say again,
 > only HEAD has the ability to handle repeated runs of strings.

 > BUT the cost of adding this functionality is breaking packages that
 > add text properties ... Packages that actually __exist__.

What are those packages? 

They can remove text properties, or even not collect them in the first
place, that is definitely easier than adding line-nums/files to
repetitive strings.

 >> Currently
 >> 
 >> (let ((t1 (propertize "aaa" 'aaa 12))
 >> (t2 (propertize "aaa" 'aaa 11)))
 >> (ido-completing-read "?: " (list t1 t2 "sfd")))
 >> 
 >> works as expected. And the above patch breaks that.

 > That would be a horrible UI.  Luckily AFAICT, it hasn't happened.

Not the best UI, but definitely not horrible, users can distinguish 2-3
strings on very rare occasions. It makes implementation much faster and
solves a lot of hustle for lazy programmers:)

 > That's why I say there is no actual valid use-case for repeating the
 > same string in completions.

Look at imenu-anywhere. It happens to have same imenu tag in different
files. The package never relied on text properties because IDO was
broken and it wasn't necessary. Now the issue is solved, and relying on
text properties is a one-line change to the package. It all depends on
whether your patch is accepted or not.

Instead of proposing patch to ido, can you propose a patch to the
"packages" that needlessly use text properties?

There was an ido interface for ETAG selection floating around which I
never used, but I doubt it was uniquifying strings by adding location.

In both cases above, one would need a non trivial pre-processing step to
sort it out. 

    Vitalie

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

Vitalie Spinu <spinuvit@gmail.com> writes:

>  >> Currently
>  >> 
>  >> (let ((t1 (propertize "aaa" 'aaa 12))
>  >> (t2 (propertize "aaa" 'aaa 11)))
>  >> (ido-completing-read "?: " (list t1 t2 "sfd")))
>  >> 
>  >> works as expected. And the above patch breaks that.
>
>  > That would be a horrible UI.  Luckily AFAICT, it hasn't happened.
>
> Not the best UI, but definitely not horrible, users can distinguish 2-3
> strings on very rare occasions.

2-3 identical strings? really? how?

> It makes implementation much faster and
> solves a lot of hustle for lazy programmers:)

Speaking as an user, I'll say that ido is protecting users from sloppy
programmers.

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

Leo, can we wrap this up please?

My last patch

a) is fast
b) fixes the bug as reported by the user (10994)
c) does not break existing functionality packages rely on
d) does not facilitate creating confusing UI in future

Seems like a win to me, but please discuss further if there are other
considerations.

--
Le

Re: fix for bug 10994 breaks ido customizations in major way

[Stefan Monnier]

> Leo, can we wrap this up please?
> My last patch

> a) is fast
> b) fixes the bug as reported by the user (10994)
> c) does not break existing functionality packages rely on
> d) does not facilitate creating confusing UI in future

> Seems like a win to me, but please discuss further if there are other
> considerations.

Supporting multiple options with same text is not very important, given
the tendency to confusion, so I think your patch is a good idea.


        Stefan

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

On Tue, May 7, 2013 at 6:26 PM, Vitalie Spinu <spinuvit@gmail.com> wrote:
> What are those packages?

ido-hacks uses it:
https://github.com/scottjad/ido-hacks/blob/master/ido-hacks.el

My flx package uses it: https://github.com/lewang/flx/blob/master/flx-ido.el

> Not the best UI, but definitely not horrible, users can distinguish 2-3
> strings on very rare occasions. It makes implementation much faster and
> solves a lot of hustle for lazy programmers:)

I find presenting the same string with different properties to be horrendous.

Using your example, but with completing-read:

(let ((t1 (propertize "aaa" 'aaa 12))
      (t2 (propertize "aaa" 'aaa 11)))
  (completing-read "?: " (list t1 t2 "sfd")))

Pressing <tab> I don't see "aaa" twice.  When I select "aaa", the
properties are stripped.

Surely you can agree that ido should not blaze its own trail just to
enable lazy programmers?

> Look at imenu-anywhere. It happens to have same imenu tag in different
> files. The package never relied on text properties because IDO was
> broken and it wasn't necessary. Now the issue is solved, and relying on
> text properties is a one-line change to the package. It all depends on
> whether your patch is accepted or not.

This is a terrible idea if ido facilitated such laziness.

> Instead of proposing patch to ido, can you propose a patch to the
> "packages" that needlessly use text properties?

Because that would be much harder.

Your proposal that I should do a harder thing so horrible UI can be
easily implemented is not acceptable to me.

>
> There was an ido interface for ETAG selection floating around which I
> never used, but I doubt it was uniquifying strings by adding location.
>
> In both cases above, one would need a non trivial pre-processing step to
> sort it out.

Yes.  One should spend time to implement such pre-processing to give
the user a better UI.

--
Le

RE: fix for bug 10994 breaks ido customizations in major way

[Drew Adams]

> > (let ((t1 (propertize "aaa" 'aaa 12))
> >       (t2 (propertize "aaa" 'aaa 11)))
> >   (ido-completing-read "?: " (list t1 t2 "sfd")))
> >
> > works as expected. And the above patch breaks that.
> 
> That would be a horrible UI.  Luckily AFAICT, it hasn't happened.
> That's why I say there is no actual valid use-case for repeating the
> same string in completions.

I don't care much about Ido, so I don't have an opinion about the question at
hand.

However, I will say that it is NOT at all the case that there is nothing out
there, in the wild, that takes advantage of completion candidates that have the
same text (same string chars) but that have other differences, whether the
latter be text properties, symbol plists, associated files/buffers, associated
buffer positions or urls or other locations - or whatever.

Icicles is an example.  There are _loads_ of commands in Icicles that take
advantage of this.  And there are many different ways that the differences,
beyond the candidate text, can be communicated to users.  And there are
different ways that users can choose among such otherwise identical candidates.

The possibilities are too numerous to mention here.  Suffice it to say that,
yes, there are Emacs applications that take advantage of candidate strings (and
symbols) that have text (and symbol) properties.

And yes, there are also applications that take advantage of the fact that a
completion candidate can be a structure (typically an alist element that is a
cons), of which the displayed string is only one component.  Matching can
involve any number of such components, as can the value returned as the user's
completion choice.

FWIW, wrt removing duplicates (and duplication can be defined various ways in
different contexts, as just mentioned), Icicles lets you hit a key (`C-$')
during completion to toggle whether to remove duplicates (or to otherwise
transform the set of matching candidates, depending on the command and user
settings).

HTH.

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

Hi Drew,

On Tue, May 7, 2013 at 10:44 PM, Drew Adams <drew.adams@oracle.com> wrote:
> I don't care much about Ido, so I don't have an opinion about the question at
> hand.
>
> However, I will say that it is NOT at all the case that there is nothing out
> there, in the wild, that takes advantage of completion candidates that have the
> same text (same string chars)

We can say with certainty that there is "nothing in the wild" because
there is a bug in the latest released Emacs and ido that does not work
with duplicate strings.

--
Le

Re: fix for bug 10994 breaks ido customizations in major way

[Vitalie Spinu]

 >> Le Wang <l26wang@gmail.com>
 >> on Tue, 7 May 2013 22:47:58 +0800 wrote:

 > Hi Drew,
 > On Tue, May 7, 2013 at 10:44 PM, Drew Adams <drew.adams@oracle.com> wrote:
 >> I don't care much about Ido, so I don't have an opinion about the question at
 >> hand.
 >> 
 >> However, I will say that it is NOT at all the case that there is nothing out
 >> there, in the wild, that takes advantage of completion candidates that have the
 >> same text (same string chars)

Indeed, it is not difficult to imagine an application when same names
have different faces.

 > We can say with certainty that there is "nothing in the wild" because
 > there is a bug in the latest released Emacs and ido that does not work
 > with duplicate strings.

This is your subjective opinion. The current state is a very reasonable
default, it does *work* (aka cycles) with duplicated strings, and call
this behavior a bug is at least inappropriate.

To have useless properties that are not needed by your application and
rely on IDO to delete those for you is a bad and lazy style. So the
applications that you mention are buggy, not IDO.

Don't want duplicated names, pass through delete-dups before calling
ido-completing-read, or even better, don't collect those properties in
the first place. Not a big deal.

What you propose will force *every* implementation out there to
explicitly deal with duplicated strings. As said before, if they have
duplicated strings they have them for a reason (even if it is simple
laziness). Don't you see that you propose to cut some of the
programmers' and users' flexibility?

    Vitalie

Re: fix for bug 10994 breaks ido customizations in major way

[Óscar Fuentes]

Vitalie Spinu <spinuvit@gmail.com> writes:

> Indeed, it is not difficult to imagine an application when same names
> have different faces.

You are inconveniencing a real (and quite useulf, IMHO) application because
some imaginary, unspecified application?

And, have you considered that there are users who don't see any coloring
on Emacs? (because the limitations of their terminals, or because they
are using voice-to-speach systems, or simply because they regard
anything but raw text as distracting noise.)

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-08 03:53 +0800, Óscar Fuentes wrote:
> You are inconveniencing a real (and quite useulf, IMHO) application because
> some imaginary, unspecified application?
>
> And, have you considered that there are users who don't see any coloring
> on Emacs? (because the limitations of their terminals, or because they
> are using voice-to-speach systems, or simply because they regard
> anything but raw text as distracting noise.)

When I was coming up with a fix for bug#10994 I have already considered
removing duplicates as an option. But I rejected it on the basis of that
being the responsibility of the caller and do not want to take that away
from the programmers.

Anyway, I'll see if I can bake these two options in.

Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

On Wed, May 8, 2013 at 8:04 AM, Leo Liu <sdl.web@gmail.com> wrote:
> On 2013-05-08 03:53 +0800, Óscar Fuentes wrote:
>> You are inconveniencing a real (and quite useulf, IMHO) application because
>> some imaginary, unspecified application?
>>
>> And, have you considered that there are users who don't see any coloring
>> on Emacs? (because the limitations of their terminals, or because they
>> are using voice-to-speach systems, or simply because they regard
>> anything but raw text as distracting noise.)
>
> When I was coming up with a fix for bug#10994 I have already considered
> removing duplicates as an option. But I rejected it on the basis of that
> being the responsibility of the caller

`completing-read' already removes duplicates.  `ido-completing-read'
should just follow its lead.

> and do not want to take that away
> from the programmers.

I want to reiterate this was never "given" to programmers in a
released version of ido.

> Anyway, I'll see if I can bake these two options in.

Baking these two in is not necessary at all!  Think about Óscar
Fuentes's scenario of someone being completely color blind.  Why are
we going out of our way to make the UI bad for these people?


--
Le

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

Your posts don't help your case when people are trying to be
constructive. Nevertheless I have reviewed your last patch:

1. renamed to ido-delete-consecutive-dups for clarify
2. fix a bug so that it can handle duplicates at the end that also
   coincide with the head

HTH,
Leo


diff --git a/lisp/ido.el b/lisp/ido.el
index e335758e..10bff015 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3170,15 +3170,13 @@ (defun ido-restrict-to-matches ()
     (exit-minibuffer)))
 
 (defun ido-chop (items elem)
-  "Remove all elements before ELEM and put them at the end of ITEMS.
-Use `eq' for comparison."
+  "Remove all elements before ELEM and put them at the end of ITEMS."
   (let ((ret nil)
 	(next nil)
 	(sofar nil))
     (while (not ret)
       (setq next (car items))
-      ;; Use `eq' to avoid bug http://debbugs.gnu.org/10994
-      (if (eq next elem)
+      (if (equal next elem)
 	  (setq ret (append items (nreverse sofar)))
 	;; else
 	(progn
@@ -3806,7 +3804,7 @@ (defun ido-set-matches-1 (items &optional do-full)
 	   (if (string-match re name)
 	       (setq matches (cons item matches)))))
        items))
-    matches))
+    (ido-delete-consecutive-dups matches)))
 
 
 (defun ido-set-matches ()
@@ -4729,6 +4727,21 @@ (defun ido-summary-buffers-to-end ()
 			      ido-temp-list))))
     (ido-to-end summaries)))
 
+(defun ido-delete-consecutive-dups (list)
+  "Destructively delete consecutive duplicates in LIST.
+Use `equal' for comparison.  First and last elements are
+considered consecutive."
+  (let ((tail list)
+	(last (make-symbol ""))
+	(result nil))
+    (while (consp tail)
+      (unless (equal (car tail) last)
+	(push (setq last (car tail)) result))
+      (setq tail (cdr tail)))
+    (nreverse (if (equal last (car list))
+		  (cdr result)
+		result))))
+
 ;;; Helper functions for other programs
 
 (put 'dired-do-rename 'ido 'ignore)

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-08 11:10 +0800, Leo Liu wrote:
> 1. renamed to ido-delete-consecutive-dups for clarify
> 2. fix a bug so that it can handle duplicates at the end that also
>    coincide with the head

It turns out my implementation doesn't modify LIST. So maybe rename it
to ido-remove-consecutive-dups or change the implementation to work
in-place.

Cheers,
Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-08 11:29 +0800, Leo Liu wrote:
> It turns out my implementation doesn't modify LIST. So maybe rename it
> to ido-remove-consecutive-dups or change the implementation to work
> in-place.

Missed the case when there is only one element. Patch re-worked as
follows.

diff --git a/lisp/ido.el b/lisp/ido.el
index e335758e..d74733c0 100644
--- a/lisp/ido.el
+++ b/lisp/ido.el
@@ -3170,15 +3170,13 @@ (defun ido-restrict-to-matches ()
     (exit-minibuffer)))
 
 (defun ido-chop (items elem)
-  "Remove all elements before ELEM and put them at the end of ITEMS.
-Use `eq' for comparison."
+  "Remove all elements before ELEM and put them at the end of ITEMS."
   (let ((ret nil)
 	(next nil)
 	(sofar nil))
     (while (not ret)
       (setq next (car items))
-      ;; Use `eq' to avoid bug http://debbugs.gnu.org/10994
-      (if (eq next elem)
+      (if (equal next elem)
 	  (setq ret (append items (nreverse sofar)))
 	;; else
 	(progn
@@ -3806,7 +3804,7 @@ (defun ido-set-matches-1 (items &optional do-full)
 	   (if (string-match re name)
 	       (setq matches (cons item matches)))))
        items))
-    matches))
+    (ido-remove-consecutive-dups matches)))
 
 
 (defun ido-set-matches ()
@@ -4729,6 +4727,22 @@ (defun ido-summary-buffers-to-end ()
 			      ido-temp-list))))
     (ido-to-end summaries)))
 
+(defun ido-remove-consecutive-dups (list)
+  "Remove consecutive duplicates in LIST.
+Use `equal' for comparison.  First and last elements are
+considered consecutive."
+  (let ((tail list)
+	(last (make-symbol ""))
+	(result nil))
+    (while (consp tail)
+      (unless (equal (car tail) last)
+	(push (setq last (car tail)) result))
+      (setq tail (cdr tail)))
+    (nreverse (if (and (equal last (car list))
+		       (cdr result))
+		  (cdr result)
+		result))))
+
 ;;; Helper functions for other programs
 
 (put 'dired-do-rename 'ido 'ignore)

Re: fix for bug 10994 breaks ido customizations in major way

[Vitalie Spinu]

 >> Leo Liu <sdl.web@gmail.com>
 >> on Wed, 08 May 2013 12:49:53 +0800 wrote:

 > +(defun ido-remove-consecutive-dups (list)
 > +  "Remove consecutive duplicates in LIST.
 > +Use `equal' for comparison.  First and last elements are
 > +considered consecutive."
 > +  (let ((tail list)
 > +	(last (make-symbol ""))
 > +	(result nil))
 > +    (while (consp tail)
 > +      (unless (equal (car tail) last)
 > +	(push (setq last (car tail)) result))
 > +      (setq tail (cdr tail)))
 > +    (nreverse (if (and (equal last (car list))
 > +		       (cdr result))
 > +		  (cdr result)
 > +		result))))
 > +

Looks like a generally useful piece. May be subr.el? 

Also delete-consecutive-dups could be very handy.

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-08 16:14 +0800, Vitalie Spinu wrote:
> Looks like a generally useful piece. May be subr.el? 
>
> Also delete-consecutive-dups could be very handy.

If people find it generally useful we can provide
delete-consecutive-dups and let users combine copy-sequence and
delete-consecutive-dups for non-destructive case.

Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Le Wang]

On Wed, May 8, 2013 at 4:42 PM, Leo Liu <sdl.web@gmail.com> wrote:
> On 2013-05-08 16:14 +0800, Vitalie Spinu wrote:
>> Looks like a generally useful piece. May be subr.el?
>>
>> Also delete-consecutive-dups could be very handy.
>
> If people find it generally useful we can provide
> delete-consecutive-dups and let users combine copy-sequence and
> delete-consecutive-dups for non-destructive case.

Last patch looks good.  (make-symbol "") is a useful idiom.


--
Le

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-08 20:23 +0800, Le Wang wrote:
> Last patch looks good.  (make-symbol "") is a useful idiom.

With some small tweak I have installed it in trunk.

Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Juri Linkov]

>> Looks like a generally useful piece. May be subr.el?
>>
>> Also delete-consecutive-dups could be very handy.
>
> If people find it generally useful we can provide
> delete-consecutive-dups and let users combine copy-sequence and
> delete-consecutive-dups for non-destructive case.

Since you intended to make `delete-consecutive-dups' destructive,
wouldn't it be more efficient to use `setcdr' like in `delete-dups'?

Then it could be also used for a new possible value of the option
`history-delete-duplicates' to delete consecutive elements from the history.

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-09 04:56 +0800, Juri Linkov wrote:
> Since you intended to make `delete-consecutive-dups' destructive,
> wouldn't it be more efficient to use `setcdr' like in `delete-dups'?
>
> Then it could be also used for a new possible value of the option
> `history-delete-duplicates' to delete consecutive elements from the history.

Yes for efficiency it could destructively modify the list in-place. ido
needs non-destructive so I am keeping it as ido-remove-consecutive-dups
for now.

Leo

Re: fix for bug 10994 breaks ido customizations in major way

[Leo Liu]

On 2013-05-09 04:56 +0800, Juri Linkov wrote:
> Since you intended to make `delete-consecutive-dups' destructive,
> wouldn't it be more efficient to use `setcdr' like in `delete-dups'?
>
> Then it could be also used for a new possible value of the option
> `history-delete-duplicates' to delete consecutive elements from the history.

delete-consecutive-dups is now in subr.el since it can be useful for
sorted lists.

Leo