--- a/lisp/ChangeLog	Fri Dec 19 11:24:59 2003 +0000
+++ b/lisp/ChangeLog	Fri Dec 19 14:29:07 2003 +0000
@@ -1,3 +1,20 @@
+2003-12-15  Steve Youngs  <sryoungs@bigpond.net.au>
+
+	* wid-edit.el (lazy): New.
+	(widget-child-value-get): New.
+	(widget-child-value-inline): New.
+	(widget-child-validate): New.
+	(widget-type-value-create): New.
+	(widget-type-default-get): New.
+	(widget-type-match): New.
+
+	This adds a "lazy" widget to allow the definition of recursive
+	datatypes for customize.  The composite widgets expand their
+	subtypes immediately, which cause obvious problems for recursive
+	datatypes.  The "lazy" will only expand them when needed, hense
+	the name.
+	From Per Abrahamsen <abraham@dina.kvl.dk>
+
 2003-12-15  Steve Youngs  <sryoungs@bigpond.net.au>
 
 	* package-get.el (package-get-list-packages-where): New.  A

--- a/lisp/wid-edit.el	Fri Dec 19 11:24:59 2003 +0000
+++ b/lisp/wid-edit.el	Fri Dec 19 14:29:07 2003 +0000
@@ -4026,6 +4026,94 @@
     (if (stringp help-echo)
 	(display-message 'help-echo help-echo))))
 
+(define-widget 'lazy 'default
+  "Base widget for recursive datastructures.
+
+The `lazy' widget will, when instantiated, contain a single inferior
+widget, of the widget type specified by the :type parameter.  The
+value of the `lazy' widget is the same as the value of the inferior
+widget.  When deriving a new widget from the 'lazy' widget, the :type
+parameter is allowed to refer to the widget currently being defined,
+thus allowing recursive datastructures to be described.
+
+The:type parameter takes the same arguments as the defcustom
+parameter with the same name.
+
+Most composite widgets, i.e. widgets containing other widgets, does
+not allow recursion.  That is, when you define a new widget type, none
+of the inferior widgets may be of the same type you are currently
+defining.
+
+In Lisp, however, it is custom to define datastructures in terms of
+themselves.  A list, for example, is defined as either nil, or a cons
+cell whose cdr itself is a list.  The obvious way to translate this
+into a widget type would be
+
+  (define-widget 'my-list 'choice
+    \"A list of sexps.\"
+    :tag \"Sexp list\"
+    :args '((const nil) (cons :value (nil) sexp my-list)))
+
+Here we attempt to define my-list as a choice of either the constant
+nil, or a cons-cell containing a sexp and my-lisp.  This will not work
+because the `choice' widget does not allow recursion.
+
+Using the `lazy' widget you can overcome this problem, as in this 
+example: 
+
+  (define-widget 'sexp-list 'lazy
+    \"A list of sexps.\"
+    :tag \"Sexp list\"
+    :type '(choice (const nil) (cons :value (nil) sexp sexp-list)))"
+  :format "%{%t%}: %v"
+  ;; We don't convert :type because we want to allow recursive
+  ;; datastructures.  This is slow, so we should not create speed
+  ;; critical widgets by deriving from this. 
+  :convert-widget 'widget-value-convert-widget
+  :value-create 'widget-type-value-create
+  :value-delete 'widget-children-value-delete
+  :value-get 'widget-child-value-get
+  :value-inline 'widget-child-value-inline
+  :default-get 'widget-type-default-get
+  :match 'widget-type-match
+  :validate 'widget-child-validate)
+
+(defun widget-child-value-get (widget)
+  "Get the value of the first member of :children in WIDGET."
+  (widget-value (car (widget-get widget :children))))
+
+(defun widget-child-value-inline (widget)
+  "Get the inline value of the first member of :children in WIDGET."
+  (widget-apply (car (widget-get widget :children)) :value-inline))
+
+(defun widget-child-validate (widget)
+  "The result of validating the first member of :children in WIDGET."
+  (widget-apply (car (widget-get widget :children)) :validate))
+
+(defun widget-type-value-create (widget)
+  "Convert and instantiate the value of the :type attribute of WIDGET.
+Store the newly created widget in the :children attribute.
+
+The value of the :type attribute should be an unconverted widget type."
+  (let ((value (widget-get widget :value))
+	(type (widget-get widget :type)))
+    (widget-put widget :children 
+                (list (widget-create-child-value widget 
+                                                 (widget-convert type)
+                                                 value)))))
+
+(defun widget-type-default-get (widget)
+  "Get default value from the :type attribute of WIDGET.
+
+The value of the :type attribute should be an unconverted widget type."
+  (widget-default-get (widget-convert (widget-get widget :type))))
+
+(defun widget-type-match (widget value)
+  "Non-nil if the :type value of WIDGET matches VALUE.
+
+The value of the :type attribute should be an unconverted widget type."
+  (widget-apply (widget-convert (widget-get widget :type)) :match value))
+
 ;;; The End:
 
 (provide 'wid-edit)

--- a/man/ChangeLog	Fri Dec 19 11:24:59 2003 +0000
+++ b/man/ChangeLog	Fri Dec 19 14:29:07 2003 +0000
@@ -1,3 +1,8 @@
+2003-12-15  Steve Youngs  <sryoungs@bigpond.net.au>
+
+	* lispref/customize.texi (Defining New Types): New node.
+	From Per Abrahamsen <abraham@dina.kvl.dk>
+
 2003-10-16  Ilya N. Golubev  <gin@mo.msk.ru>
 
 	* lispref/tips.texi (Comment Tips): Typo fix.

--- a/man/lispref/customize.texi	Fri Dec 19 11:24:59 2003 +0000
+++ b/man/lispref/customize.texi	Fri Dec 19 14:29:07 2003 +0000
@@ -325,6 +325,7 @@
 * Composite Types::
 * Splicing into Lists::
 * Type Keywords::
+* Defining New Types::
 @end menu
 
 @node Simple Types
@@ -852,3 +853,63 @@
 @var{force} from the prefix argument.
 @end defun
 
+@node Defining New Types
+@subsection Defining New Types
+
+In the previous sections we have described how to construct elaborate
+type specifications for @code{defcustom}.  In some cases you may want to
+give such a type specification a name.  The obvious case is when you are
+using the same type for many user options, rather than repeat the
+specification for each option, you can give the type specification a
+name once, and use that name each @code{defcustom}.  The other case is
+when a user option accept a recursive datastructure.  To make it
+possible for a datatype to refer to itself, it needs to have a name.
+
+Since custom types are implemented as widgets, the way to define a new
+customize type is to define a new widget.  We are not going to describe
+the widget interface here in details, see @ref{Top, , Introduction,
+widget, The Emacs Widget Library}, for that.  Instead we are going to
+demonstrate the minimal functionality needed for defining new customize
+types by a simple example.
+
+@example
+(define-widget 'binary-tree-of-string 'lazy
+  "A binary tree made of cons-cells and strings."
+  :offset 4
+  :tag "Node"
+  :type '(choice (string :tag "Leaf" :value "")
+                 (cons :tag "Interior"
+                       :value ("" . "") 
+                       binary-tree-of-string
+                       binary-tree-of-string)))
+
+(defcustom foo-bar ""
+  "Sample variable holding a binary tree of strings."
+  :type 'binary-tree-of-string)
+@end example
+
+The function to define a new widget is name @code{define-widget}.  The
+first argument is the symbol we want to make a new widget type.  The
+second argument is a symbol representing an existing widget, the new
+widget is going to be defined in terms of difference from the existing
+widget.  For the purpose of defining new customization types, the
+@code{lazy} widget is perfect, because it accept a @code{:type} keyword
+argument with the same syntax as the keyword argument to
+@code{defcustom} with the same name.  The third argument is a
+documentation string for the new widget.  You will be able to see that
+string with the @kbd{M-x widget-browse @key{ret} binary-tree-of-string
+@key{ret}} command.  
+
+After these mandatory arguments follows the keyword arguments.  The most
+important is @code{:type}, which describes the datatype we want to match
+with this widget.  Here a @code{binary-tree-of-string} is described as
+being either a string, or a cons-cell whose car and cdr are themselves
+both @code{binary-tree-of-string}.  Note the reference to the widget
+type we are currently in the process of defining.  The @code{:tag}
+attribute is a string to name the widget in the user interface, and the
+@code{:offset} argument are there to ensure that child nodes are
+indented four spaces relatively to the parent node, making the tree
+structure apparent in the customization buffer.
+
+The @code{defcustom} shows how the new widget can be used as an ordinary
+customization type.