-

4 files changed, 390 insertions, 86 deletions

diff --git a/doc/emacs/dired.texi b/doc/emacs/dired.texi
index 92c1fd5a041..123f1aea936 100644
--- a/doc/emacs/dired.texi
+++ b/doc/emacs/dired.texi
@@ -778,27 +778,31 @@ Byte compile the specified Emacs Lisp files
 Compilation, elisp, The Emacs Lisp Reference Manual}.
 
 @kindex A @r{(Dired)}
-@findex dired-do-search
+@findex dired-do-find-regexp
 @cindex search multiple files (in Dired)
 @item A @var{regexp} @key{RET}
 Search all the specified files for the regular expression @var{regexp}
-(@code{dired-do-search}).
+(@code{dired-do-find-regexp}).
 
-This command is a variant of @code{tags-search}.  The search stops at
-the first match it finds; use @kbd{M-x tags-loop-continue} to resume
-the search and find the next match.  @xref{Identifier Search}.
+This command is a variant of @code{xref-find-references}
+(@pxref{Identifier Search}), it displays the @file{*xref*} buffer,
+where you can navigate between matches and display them as needed
+using the commands described in @ref{Xref Commands}.
 
 @kindex Q @r{(Dired)}
-@findex dired-do-query-replace-regexp
+@findex dired-do-find-regexp-and-replace
 @cindex search and replace in multiple files (in Dired)
 @item Q @var{regexp} @key{RET} @var{to} @key{RET}
 Perform @code{query-replace-regexp} on each of the specified files,
 replacing matches for @var{regexp} with the string
-@var{to} (@code{dired-do-query-replace-regexp}).
-
-This command is a variant of @code{tags-query-replace}.  If you exit the
-query replace loop, you can use @kbd{M-x tags-loop-continue} to resume
-the scan and replace more matches.  @xref{Identifier Search}.
+@var{to} (@code{dired-do-find-regexp-and-replace}).
+
+This command is a variant of @code{xref-query-replace}.  It presents
+an @file{*xref*} buffer that lists all the matches of @var{regexp},
+and you can use the special commands in that buffer (@pxref{Xref
+Commands}).  In particular, if you exit the query replace loop, you
+can use @kbd{r} in that buffer to replace more matches.
+@xref{Identifier Search}.
 @end table
 
 @node Shell Commands in Dired
diff --git a/doc/lispref/control.texi b/doc/lispref/control.texi
index 008a991102b..df60347f839 100644
--- a/doc/lispref/control.texi
+++ b/doc/lispref/control.texi
@@ -297,36 +297,147 @@ For example:
 @cindex pcase
 @cindex pattern matching
 
-To compare a particular value against various possible cases, the macro
-@code{pcase} can come handy.  It takes the following form:
+The @code{cond} form lets you choose between alternatives using
+predicate conditions that compare values of expressions against
+specific values known and written in advance.  However, sometimes it
+is useful to select alternatives based on more general conditions that
+distinguish between broad classes of values.  The @code{pcase} macro
+allows to choose between alternatives based on matching the value of
+an expression against a series of patterns.  A pattern can be a
+literal value (comparison to literal values is what @code{cond} does),
+or it can be a more general description of the expected structure of
+the expression's value.
+
+@defmac pcase expression &rest clauses
+Evaluate @var{expression} and choose among an arbitrary number of
+alternatives based on the value of @var{expression}.  The possible
+alternatives are specified by @var{clauses}, each of which must be a
+list of the form @code{(@var{pattern} @var{body-forms})}.
+@code{pcase} tries to match the value of @var{expression} to the
+@var{pattern} of each clause, in textual order.  If the value matches,
+the clause succeeds; @code{pcase} then evaluates its @var{body-forms},
+and returns the value of the last of @var{body-forms}.  Any remaining
+@var{clauses} are ignored.
+
+The @var{pattern} part of a clause can be of one of two types:
+@dfn{QPattern}, a pattern quoted with a backquote; or a
+@dfn{UPattern}, which is not quoted.  UPatterns are simpler, so we
+describe them first.
+
+Note: In the description of the patterns below, we use ``the value
+being matched'' to refer to the value of the @var{expression} that is
+the first argument of @code{pcase}.
+
+A UPattern can have one of the following forms:
 
