bug#5021: avl-tree.el enhancements

[Stefan Monnier <monnier@iro.umontreal.ca>]

>> Hmm... using integers for "direction" isn't pretty.  I see it mostly
>> comes from its use in avl-tree--node-branch.  I guess we'll have to live
>> with it for now...

> Exactly -- it stems from avl-tree--node-branch (which isn't my code).
> The comment after its definition (also not mine) explains the reason
> for it.  I can't think of an efficient way to avoid this.

I know.  I wrote the comment ;-)

>> > +(defun avl-tree--del-balance (node branch dir)
>> > +  ;; Rebalance a tree at the left (BRANCH=0) or right (BRANCH=1) child
>> > +  ;; of NODE after deleting from the left (DIR=0) or right (DIR=1)
>> > +  ;; sub-tree of that child [or is it vice-versa?]. Return t if the
>> > +  ;; height of the tree has shrunk.
>> 
>> This comment should be a docstring instead.

> I've followed the existing convention in avl-tree.el, which doesn't
> provide docstrings for internal functions. If you want to change all the
> comments to docstrings throughout, that's up to you, but I disagree.

Maybe I'll do it at some point, but at least when changing code, the new
code should use docstrings rather than comments.

It used to be the case that docstrings were costly (in terms of memory
use), but that was fixed around Emacs-19 so docstrings are not kept in
memory any more.  There is still a fair bit of code written before that
time which still avoids using docstrings for that reason.  While I don't
think it's important to go back and fix all that old code, I think it's
worthwhile to fix it when we touch such code.

> I personally find the fact that internal library functions aren't
> documented to be a useful form of documentation in itself: it tells me
> that the function definitely shouldn't be used outside of the library.

That's what the "--" is for in avl-tree--del-balance.  It's also much
better because you don't need to check "does this function have
a docstring" to figure out whether it's internal or not.

> Since Elisp doesn't have modules or private functions, that's the
> closest one can get to an internal library function.  Emacs abounds
> with functions lacking docstrings, many of them apparently for
> this reason.

Some people follow this kind of convention, but the Emacs project
doesn't.  We only drop the docstring when we're lazy or when we don't
know what to put in it.

> If you still insist on making one or other or both of these into
> docstrings, I'll make the necessary changes to the patches.

Please do, thank you.

>> Why exactly do you remove the \(fn TREE) thingy at the end?

> It seemed to be a strange documentation convention followed only by
> avl-tree.el, and inconsistently at that. It's redundant, and as far as I
> know isn't used anywhere else in Emacs, because "C-h f <function>"
> already automatically shows the function's calling convention.

It's a trick that can be used to *change* the calling
convention displayed.  So it's not used/needed often.  But here, for
example, it's used to change (avl-tree-compare-function CL-X) into
(avl-tree-compare-function TREE), so the docstring (which refers to
TREE) makes more sense.
Sometimes it's used to hide some internal arguments.
It's also used systematically in autoloaded definitions so as to provide
the calling convention before the function is loaded.

>> Overall, looks good.  Please provide a ChangeLog entry for it as well.

> Errrmmmm...do you mean a ChangeLog entry in the avl-tree.el file itself?
> If so, I already did! :)

No, an entry in the format used by the ChangeLog file.
See http://www.gnu.org/prep/standards/standards.html#Change-Logs


        Stefan