Subject: bug#1085: 23.0.60; all-completions, try-completion inconsistent: Info-read-node-name-1

From: "Drew Adams" <[email-masked]>
Date: Tue, 7 Oct 2008 09:47:17 -0700

Sorry, this is a bit long. Please be patient.

> > 1. User's input should be a prefix of what it is completed to in the
> > minibuffer, which should be the same as the common prefix of all its
> > completions, the result of `try-completion':
> 
> Let's keep "completion in the minibuffer" for another thread and let's
> focus on try0completion, all-completions, and test-competion.

OK, but I'm not sure it won't need to be brought in here at some point. And I
get the impression that you do kind of bring it in, below.

> > 2. `all-completions' elements correspond to `test-completion':
> 
> >> And each of the completions returned by `all-completions' must
> >> also satisfy `test-completion'.  In particular,
> >> (test-completion STRG (all-completions strg TABLE)) must always
> >> return t, for all STRG and TABLE. In this case, for STRG = 
> >> "(el" and TABLE = `Info-read-node-name-1', it returns nil.
> 
> This is not a valid invariant.  E.g. let's say you want a completion
> table for "png files".  You'll probably want the completion to happen
> "one directory at a time", like all other file completions in Emacs,

I guess you're saying that file-name completion is within a given directory. If
not, it sounds like you're bringing in "completion in the minibuffer".

If so, then I don't know what you mean by this:

> so all-completions will have to be able to return directories, 

Do you mean return the name of a subdir?

> even though these are not png files and will hence be rejected by
> test-completion.

I see your point, I think. In that case - that is, if you are saying that a
"png-file" cannot be a directory, we are no longer talking about "like all other
file completions in Emacs" - where subdirectory names *are* treated as file
names.

IOW, if you don't want to include directories in the type "png-files", then
subdirectories would not be among the completions - it's a choice.

But you could define "png-file" (for completion purposes) to either (1) include
directories or (2) allow a directory prefix in the file name.

I think you've extrapolated from the file-completion case, but you've ignored
the fact that Emacs file-completion does treat directory names as valid file
names (for completion). Is "png-file" like file-completion or something
different? Do you want to let directories be completed or not? These are design
decisions for png-file completion. But I see no reason that "png-file" couldn't
be defined to be able to complete as one would like.

In normal file completion also, (all-completions...) can return subdir names as
some of the completions. And (test-completion...) returns t for any of those
subdir names.

Perhaps I'm missing some of what you're saying here; dunno.

> > 3. `all-completions' elements correspond to `try-completion':
> 
> >> the valid completions returned by `all-completions' have the
> >> common prefix that is returned by `try-completion' (which
> >> must in turn have the input as its prefix [see #1]). 
> 
> As discussed, this would imply that the code that builds *Completions*
> figure out which part of the prefix to drop.

The code that builds *Completions* is part of the discussion of "completion in
the minibuffer" - that is, what the user sees, as opposed to what happens for
`all-completions', `try-completion', and `test-completion'. I thought you wanted
to postpone discussion of that.

Anyway, I don't see why *Completions* would drop part of the prefix, unless by
"prefix" you are referring to part of what is in the minibuffer beyond the
prompt - e.g. the directory part for file-name completion. To me, that is *not*
a prefix of any of the completions - it is additional information needed to do
the completing. The fact that a directory name appears to the left of a file
name is almost accidental; it does not make the directory name into a prefix of
the file name.

Really, two pieces of information are being passed to the completion function:
(1) the file name to complete and (2) the directory in which to find the file
whose name you want to complete. Note that #2 is not tied to being a directory
name (string) - it is the directory itself that is needed to look up the
constituent files and their names. The (implementation/design) problem is that
completion functions are predisposed to act on only a string (e.g. file name)
and predicate - there is no explicit provision for passing additional
information that might be needed.

The Info manual/node vs file-name directory/file analogy is a good one for
reasoning about this, I think. In file-name completion, you can erase the
directory part from the minibuffer. The directory info is treated (e.g. passed)
separately; it is not part of the "prefix" for `all-completions' or
`try-completion'.

A user can type a different directory in the minibuffer, and that is taken into
account, but that happens in `find-file' or `read-file-name', not in
`all-completions' and `try-completion'. 

The same approach could be taken for Info and elsewhere as is used for file-name
completion - don't treat all of what is in the minibuffer beyond the prompt as
"prefix" in the completion sense. Use it (or any other context information) as
additional information that lets the completion function do its job. How to pass
that info to the completion function is a design/implementation problem, but it
shouldn't impact the invariants we're discussing.

> So this is the feature about which I said:
> 
>    I have banged my head against this problem for a long time, while
>    working on the minibuffer.el code (and its predecessors), 
>    so I don't expect to change my mind any time soon.  The only thing 
>    you'd accomplish with your proposal is "change", but it would just
>    shift the problems from one place to another without any actual
>    benefit.

I don't see the connection with what is above. That's a far jump.

> So of the 3 invariants you request, the first already holds, 
> the second cannot always hold, and the third will not always hold 
> because it would introduce problems elsewhere.

See above.

> > P.S. Could you explain a little about boundaries and what you meant
> > about using that feature. This is not clear to me.
> 
> minibuffer.el says:
> 
> ;; - The `action' can be (additionally to nil, t, and lambda) 
> of the form
> ;;   (boundaries . SUFFIX) in which case it should return
> ;;   (boundaries START . END).  See `completion-boundaries'.
> ;;   Any other return value should be ignored (so we ignore 
> values returned
> ;;   from completion tables that don't know about this new 
> `action' form).

By "it" in "it should return" I think you mean the function that is the value of
COLLECTION, but that could be made clearer. Similarly, the description of
COLLECTION in the doc string of `all-completions' and `try-completion' (which is
referred to from the doc for `completing-read' should say something more about
the return value of a functional COLLECTION - something beyond just "Whatever it
returns becomes the value of `all-completions'.

Another problem is that COLLECTION, in the `all-completions' doc, is described
as receiving arguments STRING, PREDICATE, and t. Nothing is said about
COLLECTION being able to handle an ACTION arg value of (boundaries . SUFFIX).
Someone writing a COLLECTION function that uses the `boundaries' feature needs
to know how this works. I really think some more work needs to be put into the
doc for this (by you ;-)).

> So, (funcall TABLE STRING PRED '(boundary . "")) should return
> (boundaries START END) where END should be (length STRING) or
> nil, and START will be the length of the prefix of STRING which is
> missing from the all-completions output (e.g. for file completion,
> START should be more or less equivalent to
> (length (file-name-directory STRING))).

Thanks; that's what I thought and saw by debugging, but this helps.

Why treat the directory as a prefix? You are in effect passing it around
separately, specially, but you are assuming unnecessarily that it will be a
prefix. Really, it's just additional info that is needed for the completion
process.

"(emacs)" in Info would be treated the same way, and there too you could
consider it a prefix, so the same mechanism could be used to do the wish-list
completion we discussed, no?

But I don't see why this extra information should always be considered a prefix.
It could be anything really. It's just something that lets COLLECTION (aka
TABLE) do its job and something that we do *not* want to appear as a prefix of
each completion. In the case of file-name and Info node completion you *could*
consider it as in some sense an invisible prefix (but not a prefix that is part
of each completion), but you need not think of it that way. 

How about making the boundaries feature less dependent on treating this separate
info as a (pseudo-)prefix? Instead of a string, it could be any type. A
directory-name string is used to represent a directory, and knowledge of that
directory is used to come up with the proper completions, but the fact that the
directory's name can appear as a prefix to the file name that is the real
completion is little more than an accident. What's really happening is that the
completion function (i.e. COLLECTION) is using the directory object to complete
its STRING input. 

The problem, as I see it, is that among STRING, PREDICATE, and ACTION, there is
no explicit provision for passing the additional info (e.g. directory). So we
have fudged. We use PREDICATE for the dir. Or we fudge ACTION so it can sneak in
the dir as a pseudo-prefix. Fudging ACTION is maybe better than fudging
PREDICATE, and it leaves more room for manoeuver and engenders less conflict,
but it is still a fudge. And if ACTION is fudged to do this, that still doesn't
mean that the extra info should be treated as a prefix (string, start, end,
etc.).

Shouldn't we fix this right, so the extra info that the COLLECTION function
needs is passed as an arg in its own right? I agree with your changes (still in
progress, IIUC) to clean up PRED so it is always a predicate. But it seems to me
that sneaking the extra info in in the form of a "prefix" string inside ACTION
is  also an ugly hack. Why don't we try to come up with something that fits
legacy but also DTRT?

Whether or not today we can always somehow consider or treat the extra info
needed as in some sense a "prefix" of each completion, if we do it right then
tomorrow, at least, there will be cases where info is passed and used that is
really, really in no sense a "prefix". Don't you agree?

I suspect that, at least historically, the treatment of this as a "prefix" might
be bound up with the treatment of base-size and highlighting of the common
prefix. Is that right? If so, I'd suggest cutting that cord now. Prefix
highlighting is something else again, and involves a true prefix that is part of
each completion. And other kinds of completion (e.g. substring) need different
kinds of such highlighting. I don't know if `boundaries' really has anything to
do with base-size and prefix highlighting, but I somehow got that feeling.

> Note that some completion tables may not know about this new
> `boundaries' argument, and will hence return something different from
> (boundaries START END), so any code using this new feature 
> should treat any other return value as equivalent to (boundaries 0
> (length STRING)).

Got it.

> As for your invariant 3, you should be able to recover it if you use
> something like:
> 
>   (defun drew-all-completions (string table pred)
>     (if (not (functionp table))
>         (all-completions string table pred)
>       (let* ((bs (funcall table string pred '(boundaries . "")))
>              (prefix (and (eq 'boundaries (car-safe bs))
>                           (integerp (car-safe (cdr bs)))
>                           (substring string 0 (cadr bs)))))
>         (mapcar (lambda (s) (concat prefix s))
>                 (all-completions string table pred)))))
> 
> I'm pretty sure this code won't work as-is, but hopefully, you get
> the idea.

Yes, thanks; I think so.

Don't get me wrong. I think you've done a great job moving the completion stuff
to Lisp. I think there's still room for improvement, but I admit that there are
some parts of it that I don't understand well, so I might be missing things.