-@example
-(pcase @var{exp} @var{branch}1 @var{branch}2 @var{branch}3 @dots{})
-@end example
+@table @code
 
-where each @var{branch} takes the form @code{(@var{upattern}
-@var{body-forms}@dots{})}.
+@item '@var{val}
+Matches if the value being matched is @code{equal} to @var{val}.
+@item @var{atom}
+Matches any @var{atom}, which can be a keyword, a number, or a string.
+(These are self-quoting, so this kind of UPattern is actually a
+shorthand for @code{'@var{atom}}.)
+@item _
+Matches any value.  This is known as @dfn{don't care} or @dfn{wildcard}.
+@item @var{symbol}
+Matches any value, and additionally let-binds @var{symbol} to the
+value it matched, so that you can later refer to it, either in the
+@var{body-forms} or also later in the pattern.
+@item (pred @var{predfun})
+Matches if the predicate function @var{predfun} returns non-@code{nil}
+when called with the value being matched as its argument.
+@var{predfun} can be one of the possible forms described below.
+@item (guard @var{boolean-expression})
+Matches if @var{boolean-expression} evaluates to non-@code{nil}.  This
+allows to include in a UPattern boolean conditions that refer to
+symbols bound to values (including the value being matched) by
+previous UPatterns.  Typically used inside an @code{and} UPattern, see
+below.  For example, @w{@code{(and x (guard (< x 10)))}} is a pattern
+which matches any number smaller than 10 and let-binds the variable
+@code{x} to that number.
+@item (let @var{upattern} @var{expression})
+Matches if the specified @var{expression} matches the specified
+@var{upattern}.  This allows to match a pattern against the value of
+an @emph{arbitrary} expression, not just the expression that is the
+first argument to @code{pcase}.  (It is called @code{let} because
+@var{upattern} can bind symbols to values using the @var{symbol}
+UPattern.)
+@item (app @var{function} @var{upattern})
+Matches if @var{function} applied to the value being matched returns a
+value that matches @var{upattern}.  This is like the @code{pred}
+UPattern, except that it tests the result against @var{UPattern},
+rather than against a boolean truth value.  The @var{function} call can
+use one of the forms described below.
+@item (or @var{upattern1} @var{upattern2}@dots{})
+Matches if one the argument UPatterns matches.  As soon as the first
+matching UPattern is found, the rest are not tested.  For this reason,
+if any of the UPatterns let-bind symbols to the matched value, they
+should all bind the same symbols.
+@item (and @var{upattern1} @var{upattern2}@dots{})
+Matches if all the argument UPatterns match.
+@end table
+
+The function calls used in the @code{pred} and @code{app} UPatterns
+can have one of the following forms:
+
+@table @asis
+@item function symbol, like @code{integerp}
+In this case, the named function is applied to the value being
+matched.
+@item lambda-function @code{(lambda (@var{arg}) @var{body})}
+In this case, the lambda-function is called with one argument, the
+value being matched.
+@item @code{(@var{func} @var{args}@dots{})}
+This is a function call with @var{n} specified arguments; the function
+is called with these @var{n} arguments and an additional @var{n}+1-th
+argument that is the value being matched.
+@end table
 
-It will first evaluate @var{exp} and then compare the value against each
-@var{upattern} to see which @var{branch} to use, after which it will run the
-corresponding @var{body-forms}.  A common use case is to distinguish
-between a few different constant values:
+Here's an illustrative example of using UPatterns:
 
+@c FIXME: This example should use every one of the UPatterns described
+@c above at least once.
 @example
 (pcase (get-return-code x)
-  (`success       (message "Done!"))
-  (`would-block   (message "Sorry, can't do it now"))
-  (`read-only     (message "The shmliblick is read-only"))
-  (`access-denied (message "You do not have the needed rights"))
+  ('success       (message "Done!"))
+  ('would-block   (message "Sorry, can't do it now"))
+  ('read-only     (message "The shmliblick is read-only"))
+  ('access-denied (message "You do not have the needed rights"))
   (code           (message "Unknown return code %S" code)))
 @end example
 
-In the last clause, @code{code} is a variable that gets bound to the value that
-was returned by @code{(get-return-code x)}.
+The QPatterns are more powerful.  They allow to match the value of the
+@var{expression} that is the first argument of @code{pcase} against
+specifications of its @emph{structure}.  For example, you can specify
+that the value must be a list of 2 elements whose first element is a
+string and the second element is a number.  QPatterns can have one of
+the following forms:
+
+@table @code
+@item `(@var{qpattern1} . @var{qpattern2})
+Matches if the value being matched is a cons cell whose @code{car}
+matches @var{qpattern1} and whose @code{cdr} matches @var{qpattern2}.
+@item `[@var{qpattern1} @var{qpattern2} @dots{} @var{qpatternm}]
+Matches if the value being matched is a vector of length @var{m} whose
+@code{0}..@code{(@var{m}-1)}th elements match @var{qpattern1},
+@var{qpattern2} @dots{} @var{qpatternm}, respectively.
+@item `(,@var{upattern1} ,@var{upattern2} @dots{})
+Matches if the value being matched is a list whose elements match the
+corresponding @var{upattern1}, @var{upattern2}, etc.
+@item @var{atom}
+Matches if corresponding element of the value being matched is
+@code{equal} to the specified @var{atom}.
+@item ,@var{upattern}
+Matches if the corresponding element of the value being matched
+matches the specified @var{upattern}.
+@end table
+
+@end defmac
 
-To give a more complex example, a simple interpreter for a little
-expression language could look like (note that this example requires
-lexical binding):
+Here is an example of using @code{pcase} to implement a simple
+interpreter for a little expression language (note that this example
+requires lexical binding, @pxref{Lexical Binding}):
 
 @example
 (defun evaluate (exp env)
@@ -340,13 +451,19 @@ lexical binding):
     (_                  (error "Unknown expression %S" exp))))
 @end example
 
-Where @code{`(add ,x ,y)} is a pattern that checks that @code{exp} is a three
-element list starting with the symbol @code{add}, then extracts the second and
-third elements and binds them to the variables @code{x} and @code{y}.
-@code{(pred numberp)} is a pattern that simply checks that @code{exp}
-is a number, and @code{_} is the catch-all pattern that matches anything.
+Here @code{`(add ,x ,y)} is a pattern that checks that @code{exp} is a
+three-element list starting with the literal symbol @code{add}, then
+extracts the second and third elements and binds them to the variables
+@code{x} and @code{y}.  Then it evaluates @code{x} and @code{y} and
+adds the results.  The @code{call} and @code{fn} patterns similarly
+implement two flavors of function calls.  @code{(pred numberp)} is a
+pattern that simply checks that @code{exp} is a number and if so,
+evaluates it.  @code{(pred symbolp)} matches symbols, and returns
+their association.  Finally, @code{_} is the catch-all pattern that
+matches anything, so it's suitable for reporting syntax errors.
 
-Here are some sample programs including their evaluation results:
+Here are some sample programs in this small language, including their
+evaluation results:
 
 @example
 (evaluate '(add 1 2) nil)                 ;=> 3
@@ -355,56 +472,13 @@ Here are some sample programs including their evaluation results:
 (evaluate '(sub 1 2) nil)                 ;=> error
 @end example
 
-There are two kinds of patterns involved in @code{pcase}, called
-@emph{U-patterns} and @emph{Q-patterns}.  The @var{upattern} mentioned above
-are U-patterns and can take the following forms:
+Additional UPatterns can be defined using the @code{pcase-defmacro}
+macro.
 
-@table @code
-@item `@var{qpattern}
-This is one of the most common form of patterns.  The intention is to mimic the
-backquote macro: this pattern matches those values that could have been built
-by such a backquote expression.  Since we're pattern matching rather than
-building a value, the unquote does not indicate where to plug an expression,
-but instead it lets one specify a U-pattern that should match the value at
-that location.
-
-More specifically, a Q-pattern can take the following forms:
-@table @code
-@item (@var{qpattern1} . @var{qpattern2})
-This pattern matches any cons cell whose @code{car} matches @var{qpattern1} and
-whose @code{cdr} matches @var{qpattern2}.
-@item [@var{qpattern1} @var{qpattern2} @dots{} @var{qpatternm}]
-This pattern matches a vector of length @var{M} whose 0..(@var{M}-1)th
-elements match @var{qpattern1}, @var{qpattern2} @dots{} @var{qpatternm},
-respectively.
-@item @var{atom}
-This pattern matches any atom @code{equal} to @var{atom}.
-@item ,@var{upattern}
-This pattern matches any object that matches the @var{upattern}.
-@end table
-
-@item @var{symbol}
-A mere symbol in a U-pattern matches anything, and additionally let-binds this
-symbol to the value that it matched, so that you can later refer to it, either
-in the @var{body-forms} or also later in the pattern.
-@item _
-This so-called @emph{don't care} pattern matches anything, like the previous
-one, but unlike symbol patterns it does not bind any variable.
-@item (pred @var{pred})
-This pattern matches if the function @var{pred} returns non-@code{nil} when
-called with the object being matched.
-@item (or @var{upattern1} @var{upattern2}@dots{})
-This pattern matches as soon as one of the argument patterns succeeds.
-All argument patterns should let-bind the same variables.
-@item (and @var{upattern1} @var{upattern2}@dots{})
-This pattern matches only if all the argument patterns succeed.
-@item (guard @var{exp})
-This pattern ignores the object being examined and simply succeeds if @var{exp}
-evaluates to non-@code{nil} and fails otherwise.  It is typically used inside
-an @code{and} pattern.  For example, @code{(and x (guard (< x 10)))}
-is a pattern which matches any number smaller than 10 and let-binds it to
-the variable @code{x}.
-@end table
+@defmac pcase-defmacro name args &rest body
+Define a new UPattern for @code{pcase}.  The UPattern will have the
+form @code{(@var{name} @var{args})}.
+@end defmac
 
 @node Combining Conditions
 @section Constructs for Combining Conditions
diff --git a/doc/lispref/elisp.texi b/doc/lispref/elisp.texi
index da519f579c9..4c1541e98c6 100644
--- a/doc/lispref/elisp.texi
+++ b/doc/lispref/elisp.texi
@@ -536,6 +536,7 @@ Functions
 * Calling Functions::       How to use an existing function.
 * Mapping Functions::       Applying a function to each element of a list, etc.
 * Anonymous Functions::     Lambda expressions are functions with no names.
+* Generic Functions::       Polymorphism, Emacs-style.
 * Function Cells::          Accessing or setting the function definition
                               of a symbol.
 * Closures::                Functions that enclose a lexical environment.
diff --git a/doc/lispref/functions.texi b/doc/lispref/functions.texi
index 1e8e7540395..c5f5b4c22c4 100644
--- a/doc/lispref/functions.texi
+++ b/doc/lispref/functions.texi
@@ -18,6 +18,7 @@ define them.
 * Calling Functions::           How to use an existing function.
 * Mapping Functions::           Applying a function to each element of a list, etc.
 * Anonymous Functions::         Lambda expressions are functions with no names.
+* Generic Functions::           Polymorphism, Emacs-style.
 * Function Cells::              Accessing or setting the function definition
                             of a symbol.
 * Closures::                    Functions that enclose a lexical environment.
@@ -1092,6 +1093,230 @@ the compiled code.  The byte-compiler cannot assume this list is a
 function, even though it looks like one, since it does not know that
 @code{change-property} intends to use it as a function.
 
+@node Generic Functions
+@section Generic Functions
+@cindex generic functions
+@cindex polymorphism
+
+  Functions defined using @code{defun} have a hard-coded set of
+assumptions about the types and expected values of their arguments.
+For example, a function that was designed to handle values of its
+argument that are either numbers or lists of numbers will fail or
+signal an error if called with a value of any other type, such as a
+vector or a string.  This happens because the implementation of the
+function is not prepared to deal with types other than those assumed
+during the design.
+
+  By contrast, object-oriented programs use @dfn{polymorphic
+functions}: a set of specialized functions having the same name, each
+one of which was written for a certain specific set of argument types.
+Which of the functions is actually called is decided at run time based
+on the types of the actual arguments.
+
+@cindex CLOS
+  Emacs provides support for polymorphism.  Like other Lisp
+environments, notably Common Lisp and its Common Lisp Object System
+(@acronym{CLOS}), this support is based on @dfn{generic functions}.
+The Emacs generic functions closely follow @acronym{CLOS}, including
+use of similar names, so if you have experience with @acronym{CLOS},
+the rest of this section will sound very familiar.
+
+  A generic function specifies an abstract operation, by defining its
+name and list of arguments, but (usually) no implementation.  The
+actual implementation for several specific classes of arguments is
+provided by @dfn{methods}, which should be defined separately.  Each
+method that implements a generic function has the same name as the
+generic function, but the method's definition indicates what kinds of
+arguments it can handle by @dfn{specializing} the arguments defined by
+the generic function.  These @dfn{argument specializers} can be more
+or less specific; for example, a @code{string} type is more specific
+than a more general type, such as @code{sequence}.
+
+  Note that, unlike in message-based OO languages, such as C@t{++} and
+Simula, methods that implement generic functions don't belong to a
+class, they belong to the generic function they implement.
+
+  When a generic function is invoked, it selects the applicable
+methods by comparing the actual arguments passed by the caller with
+the argument specializers of each method.  A method is applicable if
+the actual arguments of the call are compatible with the method's
+specializers.  If more than one method is applicable, they are
+combined using certain rules, described below, and the combination
+then handles the call.
+
+@defmac cl-defgeneric name arguments [documentation] [options-and-methods@dots{}] &rest body
+This macro defines a generic function with the specified @var{name}
+and @var{arguments}.  If @var{body} is present, it provides the
+default implementation.  If @var{documentation} is present (it should
+always be), it specifies the documentation string for the generic
+function, in the form @code{(:documentation @var{docstring})}.  The
+optional @var{options-and-methods} can be one of the following forms:
+
+@table @code
+@item (declare @var{declarations})
+A declare form, as described in @ref{Declare Form}.
+@item (:argument-precedence-order &rest @var{args})
+This form affects the sorting order for combining applicable methods.
+Normally, when two methods are compared during combination, method
+arguments are examined left to right, and the first method whose
+argument specializer is more specific will come before the other one.
+The order defined by this form overrides that, and the arguments are
+examined according to their order in this form, and not left to right.
+@item (:method [@var{qualifiers}@dots{}] args &rest body)
+This form defines a method like @code{cl-defmethod} does.
+@end table
+@end defmac
+
+@defmac cl-defmethod name [qualifier] arguments &rest [docstring] body
+This macro defines a particular implementation for the generic
+function called @var{name}.  The implementation code is given by
+@var{body}.  If present, @var{docstring} is the documentation string
+for the method.  The @var{arguments} list, which must be identical in
+all the methods that implement a generic function, and must match the
+argument list of that function, provides argument specializers of the
+form @code{(@var{arg} @var{spec})}, where @var{arg} is the argument
+name as specified in the @code{cl-defgeneric} call, and @var{spec} is
+one of the following specializer forms:
+
+@table @code
+@item @var{type}
+This specializer requires the argument to be of the given @var{type},
+one of the types from the type hierarchy described below.
+@item (eql @var{object})
+This specializer requires the argument be @code{eql} to the given
+@var{object}.
+@item (head @var{object})
+The argument must be a cons cell whose @code{car} is @code{eql} to
+@var{object}.
+@item @var{struct-tag}
+The argument must be an instance of a class named @var{struct-tag}
+defined with @code{cl-defstruct} (@pxref{Structures,,, cl, Common Lisp
+Extensions for GNU Emacs Lisp}), or of one of its parent classes.
+@end table
+
+Alternatively, the argument specializer can be of the form
+@code{&context (@var{expr} @var{spec})}, in which case the value of
+@var{expr} must be compatible with the specializer provided by
+@var{spec}; @var{spec} can be any of the forms described above.  In
+other words, this form of specializer uses the value of @var{expr}
+instead of arguments for the decision whether the method is
+applicable.  For example, @code{&context (overwrite-mode (eql t))}
+will make the method compatible only when @code{overwrite-mode} is
+turned on.
+
+The type specializer, @code{(@var{arg} @var{type})}, can specify one
+of the @dfn{system types} in the following list.  When a parent type
+is specified, an argument whose type is any of its more specific child
+types, as well as grand-children, grand-grand-children, etc. will also
+be compatible.
+
+@table @code
+@item integer
+Parent type: @code{number}.
+@item number
+@item null
+Parent type: @code{symbol}
+@item symbol
+@item string
+Parent type: @code{array}.
+@item array
+Parent type: @code{sequence}.
+@item cons
+Parent type: @code{list}.
+@item list
+Parent type: @code{sequence}.
+@item marker
+@item overlay
+@item float
+Parent type: @code{number}.
+@item window-configuration
+@item process
+@item window
+@item subr
+@item compiled-function
+@item buffer
+@item char-table
+Parent type: @code{array}.
+@item bool-vector
+Parent type: @code{array}.
+@item vector
+Parent type: @code{array}.
+@item frame
+@item hash-table
+@item font-spec
+@item font-entity
+@item font-object
+@end table
+
+The optional @var{qualifier} allows to combine several applicable
+methods.  If it is not present, the defined method is a @dfn{primary}
+method, responsible for providing the primary implementation of the
+generic function for the specialized arguments.  You can also define
+@dfn{auxiliary methods}, by using one of the following values as
+@var{qualifier}:
+
+@table @code
+@item :before
+This auxiliary method will run before the primary method.  More
+accurately, all the @code{:before} methods will run before the
+primary, in the most-specific-first order.
+@item :after
+This auxiliary method will run after the primary method.  More
+accurately, all such methods will run after the primary, in the
+most-specific-last order.
+@item :around
+This auxiliary method will run @emph{instead} of the primary method.
+The most specific of such methods will be run before any other method.
+Such methods normally use @code{cl-call-next-method}, described below,
+to invoke the other auxiliary or primary methods.
+@item :extra @var{string}
+This allows to add more methods, distinguished by @var{string}, for
+the same specializers and qualifiers.
+@end table
+@end defmac
+
+@cindex dispatch of methods for generic function
+@cindex multiple-dispatch methods
+Each time a generic function is called, it builds the @dfn{effective
+method} which will handle this invocation by combining the applicable
+methods defined for the function.  The process of finding the
+applicable methods and producing the effective method is called
+@dfn{dispatch}.  The applicable methods are those all of whose
+specializers are compatible with the actual arguments of the call.
+Since all of the arguments must be compatible with the specializers,
+they all determine whether a method is applicable.  Methods that
+explicitly specialize more than one argument are called
+@dfn{multiple-dispatch methods}.
+
+The applicable methods are sorted into the order in which they will be
+combined.  The method whose left-most argument specializer is the most
+specific one will come first in the order.  (Specifying
+@code{:argument-precedence-order} as part of @code{cl-defmethod}
+overrides that, as described above.)  If the method body calls
+@code{cl-call-next-method}, the next most-specific method will run.
+If there are applicable @code{:around} methods, the most-specific of
+them will run first; it should call @code{cl-call-next-method} to run
+any of the less specific @code{:around} methods.  Next, the
+@code{:before} methods run in the order of their specificity, followed
+by the primary method, and lastly the @code{:after} methods in the
+reverse order of their specificity.
+
+@defun cl-call-next-method &rest args
+When invoked from within the lexical body of a primary or an
+@code{:around} auxiliary method, call the next applicable method for
+the same generic function.  Normally, it is called with no arguments,
+which means to call the next applicable method with the same arguments
+that the calling method was invoked.  Otherwise, the specified
+arguments are used instead.
+@end defun
+
+@defun cl-next-method-p
+This function, when called from within the lexical body of a primary
+or an @code{:around} auxiliary method, returns non-@code{nil} if there
+is a next method to call.
+@end defun
+
+
 @node Function Cells
 @section Accessing Function Cell Contents