* bug#61721: Improving support for setting customization at startup in redumped images
@ 2023-02-23 2:33 Lynn Winebarger
0 siblings, 0 replies; only message in thread
From: Lynn Winebarger @ 2023-02-23 2:33 UTC (permalink / raw)
To: 61721
[-- Attachment #1: Type: text/plain, Size: 43563 bytes --]
The attached patch provides support for resetting customization
variables at startup after redumping. It could be considerably improved
by determining dependencies of variables by analysis of the specified
initialization expressions.
Patch is against master commit 098add06eb7d742ff0e6ee0e294931a93a60c71c
In GNU Emacs 30.0.50 (build 6, x86_64-pc-linux-gnu, GTK+ Version
3.24.34, cairo version 1.16.0) of 2023-02-22 built on
localhost.localdomain
Repository revision: 4c68e073419999b14cfee1a1cef5d41d28ab6efe
Repository branch: feature/redump-startup-support
Windowing system distributor 'The X.Org Foundation', version 11.0.12003000
System Description: openSUSE Leap 15.4
Configured using:
'configure --with-xwidgets --with-imagemagick'
Configured features:
ACL CAIRO DBUS FREETYPE GIF GLIB GMP GNUTLS GPM GSETTINGS HARFBUZZ
IMAGEMAGICK JPEG JSON LCMS2 LIBOTF LIBSELINUX LIBSYSTEMD LIBXML2
M17N_FLT MODULES NOTIFY INOTIFY PDUMPER PNG RSVG SECCOMP SOUND SQLITE3
THREADS TIFF TOOLKIT_SCROLL_BARS TREE_SITTER WEBP X11 XDBE XIM XINPUT2
XPM XWIDGETS GTK3 ZLIB
Important settings:
value of $LC_CTYPE: en_US.utf8
value of $LANG: en_US.utf8
value of $XMODIFIERS: @im=fcitx
locale-coding-system: utf-8-unix
Major mode: Lisp Interaction
Minor modes in effect:
erefactor-check-eval-mode: t
erefactor-highlight-mode: t
TeX-PDF-mode: t
global-semantic-mru-bookmark-mode: t
global-semanticdb-minor-mode: t
global-semantic-decoration-mode: t
global-semantic-idle-breadcrumbs-mode: t
global-semantic-idle-completions-mode: t
global-semantic-idle-scheduler-mode: t
global-semantic-idle-local-symbol-highlight-mode: t
global-semantic-idle-summary-mode: t
global-semantic-highlight-func-mode: t
global-semantic-stickyfunc-mode: t
global-semantic-show-parser-state-mode: t
global-semantic-show-unmatched-syntax-mode: t
global-semantic-highlight-edits-mode: t
semantic-mode: t
mode-icons-mode: t
ivy-rich-mode: t
global-origami-mode: t
origami-mode: t
global-hl-line-mode: t
global-ede-mode: t
global-dash-fontify-mode: t
dash-fontify-mode: t
counsel-projectile-mode: t
projectile-mode: t
counsel-mode: t
ivy-mode: t
company-tng-mode: t
company-quickhelp-mode: t
company-quickhelp-local-mode: t
company-posframe-mode: t
global-company-mode: t
company-mode: t
windmove-mode: t
tooltip-mode: t
global-eldoc-mode: t
eldoc-mode: t
show-paren-mode: t
electric-indent-mode: t
mouse-wheel-mode: t
tool-bar-mode: t
menu-bar-mode: t
file-name-shadow-mode: t
global-font-lock-mode: t
font-lock-mode: t
blink-cursor-mode: t
column-number-mode: t
line-number-mode: t
indent-tabs-mode: t
transient-mark-mode: t
auto-composition-mode: t
auto-encryption-mode: t
auto-compression-mode: t
Load-path shadows:
/usr/share/emacs/site-lisp/emu/poem hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/poem
/usr/share/emacs/site-lisp/emu/apel-ver hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/apel-ver
/usr/share/emacs/site-lisp/emu/mule-caesar hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/mule-caesar
/usr/share/emacs/site-lisp/emu/poem-e20_3 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/poem-e20_3
/usr/share/emacs/site-lisp/apel/filename hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/filename
/usr/share/emacs/site-lisp/emu/poem-e20 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/poem-e20
/usr/share/emacs/site-lisp/emu/product hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/product
/usr/share/emacs/site-lisp/emu/pces-20 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/pces-20
/usr/share/emacs/site-lisp/emu/static hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/static
/usr/share/emacs/site-lisp/emu/poe hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/poe
/usr/share/emacs/site-lisp/apel/path-util hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/path-util
/usr/share/emacs/site-lisp/emu/pccl hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/pccl
/usr/share/emacs/site-lisp/emu/mcs-20 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/mcs-20
/usr/share/emacs/site-lisp/emu/inv-23 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/inv-23
/usr/share/emacs/site-lisp/apel/alist hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/alist
/usr/share/emacs/site-lisp/emu/pces-e20 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/pces-e20
/usr/share/emacs/site-lisp/apel/install hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/install
/usr/share/emacs/site-lisp/emu/mcs-e20 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/mcs-e20
/usr/share/emacs/site-lisp/emu/pces hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/pces
/usr/share/emacs/site-lisp/emu/mcharset hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/mcharset
/usr/share/emacs/site-lisp/emu/emu hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/emu
/usr/share/emacs/site-lisp/emu/pccl-20 hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/pccl-20
/usr/share/emacs/site-lisp/emu/broken hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/broken
/usr/share/emacs/site-lisp/apel/calist hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/calist
/usr/share/emacs/site-lisp/emu/invisible hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/invisible
/usr/share/emacs/site-lisp/emu/pcustom hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/pcustom
/usr/share/emacs/site-lisp/emu/richtext hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/richtext
/usr/share/emacs/site-lisp/emu/pym hides
/home/owinebar/.emacs.d/elpa-30/apel-20220720.1308/pym
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/hmac-sha1 hides
/home/owinebar/.emacs.d/elpa-30/oauth-20130128.151/hmac-sha1
/usr/share/emacs/site-lisp/site-start.d/auctex hides
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/auctex
/home/owinebar/.emacs.d/elpa-30/elsa-20230207.1358/Elsafile hides
/home/owinebar/.emacs.d/elpa-30/flycheck-elsa-20220523.1105/Elsafile
/home/owinebar/.emacs.d/elpa-30/lispy-20221225.1927/elpa hides
/home/owinebar/.emacs.d/elpa-30/ivy-20220926.1250/elpa
/home/owinebar/.emacs.d/elpa-30/maxima-20220531.1847/maxima-font-lock
hides /usr/local/share/emacs/site-lisp/maxima-font-lock
/home/owinebar/.emacs.d/elpa-30/cmake-mode-20230209.1921/cmake-mode
hides /usr/local/share/emacs/site-lisp/cmake-mode
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-site hides
/usr/local/share/emacs/site-lisp/tex-site
/home/owinebar/.emacs.d/elpa-30/maxima-20220531.1847/maxima hides
/usr/local/share/emacs/site-lisp/maxima
/usr/share/emacs/site-lisp/apel/filename hides
/usr/local/share/emacs/site-lisp/apel/filename
/usr/share/emacs/site-lisp/apel/path-util hides
/usr/local/share/emacs/site-lisp/apel/path-util
/usr/share/emacs/site-lisp/apel/alist hides
/usr/local/share/emacs/site-lisp/apel/alist
/usr/share/emacs/site-lisp/apel/install hides
/usr/local/share/emacs/site-lisp/apel/install
/usr/share/emacs/site-lisp/apel/calist hides
/usr/local/share/emacs/site-lisp/apel/calist
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-info hides
/usr/local/share/emacs/site-lisp/auctex/tex-info
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-style hides
/usr/local/share/emacs/site-lisp/auctex/tex-style
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/plain-tex hides
/usr/local/share/emacs/site-lisp/auctex/plain-tex
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-jp hides
/usr/local/share/emacs/site-lisp/auctex/tex-jp
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-fold hides
/usr/local/share/emacs/site-lisp/auctex/tex-fold
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/context hides
/usr/local/share/emacs/site-lisp/auctex/context
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/latex-flymake hides
/usr/local/share/emacs/site-lisp/auctex/latex-flymake
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/texmathp hides
/usr/local/share/emacs/site-lisp/auctex/texmathp
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex hides
/usr/local/share/emacs/site-lisp/auctex/tex
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-bar hides
/usr/local/share/emacs/site-lisp/auctex/tex-bar
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/latex hides
/usr/local/share/emacs/site-lisp/auctex/latex
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-mik hides
/usr/local/share/emacs/site-lisp/auctex/tex-mik
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/toolbar-x hides
/usr/local/share/emacs/site-lisp/auctex/toolbar-x
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/multi-prompt hides
/usr/local/share/emacs/site-lisp/auctex/multi-prompt
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/context-nl hides
/usr/local/share/emacs/site-lisp/auctex/context-nl
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/preview hides
/usr/local/share/emacs/site-lisp/auctex/preview
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-ispell hides
/usr/local/share/emacs/site-lisp/auctex/tex-ispell
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/bib-cite hides
/usr/local/share/emacs/site-lisp/auctex/bib-cite
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/font-latex hides
/usr/local/share/emacs/site-lisp/auctex/font-latex
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/tex-font hides
/usr/local/share/emacs/site-lisp/auctex/tex-font
/home/owinebar/.emacs.d/elpa-30/auctex-13.1.9/context-en hides
/usr/local/share/emacs/site-lisp/auctex/context-en
/usr/share/emacs/site-lisp/emu/poem hides
/usr/local/share/emacs/site-lisp/emu/poem
/usr/share/emacs/site-lisp/emu/inv-23 hides
/usr/local/share/emacs/site-lisp/emu/inv-23
/usr/share/emacs/site-lisp/emu/invisible hides
/usr/local/share/emacs/site-lisp/emu/invisible
/usr/share/emacs/site-lisp/emu/mule-caesar hides
/usr/local/share/emacs/site-lisp/emu/mule-caesar
/usr/share/emacs/site-lisp/emu/poem-e20 hides
/usr/local/share/emacs/site-lisp/emu/poem-e20
/usr/share/emacs/site-lisp/emu/pces-20 hides
/usr/local/share/emacs/site-lisp/emu/pces-20
/usr/share/emacs/site-lisp/emu/pces hides
/usr/local/share/emacs/site-lisp/emu/pces
/usr/share/emacs/site-lisp/emu/pym hides
/usr/local/share/emacs/site-lisp/emu/pym
/usr/share/emacs/site-lisp/emu/pccl hides
/usr/local/share/emacs/site-lisp/emu/pccl
/usr/share/emacs/site-lisp/emu/poem-e20_3 hides
/usr/local/share/emacs/site-lisp/emu/poem-e20_3
/usr/share/emacs/site-lisp/emu/pccl-20 hides
/usr/local/share/emacs/site-lisp/emu/pccl-20
/usr/share/emacs/site-lisp/emu/mcs-e20 hides
/usr/local/share/emacs/site-lisp/emu/mcs-e20
/usr/share/emacs/site-lisp/emu/apel-ver hides
/usr/local/share/emacs/site-lisp/emu/apel-ver
/usr/share/emacs/site-lisp/emu/pces-e20 hides
/usr/local/share/emacs/site-lisp/emu/pces-e20
/usr/share/emacs/site-lisp/emu/mcs-20 hides
/usr/local/share/emacs/site-lisp/emu/mcs-20
/usr/share/emacs/site-lisp/emu/product hides
/usr/local/share/emacs/site-lisp/emu/product
/usr/share/emacs/site-lisp/emu/static hides
/usr/local/share/emacs/site-lisp/emu/static
/usr/share/emacs/site-lisp/emu/emu hides
/usr/local/share/emacs/site-lisp/emu/emu
/usr/share/emacs/site-lisp/emu/broken hides
/usr/local/share/emacs/site-lisp/emu/broken
/usr/share/emacs/site-lisp/emu/poe hides
/usr/local/share/emacs/site-lisp/emu/poe
/usr/share/emacs/site-lisp/emu/mcharset hides
/usr/local/share/emacs/site-lisp/emu/mcharset
/usr/share/emacs/site-lisp/emu/pcustom hides
/usr/local/share/emacs/site-lisp/emu/pcustom
/usr/share/emacs/site-lisp/emu/richtext hides
/usr/local/share/emacs/site-lisp/emu/richtext
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mmgeneric hides
/usr/local/share/emacs/site-lisp/flim/mmgeneric
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mime-def hides
/usr/local/share/emacs/site-lisp/flim/mime-def
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mime hides
/usr/local/share/emacs/site-lisp/flim/mime
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/lunit hides
/usr/local/share/emacs/site-lisp/flim/lunit
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mime-conf hides
/usr/local/share/emacs/site-lisp/flim/mime-conf
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mime-parse hides
/usr/local/share/emacs/site-lisp/flim/mime-parse
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mmbuffer hides
/usr/local/share/emacs/site-lisp/flim/mmbuffer
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/std11 hides
/usr/local/share/emacs/site-lisp/flim/std11
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/smtp hides
/usr/local/share/emacs/site-lisp/flim/smtp
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mel-u hides
/usr/local/share/emacs/site-lisp/flim/mel-u
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/hmac-sha1 hides
/usr/local/share/emacs/site-lisp/flim/hmac-sha1
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mel-q hides
/usr/local/share/emacs/site-lisp/flim/mel-q
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mel hides
/usr/local/share/emacs/site-lisp/flim/mel
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/luna hides
/usr/local/share/emacs/site-lisp/flim/luna
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mel-q-ccl hides
/usr/local/share/emacs/site-lisp/flim/mel-q-ccl
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/md5 hides
/usr/local/share/emacs/site-lisp/flim/md5
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mmexternal hides
/usr/local/share/emacs/site-lisp/flim/mmexternal
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/sasl-scram hides
/usr/local/share/emacs/site-lisp/flim/sasl-scram
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mmcooked hides
/usr/local/share/emacs/site-lisp/flim/mmcooked
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/mel-g hides
/usr/local/share/emacs/site-lisp/flim/mel-g
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/eword-encode hides
/usr/local/share/emacs/site-lisp/flim/eword-encode
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/qmtp hides
/usr/local/share/emacs/site-lisp/flim/qmtp
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/eword-decode hides
/usr/local/share/emacs/site-lisp/flim/eword-decode
/usr/share/emacs/site-lisp/gnugo/make-xpms-file hides
/usr/local/share/emacs/site-lisp/gnugo/make-xpms-file
/usr/share/emacs/site-lisp/gnugo/gnugo-big-xpms hides
/usr/local/share/emacs/site-lisp/gnugo/gnugo-big-xpms
/usr/share/emacs/site-lisp/gnugo/gnugo-db hides
/usr/local/share/emacs/site-lisp/gnugo/gnugo-db
/usr/share/emacs/site-lisp/gnugo/gnugo hides
/usr/local/share/emacs/site-lisp/gnugo/gnugo
/usr/share/emacs/site-lisp/gnugo/gnugo-xpms hides
/usr/local/share/emacs/site-lisp/gnugo/gnugo-xpms
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-api hides
/usr/local/share/emacs/site-lisp/psgml/psgml-api
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-pkg hides
/usr/local/share/emacs/site-lisp/psgml/psgml-pkg
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-info hides
/usr/local/share/emacs/site-lisp/psgml/psgml-info
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-debug hides
/usr/local/share/emacs/site-lisp/psgml/psgml-debug
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-fs hides
/usr/local/share/emacs/site-lisp/psgml/psgml-fs
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-dtd hides
/usr/local/share/emacs/site-lisp/psgml/psgml-dtd
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-parse hides
/usr/local/share/emacs/site-lisp/psgml/psgml-parse
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-other hides
/usr/local/share/emacs/site-lisp/psgml/psgml-other
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml-edit hides
/usr/local/share/emacs/site-lisp/psgml/psgml-edit
/home/owinebar/.emacs.d/elpa-30/psgml-1.3.5/psgml hides
/usr/local/share/emacs/site-lisp/psgml/psgml
/home/owinebar/.emacs.d/elpa-30/rtags-xref-20210721.2314/rtags-xref
hides /usr/local/share/emacs/site-lisp/rtags/rtags-xref
/home/owinebar/.emacs.d/elpa-30/company-rtags-20191222.920/company-rtags
hides /usr/local/share/emacs/site-lisp/rtags/company-rtags
/home/owinebar/.emacs.d/elpa-30/ac-rtags-20191222.920/ac-rtags hides
/usr/local/share/emacs/site-lisp/rtags/ac-rtags
/home/owinebar/.emacs.d/elpa-30/ivy-rtags-20191222.920/ivy-rtags hides
/usr/local/share/emacs/site-lisp/rtags/ivy-rtags
/home/owinebar/.emacs.d/elpa-30/rtags-20220818.1535/rtags hides
/usr/local/share/emacs/site-lisp/rtags/rtags
/home/owinebar/.emacs.d/elpa-30/flycheck-rtags-20191222.920/flycheck-rtags
hides /usr/local/share/emacs/site-lisp/rtags/flycheck-rtags
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/semi-setup hides
/usr/local/share/emacs/site-lisp/semi/semi-setup
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-pgp hides
/usr/local/share/emacs/site-lisp/semi/mime-pgp
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/signature hides
/usr/local/share/emacs/site-lisp/semi/signature
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mail-mime-setup
hides /usr/local/share/emacs/site-lisp/semi/mail-mime-setup
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-view hides
/usr/local/share/emacs/site-lisp/semi/mime-view
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-setup hides
/usr/local/share/emacs/site-lisp/semi/mime-setup
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-play hides
/usr/local/share/emacs/site-lisp/semi/mime-play
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-edit hides
/usr/local/share/emacs/site-lisp/semi/mime-edit
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/semi-def hides
/usr/local/share/emacs/site-lisp/semi/semi-def
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-partial hides
/usr/local/share/emacs/site-lisp/semi/mime-partial
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-image hides
/usr/local/share/emacs/site-lisp/semi/mime-image
/home/owinebar/.emacs.d/elpa-30/semi-20230104.1321/mime-w3 hides
/usr/local/share/emacs/site-lisp/semi/mime-w3
/usr/share/emacs/site-lisp/site-start.d/auctex hides
/usr/local/share/emacs/site-lisp/site-start.d/auctex
/usr/share/emacs/site-lisp/site-start.d/preview-latex hides
/usr/local/share/emacs/site-lisp/site-start.d/preview-latex
/usr/share/emacs/site-lisp/w3m/w3m-load hides
/usr/local/share/emacs/site-lisp/w3m/w3m-load
/usr/share/emacs/site-lisp/w3m/sb-heise hides
/usr/local/share/emacs/site-lisp/w3m/sb-heise
/usr/share/emacs/site-lisp/w3m/sb-yoshirin hides
/usr/local/share/emacs/site-lisp/w3m/sb-yoshirin
/usr/share/emacs/site-lisp/w3m/w3m-hist hides
/usr/local/share/emacs/site-lisp/w3m/w3m-hist
/usr/share/emacs/site-lisp/w3m/sb-exconn hides
/usr/local/share/emacs/site-lisp/w3m/sb-exconn
/usr/share/emacs/site-lisp/w3m/sb-mhonarc hides
/usr/local/share/emacs/site-lisp/w3m/sb-mhonarc
/usr/share/emacs/site-lisp/w3m/sb-pocketgames hides
/usr/local/share/emacs/site-lisp/w3m/sb-pocketgames
/usr/share/emacs/site-lisp/w3m/sb-sankei hides
/usr/local/share/emacs/site-lisp/w3m/sb-sankei
/usr/share/emacs/site-lisp/w3m/sb-security-memo hides
/usr/local/share/emacs/site-lisp/w3m/sb-security-memo
/usr/share/emacs/site-lisp/w3m/sb-toshiba hides
/usr/local/share/emacs/site-lisp/w3m/sb-toshiba
/usr/share/emacs/site-lisp/w3m/sb-mailman hides
/usr/local/share/emacs/site-lisp/w3m/sb-mailman
/usr/share/emacs/site-lisp/w3m/sb-text hides
/usr/local/share/emacs/site-lisp/w3m/sb-text
/usr/share/emacs/site-lisp/w3m/sb-wired-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-wired-jp
/usr/share/emacs/site-lisp/w3m/sb-hns hides
/usr/local/share/emacs/site-lisp/w3m/sb-hns
/usr/share/emacs/site-lisp/w3m/sb-bbdb-ml hides
/usr/local/share/emacs/site-lisp/w3m/sb-bbdb-ml
/usr/share/emacs/site-lisp/w3m/sb-opentechpress-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-opentechpress-jp
/usr/share/emacs/site-lisp/w3m/w3m-rss hides
/usr/local/share/emacs/site-lisp/w3m/w3m-rss
/usr/share/emacs/site-lisp/w3m/sb-fml hides
/usr/local/share/emacs/site-lisp/w3m/sb-fml
/usr/share/emacs/site-lisp/w3m/w3m-save hides
/usr/local/share/emacs/site-lisp/w3m/w3m-save
/usr/share/emacs/site-lisp/w3m/sb-slashdot-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-slashdot-jp
/usr/share/emacs/site-lisp/w3m/sb-yomiuri-html hides
/usr/local/share/emacs/site-lisp/w3m/sb-yomiuri-html
/usr/share/emacs/site-lisp/w3m/w3m hides
/usr/local/share/emacs/site-lisp/w3m/w3m
/usr/share/emacs/site-lisp/w3m/sb-ruby hides
/usr/local/share/emacs/site-lisp/w3m/sb-ruby
/usr/share/emacs/site-lisp/w3m/w3m-lnum hides
/usr/local/share/emacs/site-lisp/w3m/w3m-lnum
/usr/share/emacs/site-lisp/w3m/sb-cnn-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-cnn-jp
/usr/share/emacs/site-lisp/w3m/w3m-antenna hides
/usr/local/share/emacs/site-lisp/w3m/w3m-antenna
/usr/share/emacs/site-lisp/w3m/sb-yahoo hides
/usr/local/share/emacs/site-lisp/w3m/sb-yahoo
/usr/share/emacs/site-lisp/w3m/sb-kyoko-np hides
/usr/local/share/emacs/site-lisp/w3m/sb-kyoko-np
/usr/share/emacs/site-lisp/w3m/sb-ibm-dev hides
/usr/local/share/emacs/site-lisp/w3m/sb-ibm-dev
/usr/share/emacs/site-lisp/w3m/sb-itmedia hides
/usr/local/share/emacs/site-lisp/w3m/sb-itmedia
/usr/share/emacs/site-lisp/w3m/sb-excite hides
/usr/local/share/emacs/site-lisp/w3m/sb-excite
/usr/share/emacs/site-lisp/w3m/w3m-image hides
/usr/local/share/emacs/site-lisp/w3m/w3m-image
/usr/share/emacs/site-lisp/w3m/sb-f1fan hides
/usr/local/share/emacs/site-lisp/w3m/sb-f1fan
/usr/share/emacs/site-lisp/w3m/sb-airs hides
/usr/local/share/emacs/site-lisp/w3m/sb-airs
/usr/share/emacs/site-lisp/w3m/w3m-ems hides
/usr/local/share/emacs/site-lisp/w3m/w3m-ems
/usr/share/emacs/site-lisp/w3m/sb-mailarc hides
/usr/local/share/emacs/site-lisp/w3m/sb-mailarc
/usr/share/emacs/site-lisp/w3m/sb-debian hides
/usr/local/share/emacs/site-lisp/w3m/sb-debian
/usr/share/emacs/site-lisp/w3m/sb-meadow hides
/usr/local/share/emacs/site-lisp/w3m/sb-meadow
/usr/share/emacs/site-lisp/w3m/sb-yomiuri hides
/usr/local/share/emacs/site-lisp/w3m/sb-yomiuri
/usr/share/emacs/site-lisp/w3m/sb-scipy hides
/usr/local/share/emacs/site-lisp/w3m/sb-scipy
/usr/share/emacs/site-lisp/w3m/sb-savannah hides
/usr/local/share/emacs/site-lisp/w3m/sb-savannah
/usr/share/emacs/site-lisp/w3m/sb-squeak-ja hides
/usr/local/share/emacs/site-lisp/w3m/sb-squeak-ja
/usr/share/emacs/site-lisp/w3m/w3m-weather hides
/usr/local/share/emacs/site-lisp/w3m/w3m-weather
/usr/share/emacs/site-lisp/w3m/sb-rss-blogs hides
/usr/local/share/emacs/site-lisp/w3m/sb-rss-blogs
/usr/share/emacs/site-lisp/w3m/sb-debian-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-debian-jp
/usr/share/emacs/site-lisp/w3m/sb-rediff hides
/usr/local/share/emacs/site-lisp/w3m/sb-rediff
/usr/share/emacs/site-lisp/w3m/sb-xemacs hides
/usr/local/share/emacs/site-lisp/w3m/sb-xemacs
/usr/share/emacs/site-lisp/w3m/sb-haiku-os hides
/usr/local/share/emacs/site-lisp/w3m/sb-haiku-os
/usr/share/emacs/site-lisp/w3m/w3m-util hides
/usr/local/share/emacs/site-lisp/w3m/w3m-util
/usr/share/emacs/site-lisp/w3m/sb-fau hides
/usr/local/share/emacs/site-lisp/w3m/sb-fau
/usr/share/emacs/site-lisp/w3m/sb-pcweb-column hides
/usr/local/share/emacs/site-lisp/w3m/sb-pcweb-column
/usr/share/emacs/site-lisp/w3m/sb-2ch hides
/usr/local/share/emacs/site-lisp/w3m/sb-2ch
/usr/share/emacs/site-lisp/w3m/sb-japantimes hides
/usr/local/share/emacs/site-lisp/w3m/sb-japantimes
/usr/share/emacs/site-lisp/w3m/sb-redhat hides
/usr/local/share/emacs/site-lisp/w3m/sb-redhat
/usr/share/emacs/site-lisp/w3m/sb-asahi-html hides
/usr/local/share/emacs/site-lisp/w3m/sb-asahi-html
/usr/share/emacs/site-lisp/w3m/sb-rss-hash hides
/usr/local/share/emacs/site-lisp/w3m/sb-rss-hash
/usr/share/emacs/site-lisp/w3m/sb-engadget-ja hides
/usr/local/share/emacs/site-lisp/w3m/sb-engadget-ja
/usr/share/emacs/site-lisp/w3m/sb-wikimedia hides
/usr/local/share/emacs/site-lisp/w3m/sb-wikimedia
/usr/share/emacs/site-lisp/w3m/sb-gnome hides
/usr/local/share/emacs/site-lisp/w3m/sb-gnome
/usr/share/emacs/site-lisp/w3m/sb-laut-de hides
/usr/local/share/emacs/site-lisp/w3m/sb-laut-de
/usr/share/emacs/site-lisp/w3m/w3m-perldoc hides
/usr/local/share/emacs/site-lisp/w3m/w3m-perldoc
/usr/share/emacs/site-lisp/w3m/sb-the-onion hides
/usr/local/share/emacs/site-lisp/w3m/sb-the-onion
/usr/share/emacs/site-lisp/w3m/sb-perlentaucher-de hides
/usr/local/share/emacs/site-lisp/w3m/sb-perlentaucher-de
/usr/share/emacs/site-lisp/w3m/sb-coldsync hides
/usr/local/share/emacs/site-lisp/w3m/sb-coldsync
/usr/share/emacs/site-lisp/w3m/sb-sml hides
/usr/local/share/emacs/site-lisp/w3m/sb-sml
/usr/share/emacs/site-lisp/w3m/sb-m17n hides
/usr/local/share/emacs/site-lisp/w3m/sb-m17n
/usr/share/emacs/site-lisp/w3m/sb-zdnet-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-zdnet-jp
/usr/share/emacs/site-lisp/w3m/sb-msports-nifty hides
/usr/local/share/emacs/site-lisp/w3m/sb-msports-nifty
/usr/share/emacs/site-lisp/w3m/sb-hash hides
/usr/local/share/emacs/site-lisp/w3m/sb-hash
/usr/share/emacs/site-lisp/w3m/sb-digiko hides
/usr/local/share/emacs/site-lisp/w3m/sb-digiko
/usr/share/emacs/site-lisp/w3m/sb-x51 hides
/usr/local/share/emacs/site-lisp/w3m/sb-x51
/usr/share/emacs/site-lisp/w3m/sb-cgi-board hides
/usr/local/share/emacs/site-lisp/w3m/sb-cgi-board
/usr/share/emacs/site-lisp/w3m/sb-n24-de hides
/usr/local/share/emacs/site-lisp/w3m/sb-n24-de
/usr/share/emacs/site-lisp/w3m/sb-sourceforge-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-sourceforge-jp
/usr/share/emacs/site-lisp/w3m/w3m-dtree hides
/usr/local/share/emacs/site-lisp/w3m/w3m-dtree
/usr/share/emacs/site-lisp/w3m/sb-cnet-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-cnet-jp
/usr/share/emacs/site-lisp/w3m/sb-nytimes hides
/usr/local/share/emacs/site-lisp/w3m/sb-nytimes
/usr/share/emacs/site-lisp/w3m/w3m-session hides
/usr/local/share/emacs/site-lisp/w3m/w3m-session
/usr/share/emacs/site-lisp/w3m/w3m-proc hides
/usr/local/share/emacs/site-lisp/w3m/w3m-proc
/usr/share/emacs/site-lisp/w3m/sb-mainichi hides
/usr/local/share/emacs/site-lisp/w3m/sb-mainichi
/usr/share/emacs/site-lisp/w3m/sb-tech-on hides
/usr/local/share/emacs/site-lisp/w3m/sb-tech-on
/usr/share/emacs/site-lisp/w3m/sb-dennou hides
/usr/local/share/emacs/site-lisp/w3m/sb-dennou
/usr/share/emacs/site-lisp/w3m/sb-aljazeera hides
/usr/local/share/emacs/site-lisp/w3m/sb-aljazeera
/usr/share/emacs/site-lisp/w3m/sb-atom hides
/usr/local/share/emacs/site-lisp/w3m/sb-atom
/usr/share/emacs/site-lisp/w3m/sb-emacs-w3m hides
/usr/local/share/emacs/site-lisp/w3m/sb-emacs-w3m
/usr/share/emacs/site-lisp/w3m/sb-wincefan hides
/usr/local/share/emacs/site-lisp/w3m/sb-wincefan
/usr/share/emacs/site-lisp/w3m/sb-ffii hides
/usr/local/share/emacs/site-lisp/w3m/sb-ffii
/usr/share/emacs/site-lisp/w3m/sb-yahoo-sports hides
/usr/local/share/emacs/site-lisp/w3m/sb-yahoo-sports
/usr/share/emacs/site-lisp/w3m/sb-debugmagazin-de hides
/usr/local/share/emacs/site-lisp/w3m/sb-debugmagazin-de
/usr/share/emacs/site-lisp/w3m/sb-nikkansports hides
/usr/local/share/emacs/site-lisp/w3m/sb-nikkansports
/usr/share/emacs/site-lisp/w3m/sb-slashdot hides
/usr/local/share/emacs/site-lisp/w3m/sb-slashdot
/usr/share/emacs/site-lisp/w3m/sb-javaconf hides
/usr/local/share/emacs/site-lisp/w3m/sb-javaconf
/usr/share/emacs/site-lisp/w3m/sb-yahoo-auctions hides
/usr/local/share/emacs/site-lisp/w3m/sb-yahoo-auctions
/usr/share/emacs/site-lisp/w3m/w3m-favicon hides
/usr/local/share/emacs/site-lisp/w3m/w3m-favicon
/usr/share/emacs/site-lisp/w3m/sb-kantei hides
/usr/local/share/emacs/site-lisp/w3m/sb-kantei
/usr/share/emacs/site-lisp/w3m/w3m-cookie hides
/usr/local/share/emacs/site-lisp/w3m/w3m-cookie
/usr/share/emacs/site-lisp/w3m/sb-squeak-dev hides
/usr/local/share/emacs/site-lisp/w3m/sb-squeak-dev
/usr/share/emacs/site-lisp/w3m/sb-bbc hides
/usr/local/share/emacs/site-lisp/w3m/sb-bbc
/usr/share/emacs/site-lisp/w3m/w3m-search hides
/usr/local/share/emacs/site-lisp/w3m/w3m-search
/usr/share/emacs/site-lisp/w3m/sb-impress hides
/usr/local/share/emacs/site-lisp/w3m/sb-impress
/usr/share/emacs/site-lisp/w3m/sb-jpilot hides
/usr/local/share/emacs/site-lisp/w3m/sb-jpilot
/usr/share/emacs/site-lisp/w3m/sb-cnet hides
/usr/local/share/emacs/site-lisp/w3m/sb-cnet
/usr/share/emacs/site-lisp/w3m/sb-atmarkit hides
/usr/local/share/emacs/site-lisp/w3m/sb-atmarkit
/usr/share/emacs/site-lisp/w3m/sb-chise hides
/usr/local/share/emacs/site-lisp/w3m/sb-chise
/usr/share/emacs/site-lisp/w3m/w3m-tabmenu hides
/usr/local/share/emacs/site-lisp/w3m/w3m-tabmenu
/usr/share/emacs/site-lisp/w3m/sb-lump hides
/usr/local/share/emacs/site-lisp/w3m/sb-lump
/usr/share/emacs/site-lisp/w3m/sb-atom-hash hides
/usr/local/share/emacs/site-lisp/w3m/sb-atom-hash
/usr/share/emacs/site-lisp/w3m/sb-mew hides
/usr/local/share/emacs/site-lisp/w3m/sb-mew
/usr/share/emacs/site-lisp/w3m/sb-multi hides
/usr/local/share/emacs/site-lisp/w3m/sb-multi
/usr/share/emacs/site-lisp/w3m/sb-arch-bluegate hides
/usr/local/share/emacs/site-lisp/w3m/sb-arch-bluegate
/usr/share/emacs/site-lisp/w3m/w3m-form hides
/usr/local/share/emacs/site-lisp/w3m/w3m-form
/usr/share/emacs/site-lisp/w3m/sb-plucker hides
/usr/local/share/emacs/site-lisp/w3m/sb-plucker
/usr/share/emacs/site-lisp/w3m/sb-welt-de hides
/usr/local/share/emacs/site-lisp/w3m/sb-welt-de
/usr/share/emacs/site-lisp/w3m/sb-asahi-mytown hides
/usr/local/share/emacs/site-lisp/w3m/sb-asahi-mytown
/usr/share/emacs/site-lisp/w3m/sb-linuxce-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-linuxce-jp
/usr/share/emacs/site-lisp/w3m/sb-nikkei hides
/usr/local/share/emacs/site-lisp/w3m/sb-nikkei
/usr/share/emacs/site-lisp/w3m/sb-glimpse hides
/usr/local/share/emacs/site-lisp/w3m/sb-glimpse
/usr/share/emacs/site-lisp/w3m/sb-pilot-mailsync hides
/usr/local/share/emacs/site-lisp/w3m/sb-pilot-mailsync
/usr/share/emacs/site-lisp/w3m/w3m-bookmark hides
/usr/local/share/emacs/site-lisp/w3m/w3m-bookmark
/usr/share/emacs/site-lisp/w3m/sb-sponichi hides
/usr/local/share/emacs/site-lisp/w3m/sb-sponichi
/usr/share/emacs/site-lisp/w3m/sb-namazu hides
/usr/local/share/emacs/site-lisp/w3m/sb-namazu
/usr/share/emacs/site-lisp/w3m/sb-lotusex hides
/usr/local/share/emacs/site-lisp/w3m/sb-lotusex
/usr/share/emacs/site-lisp/w3m/octet hides
/usr/local/share/emacs/site-lisp/w3m/octet
/usr/share/emacs/site-lisp/w3m/bookmark-w3m hides
/usr/local/share/emacs/site-lisp/w3m/bookmark-w3m
/usr/share/emacs/site-lisp/w3m/sb-marc-aims hides
/usr/local/share/emacs/site-lisp/w3m/sb-marc-aims
/usr/share/emacs/site-lisp/w3m/sb-tdiary hides
/usr/local/share/emacs/site-lisp/w3m/sb-tdiary
/usr/share/emacs/site-lisp/w3m/w3m-bug hides
/usr/local/share/emacs/site-lisp/w3m/w3m-bug
/usr/share/emacs/site-lisp/w3m/sb-mozilla-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-mozilla-jp
/usr/share/emacs/site-lisp/w3m/mime-w3m hides
/usr/local/share/emacs/site-lisp/w3m/mime-w3m
/usr/share/emacs/site-lisp/w3m/sb-macosx-jp hides
/usr/local/share/emacs/site-lisp/w3m/sb-macosx-jp
/usr/share/emacs/site-lisp/w3m/sb-spiegel hides
/usr/local/share/emacs/site-lisp/w3m/sb-spiegel
/usr/share/emacs/site-lisp/w3m/sb-pilot-link hides
/usr/local/share/emacs/site-lisp/w3m/sb-pilot-link
/usr/share/emacs/site-lisp/w3m/sb-emacswiki hides
/usr/local/share/emacs/site-lisp/w3m/sb-emacswiki
/usr/share/emacs/site-lisp/w3m/sb-w3m-dev hides
/usr/local/share/emacs/site-lisp/w3m/sb-w3m-dev
/usr/share/emacs/site-lisp/w3m/sb-palmfan hides
/usr/local/share/emacs/site-lisp/w3m/sb-palmfan
/usr/share/emacs/site-lisp/w3m/sb-rss hides
/usr/local/share/emacs/site-lisp/w3m/sb-rss
/usr/share/emacs/site-lisp/w3m/sb-infoshop hides
/usr/local/share/emacs/site-lisp/w3m/sb-infoshop
/usr/share/emacs/site-lisp/w3m/sb-msdn hides
/usr/local/share/emacs/site-lisp/w3m/sb-msdn
/usr/share/emacs/site-lisp/w3m/sb-asahi hides
/usr/local/share/emacs/site-lisp/w3m/sb-asahi
/usr/share/emacs/site-lisp/w3m/sb-tigris hides
/usr/local/share/emacs/site-lisp/w3m/sb-tigris
/usr/share/emacs/site-lisp/w3m/w3m-filter hides
/usr/local/share/emacs/site-lisp/w3m/w3m-filter
/usr/share/emacs/site-lisp/w3m/sb-texfaq hides
/usr/local/share/emacs/site-lisp/w3m/sb-texfaq
/usr/share/emacs/site-lisp/w3m/mew-shimbun hides
/usr/local/share/emacs/site-lisp/w3m/mew-shimbun
/usr/share/emacs/site-lisp/w3m/w3m-namazu hides
/usr/local/share/emacs/site-lisp/w3m/w3m-namazu
/usr/share/emacs/site-lisp/w3m/sb-wiki hides
/usr/local/share/emacs/site-lisp/w3m/sb-wiki
/usr/share/emacs/site-lisp/w3m/sb-tdiary-ml hides
/usr/local/share/emacs/site-lisp/w3m/sb-tdiary-ml
/usr/share/emacs/site-lisp/w3m/sb-kde hides
/usr/local/share/emacs/site-lisp/w3m/sb-kde
/usr/share/emacs/site-lisp/w3m/sb-geocrawler hides
/usr/local/share/emacs/site-lisp/w3m/sb-geocrawler
/usr/share/emacs/site-lisp/w3m/w3m-ucs hides
/usr/local/share/emacs/site-lisp/w3m/w3m-ucs
/usr/share/emacs/site-lisp/w3m/shimbun hides
/usr/local/share/emacs/site-lisp/w3m/shimbun
/usr/share/emacs/site-lisp/w3m/nnshimbun hides
/usr/local/share/emacs/site-lisp/w3m/nnshimbun
/usr/share/emacs/site-lisp/w3m/sb-vinelinux hides
/usr/local/share/emacs/site-lisp/w3m/sb-vinelinux
/usr/share/emacs/site-lisp/w3m/w3m-mail hides
/usr/local/share/emacs/site-lisp/w3m/w3m-mail
/usr/share/emacs/site-lisp/w3m/w3m-ccl hides
/usr/local/share/emacs/site-lisp/w3m/w3m-ccl
/usr/share/emacs/site-lisp/w3m/sb-zeit-de hides
/usr/local/share/emacs/site-lisp/w3m/sb-zeit-de
/usr/share/emacs/site-lisp/w3m/sb-sueddeutsche-de hides
/usr/local/share/emacs/site-lisp/w3m/sb-sueddeutsche-de
/usr/share/emacs/site-lisp/w3m/sb-tcup hides
/usr/local/share/emacs/site-lisp/w3m/sb-tcup
/usr/share/emacs/site-lisp/w3m/sb-the-register hides
/usr/local/share/emacs/site-lisp/w3m/sb-the-register
/usr/share/emacs/site-lisp/w3m/sb-orca hides
/usr/local/share/emacs/site-lisp/w3m/sb-orca
/usr/share/emacs/site-lisp/w3m/w3m-symbol hides
/usr/local/share/emacs/site-lisp/w3m/w3m-symbol
/usr/share/emacs/site-lisp/w3m/sb-nikkangendai hides
/usr/local/share/emacs/site-lisp/w3m/sb-nikkangendai
/usr/share/emacs/site-lisp/w3m/sb-makanai hides
/usr/local/share/emacs/site-lisp/w3m/sb-makanai
/usr/share/emacs/site-lisp/w3m/w3m-fb hides
/usr/local/share/emacs/site-lisp/w3m/w3m-fb
/usr/share/emacs/site-lisp/w3m/sb-rakuten hides
/usr/local/share/emacs/site-lisp/w3m/sb-rakuten
/usr/share/emacs/site-lisp/w3m/sb-elips hides
/usr/local/share/emacs/site-lisp/w3m/sb-elips
/usr/share/emacs/site-lisp/w3m/sb-jpo hides
/usr/local/share/emacs/site-lisp/w3m/sb-jpo
/usr/share/emacs/site-lisp/w3m/mew-w3m hides
/usr/local/share/emacs/site-lisp/w3m/mew-w3m
/usr/share/emacs/site-lisp/w3m/sb-netbsd hides
/usr/local/share/emacs/site-lisp/w3m/sb-netbsd
/home/owinebar/.emacs.d/elpa-30/jsonrpc-1.0.16/jsonrpc hides
/usr/local/share/emacs/30.0.50/lisp/jsonrpc
/home/owinebar/.emacs.d/elpa-30/pcmpl-git-20170121.59/pcmpl-git hides
/usr/local/share/emacs/30.0.50/lisp/pcmpl-git
/home/owinebar/.emacs.d/elpa-30/svg-1.1/svg hides
/usr/local/share/emacs/30.0.50/lisp/svg
/home/owinebar/.emacs.d/elpa-30/sqlite-20201227.1822/sqlite hides
/usr/local/share/emacs/30.0.50/lisp/sqlite
/home/owinebar/.emacs.d/elpa-30/transient-20230209.2250/transient
hides /usr/local/share/emacs/30.0.50/lisp/transient
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package-ensure
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package-ensure
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package-diminish
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package-diminish
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package-bind-key
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package-bind-key
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package-delight
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package-delight
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package-lint
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package-lint
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package-core
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package-core
/home/owinebar/.emacs.d/elpa-30/use-package-20230203.2004/use-package-jump
hides /usr/local/share/emacs/30.0.50/lisp/use-package/use-package-jump
/home/owinebar/.emacs.d/elpa-30/bind-key-20230203.2004/bind-key hides
/usr/local/share/emacs/30.0.50/lisp/use-package/bind-key
/home/owinebar/.emacs.d/elpa-30/flymake-1.2.2/flymake hides
/usr/local/share/emacs/30.0.50/lisp/progmodes/flymake
/home/owinebar/.emacs.d/elpa-30/python-0.28/python hides
/usr/local/share/emacs/30.0.50/lisp/progmodes/python
/home/owinebar/.emacs.d/elpa-30/xref-1.6.1/xref hides
/usr/local/share/emacs/30.0.50/lisp/progmodes/xref
/home/owinebar/.emacs.d/elpa-30/csharp-mode-20221126.2005/csharp-mode
hides /usr/local/share/emacs/30.0.50/lisp/progmodes/csharp-mode
/home/owinebar/.emacs.d/elpa-30/project-0.9.6/project hides
/usr/local/share/emacs/30.0.50/lisp/progmodes/project
/home/owinebar/.emacs.d/elpa-30/verilog-mode-2022.12.18.181110314/verilog-mode
hides /usr/local/share/emacs/30.0.50/lisp/progmodes/verilog-mode
/home/owinebar/.emacs.d/elpa-30/eglot-20221020.1010/eglot hides
/usr/local/share/emacs/30.0.50/lisp/progmodes/eglot
/home/owinebar/.emacs.d/elpa-30/flim-20230205.1423/sasl hides
/usr/local/share/emacs/30.0.50/lisp/net/sasl
/usr/local/share/emacs/site-lisp/semi/smime hides
/usr/local/share/emacs/30.0.50/lisp/gnus/smime
/home/owinebar/.emacs.d/elpa-30/eldoc-1.13.0/eldoc hides
/usr/local/share/emacs/30.0.50/lisp/emacs-lisp/eldoc
/home/owinebar/.emacs.d/elpa-30/seq-2.23/seq hides
/usr/local/share/emacs/30.0.50/lisp/emacs-lisp/seq
/home/owinebar/.emacs.d/elpa-30/map-3.3.1/map hides
/usr/local/share/emacs/30.0.50/lisp/emacs-lisp/map
/home/owinebar/.emacs.d/elpa-30/hierarchy-20190425.842/hierarchy hides
/usr/local/share/emacs/30.0.50/lisp/emacs-lisp/hierarchy
/usr/local/share/emacs/site-lisp/semi/pgg-pgp hides
/usr/local/share/emacs/30.0.50/lisp/obsolete/pgg-pgp
/usr/local/share/emacs/site-lisp/semi/pgg hides
/usr/local/share/emacs/30.0.50/lisp/obsolete/pgg
/usr/local/share/emacs/site-lisp/semi/pgg-pgp5 hides
/usr/local/share/emacs/30.0.50/lisp/obsolete/pgg-pgp5
/usr/local/share/emacs/site-lisp/semi/pgg-parse hides
/usr/local/share/emacs/30.0.50/lisp/obsolete/pgg-parse
/usr/local/share/emacs/site-lisp/semi/pgg-gpg hides
/usr/local/share/emacs/30.0.50/lisp/obsolete/pgg-gpg
/usr/local/share/emacs/site-lisp/semi/pgg-def hides
/usr/local/share/emacs/30.0.50/lisp/obsolete/pgg-def
Features:
(shadow sort mail-extr emacsbug message yank-media rfc822 mml mml-sec
epa derived epg rfc6068 epg-config gnus-util mm-decode mm-bodies
mm-encode mailabbrev gmm-utils mailheader sendmail mail-utils mule-util
minibuffer-complete-cycle smex time-date overseer pkg-info url-http
url-auth mail-parse rfc2231 rfc2047 rfc2045 mm-util ietf-drums
mail-prsvr url-gw nsm puny epl package browse-url url url-proxy
url-privacy url-expand url-methods url-history url-cookie
generate-lisp-file url-domsuf url-util mailcap url-handlers url-parse
auth-source password-cache url-vars f f-shortdoc erefactor flymake-proc
flymake warnings font-latex tex dbus ido-completing-read+ memoize
cus-edit cus-start icons minibuf-eldef ido xml crm texmathp
semantic/mru-bookmark semantic/db-mode semantic/decorate/mode
semantic/decorate pulse semantic/idle semantic/analyze semantic/sort
semantic/scope semantic/analyze/fcn semantic/db semantic/format
semantic/tag-ls semantic/find semantic/ctxt company-oddmuse
company-keywords company-etags etags fileloop generator company-gtags
company-dabbrev-code company-dabbrev company-files company-clang
company-capf company-cmake company-semantic company-template
company-bbdb ef-frost-theme ef-themes smart-mode-line-light-theme
vertico-posframe vertico semantic/util-modes semantic/util semantic pp
semantic/tag semantic/lex semantic/fw mode-local find-func mode-icons
emojify apropos tar-mode arc-mode archive-mode json map ht ivy-rich
ivy-posframe easy-mmode origami origami-parsers s hl-line ede/speedbar
ede/files ede ede/detect ede/base ede/source eieio-speedbar speedbar
ezimage dframe eieio-custom wid-edit cedet dash counsel-projectile
projectile lisp-mnt grep ibuf-ext ibuffer ibuffer-loaddefs thingatpt
counsel xdg xref project dired dired-loaddefs compile
text-property-search comint ansi-osc ansi-color swiper cl-extra
help-mode ivy flx delsel ring ivy-faces ivy-overlay colir color
company-tng company-quickhelp pos-tip company-posframe posframe company
pcase subr-x cus-load windmove xfonts rmailgen preview-latex w3m-load
ispell info hl-block-mode-autoloads annotate-autoloads
racket-mode-autoloads auto-yasnippet-autoloads org-ivy-search-autoloads
js-import-autoloads package-build-autoloads vterm-autoloads
substitute-autoloads cargo-mode-autoloads tabspaces-autoloads
rustic-autoloads evil-cleverparens-autoloads chronometrist-autoloads
all-the-icons all-the-icons-faces data-material data-weathericons
data-octicons data-fileicons data-faicons data-alltheicons
bash-completion-autoloads ekg-autoloads triples-autoloads
marginalia-autoloads flymake-sqlfluff-autoloads citar-autoloads
consult-flycheck-autoloads buffer-sets-autoloads consult-lsp-autoloads
org-ref-autoloads all-the-icons-ivy-rich-autoloads flim-autoloads
paperless-autoloads systemd-autoloads cmake-mode-autoloads
diffed-autoloads evil-visual-mark-mode-autoloads
org-roam-bibtex-autoloads consult-org-roam-autoloads
language-id-autoloads ergoemacs-mode-autoloads use-package-autoloads
embark-consult-autoloads rx realgud-lldb-autoloads web-mode-autoloads
call-graph-autoloads pcsv-autoloads org-modern-autoloads tide-autoloads
orderless-autoloads cape-autoloads evil-matchit-autoloads
csv-mode-autoloads modus-themes-autoloads doom-modeline-autoloads
graphviz-dot-mode-autoloads tree-sitter-langs-autoloads helm-autoloads
helm-core-autoloads advice embark-autoloads caml-autoloads
elsa-autoloads hl-prog-extra-autoloads auctex-autoloads tex-site
biblio-autoloads biblio-core-autoloads idle-highlight-mode-autoloads cl
yasnippet-snippets-autoloads websocket-autoloads git-link-autoloads
sml-mode-autoloads async-autoloads ede/auto eieio-base cl-seq eieio
byte-opt bytecomp byte-compile eieio-core cl-macs gv cl-loaddefs cl-lib
bind-key-autoloads consult-eglot-autoloads consult-autoloads
realgud-recursive-autoloads slime-autoloads flycheck-autoloads
cider-autoloads evil-autoloads lsp-mode-autoloads company-autoloads
elpa-mirror-autoloads magit-autoloads magit-section-autoloads
git-commit-autoloads with-editor-autoloads transient-autoloads
compat-autoloads rmc iso-transl tooltip cconv eldoc paren electric
uniquify ediff-hook vc-hooks lisp-float-type avl-tree-core elisp-mode
mwheel term/x-win x-win term/common-win x-dnd tool-bar dnd fontset image
regexp-opt fringe tabulated-list replace newcomment text-mode lisp-mode
prog-mode register page tab-bar menu-bar rfn-eshadow isearch easymenu
timer select scroll-bar mouse jit-lock font-lock syntax font-core
term/tty-colors frame minibuffer nadvice seq simple cl-generic
indonesian philippine cham georgian utf-8-lang misc-lang vietnamese
tibetan thai tai-viet lao korean japanese eucjp-ms cp51932 hebrew greek
romanian slovak czech european ethiopic indian cyrillic chinese
composite emoji-zwj charscript charprop case-table epa-hook
jka-cmpr-hook help abbrev obarray oclosure cl-preloaded button loaddefs
theme-loaddefs faces cus-face macroexp files window text-properties
overlay sha1 md5 base64 format env code-pages mule custom widget keymap
hashtable-print-readable backquote threads xwidget-internal dbusbind
inotify lcms2 dynamic-setting system-font-setting font-render-setting
cairo move-toolbar gtk x-toolkit xinput2 x multi-tty
make-network-process emacs)
Memory information:
((conses 16 346976 23660)
(symbols 48 35342 0)
(strings 32 106167 3883)
(string-bytes 1 3860030)
(vectors 16 43792)
(vector-slots 8 724172 17725)
(floats 8 597 238)
(intervals 56 490 0)
(buffers 984 13))
[-- Attachment #2: emacs-custom-startup-redump.patch --]
[-- Type: text/x-patch, Size: 73357 bytes --]
diff --git a/lisp/custom.el b/lisp/custom.el
index fa77e5c2c56..1cd866e236f 100644
--- a/lisp/custom.el
+++ b/lisp/custom.el
@@ -34,7 +34,16 @@
;;; Code:
(require 'widget)
-
+;;(require 'transitive-closure)
+(declare-function tc-reverse-rooted-graph
+ "emacs-lisp/transitive-closure"
+ (nodes edges &optional roots))
+(declare-function tc-graph-reachable
+ "emacs-lisp/transitive-closure"
+ (tcg &optional v))
+(declare-function tc-graph-ordering
+ "emacs-lisp/transitive-closure"
+ (tcg))
(defvar custom-define-hook nil
;; Customize information for this option is in `cus-edit.el'.
"Hook called after defining each customize option.")
@@ -152,11 +161,12 @@ custom-initialize-delay
;; This seemed to be at least as good as setting it to an arbitrary
;; value like nil (evaluating `value' is not an option because it
;; may have undesirable side-effects).
- (if (listp custom-delayed-init-variables)
- (push symbol custom-delayed-init-variables)
- ;; In case this is called after startup, there is no "later" to which to
- ;; delay it, so initialize it "normally" (bug#47072).
- (custom-initialize-reset symbol value)))
+ (put symbol 'custom-implied-dependencies custom-delayed-init-variables)
+ (if (not (listp custom-delayed-init-variables))
+ ;; In case this is called after startup, there is no "later" to which to
+ ;; delay it, so initialize it "normally" (bug#47072).
+ (custom-initialize-reset symbol value)
+ (push symbol custom-delayed-init-variables)))
(defun custom-declare-variable (symbol default doc &rest args)
"Like `defcustom', but SYMBOL and DEFAULT are evaluated as normal arguments.
@@ -832,6 +842,23 @@ custom-reevaluate-setting
(eval (car (or (get symbol 'saved-value)
(get symbol 'standard-value))))))
+(defun custom-runtime-setting (symbol)
+ "Reset the value of SYMBOL by re-evaluating standard value.
+Use the :set function to do so. This is useful for customizable options
+that are defined before their standard value can really be computed.
+E.g. dumped variables whose default depends on run-time information."
+ ;; We are initializing
+ ;; the variable, and normally any :set function would not apply.
+ ;; For custom-initialize-delay, however, it is documented that "the
+ ;; (delayed) initialization is performed with the :set function".
+ ;; This is needed by eg global-font-lock-mode, which uses
+ ;; custom-initialize-delay but needs the :set function custom-set-minor-mode
+ ;; to also run during initialization. So, long story short, we
+ ;; always do the funcall step, even if symbol was not bound before.
+ (funcall (or (get symbol 'custom-set) #'set-default)
+ symbol
+ (eval (car (get symbol 'standard-value)))))
+
\f
;;; Custom Themes
@@ -1776,6 +1803,51 @@ custom--add-custom-loads
(push load loads)))
(put symbol 'custom-loads loads))
+(defvar custom--reset-at-startup-vars nil)
+(defvar custom--restore-after-reset-vars nil)
+(defun custom--startup-calculate-initializations ()
+ (setq custom--reset-at-startup-vars nil)
+ (setq custom--restore-after-reset-vars nil)
+ (unless (listp custom-delayed-init-variables)
+ (let (vars deps saved tcg ordering explicit-startup startup-reachable)
+ (mapatoms
+ (lambda (s) (when (get s 'custom-type) (push s vars))))
+ (setq explicit-startup
+ (seq-filter (lambda (v)
+ (get v 'custom-implied-dependencies))
+ vars))
+ (setq deps
+ (mapcar (lambda (v)
+ (let ((ds (get v 'custom-dependencies))
+ (imp (get v 'custom-implied-dependencies)))
+ `(,v ,@(seq-union ds imp))))
+ vars))
+ (setq tcg (tc-reverse-rooted-graph vars deps explicit-startup))
+ (setq startup-reachable (tc-graph-reachable tcg))
+ (setq ordering (tc-graph-ordering tcg))
+ (setq custom--reset-at-startup-vars
+ (apply #'nconc (append ordering nil)))
+ (setq custom--restore-after-reset-vars
+ (seq-filter (lambda (v)
+ (and (get v 'saved-value)))
+ startup-reachable)))))
+
+(defun custom-do-startup-settings ()
+ (let ((ordering custom--reset-at-startup-vars)
+ (saved custom--restore-after-reset-vars)
+ var set-var)
+ (mapc (lambda (v)
+ (when (boundp v)
+ (makunbound v)))
+ custom--reset-at-startup-vars)
+ (while ordering
+ (custom-runtime-setting (pop ordering)))
+ (while saved
+ (custom-reevaluate-setting (pop saved)))))
+
+(add-hook 'after-pdump-load-hook
+ #'custom--startup-calculate-initializations)
+
(provide 'custom)
;;; custom.el ends here
diff --git a/lisp/emacs-lisp/avl-tree-core.el b/lisp/emacs-lisp/avl-tree-core.el
new file mode 100644
index 00000000000..8a8d5f34426
--- /dev/null
+++ b/lisp/emacs-lisp/avl-tree-core.el
@@ -0,0 +1,675 @@
+;;; avl-tree-core.el --- balanced binary trees, AVL-trees -*- lexical-binding:t -*-
+
+;; Copyright (C) 1995, 2007-2023 Free Software Foundation, Inc.
+
+;; Author: Per Cederqvist <ceder@lysator.liu.se>
+;; Inge Wallin <inge@lysator.liu.se>
+;; Thomas Bellman <bellman@lysator.liu.se>
+;; Toby Cubitt <toby-predictive@dr-qubit.org>
+;; Maintainer: emacs-devel@gnu.org
+;; Created: 10 May 1991
+;; Keywords: extensions, data structures, AVL, tree
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; An AVL tree is a self-balancing binary tree. As such, inserting,
+;; deleting, and retrieving data from an AVL tree containing n elements
+;; is O(log n). It is somewhat more rigidly balanced than other
+;; self-balancing binary trees (such as red-black trees and AA trees),
+;; making insertion slightly slower, deletion somewhat slower, and
+;; retrieval somewhat faster (the asymptotic scaling is of course the
+;; same for all types). Thus it may be a good choice when the tree will
+;; be relatively static, i.e. data will be retrieved more often than
+;; they are modified.
+;;
+;; Internally, a tree consists of two elements, the root node and the
+;; comparison function. The actual tree has a dummy node as its root
+;; with the real root in the left pointer, which allows the root node to
+;; be treated on a par with all other nodes.
+;;
+;; Each node of the tree consists of one data element, one left
+;; sub-tree, one right sub-tree, and a balance count. The latter is the
+;; difference in depth of the left and right sub-trees.
+;;
+;; The functions with names of the form "avl-tree--" are intended for
+;; internal use only.
+
+;; avl-tree-core omits the iterator functionality to allow
+;; inclusion in loadup.el
+;;
+
+;;; Code:
+
+(eval-when-compile (require 'cl-lib))
+(eval-when-compile (require 'cl-extra))
+
+
+;; ================================================================
+;;; Internal functions and macros for use in the AVL tree package
+
+
+;; ----------------------------------------------------------------
+;; Functions and macros handling an AVL tree.
+
+(cl-defstruct (avl-tree-
+ ;; A tagged list is the pre-defstruct representation.
+ ;; (:type list)
+ :named
+ (:constructor nil)
+ (:constructor avl-tree--create (cmpfun))
+ (:predicate avl-tree-p)
+ (:copier nil))
+ (dummyroot (avl-tree--node-create nil nil nil 0))
+ cmpfun)
+
+(defmacro avl-tree--root (tree)
+ "Return the root node for an AVL TREE. INTERNAL USE ONLY."
+ `(avl-tree--node-left (avl-tree--dummyroot ,tree)))
+
+;; ----------------------------------------------------------------
+;; Functions and macros handling an AVL tree node.
+
+(cl-defstruct (avl-tree--node
+ ;; We force a representation without tag so it matches the
+ ;; pre-defstruct representation. Also we use the underlying
+ ;; representation in the implementation of
+ ;; avl-tree--node-branch.
+ (:type vector)
+ (:constructor nil)
+ (:constructor avl-tree--node-create (left right data balance))
+ (:copier nil))
+ left right data balance)
+
+
+(defalias 'avl-tree--node-branch #'aref
+ ;; This implementation is efficient but breaks the defstruct
+ ;; abstraction. An alternative could be (funcall (aref [avl-tree-left
+ ;; avl-tree-right avl-tree-data] branch) node)
+ "Get value of a branch of a node.
+NODE is the node, and BRANCH is the branch.
+0 for left pointer, 1 for right pointer and 2 for the data.
+\n(fn BRANCH NODE)")
+
+
+;; The funcall/aref trick wouldn't work for the setf method, unless we
+;; tried to access the underlying setter function, but this wouldn't be
+;; portable either.
+(gv-define-simple-setter avl-tree--node-branch aset)
+
+
+
+;; ----------------------------------------------------------------
+;; Convenience macros
+
+(defmacro avl-tree--switch-dir (dir)
+ "Return opposite direction to DIR (0 = left, 1 = right)."
+ `(- 1 ,dir))
+
+(defmacro avl-tree--dir-to-sign (dir)
+ "Convert direction DIR (0,1) to sign factor (-1,+1)."
+ `(1- (* 2 ,dir)))
+
+(defmacro avl-tree--sign-to-dir (dir)
+ "Convert sign factor in DIR (-x,+x) to direction (0,1)."
+ `(if (< ,dir 0) 0 1))
+
+
+;; ----------------------------------------------------------------
+;; Deleting data
+
+(defun avl-tree--del-balance (node branch dir)
+ "Rebalance a tree after deleting a NODE.
+The deletion was done from the left (DIR=0) or right (DIR=1) sub-tree
+of the left (BRANCH=0) or right (BRANCH=1) child of NODE.
+Return t if the height of the tree has shrunk."
+ ;; (or is it vice-versa for BRANCH?)
+ (let ((br (avl-tree--node-branch node branch))
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
+ p1 b1 p2 b2)
+ (cond
+ ((> (* sgn (avl-tree--node-balance br)) 0)
+ (setf (avl-tree--node-balance br) 0)
+ t)
+
+ ((= (avl-tree--node-balance br) 0)
+ (setf (avl-tree--node-balance br) (- sgn))
+ nil)
+
+ (t
+ ;; Rebalance.
+ (setq p1 (avl-tree--node-branch br opp)
+ b1 (avl-tree--node-balance p1))
+ (if (<= (* sgn b1) 0)
+ ;; Single rotation.
+ (progn
+ (setf (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p1 dir) br
+ (avl-tree--node-branch node branch) p1)
+ (if (= 0 b1)
+ (progn
+ (setf (avl-tree--node-balance br) (- sgn)
+ (avl-tree--node-balance p1) sgn)
+ nil) ; height hasn't changed
+ (setf (avl-tree--node-balance br) 0)
+ (setf (avl-tree--node-balance p1) 0)
+ t)) ; height has changed
+
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 dir)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) p1
+ (avl-tree--node-branch br opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) br
+ (avl-tree--node-balance br)
+ (if (< (* sgn b2) 0) sgn 0)
+ (avl-tree--node-balance p1)
+ (if (> (* sgn b2) 0) (- sgn) 0)
+ (avl-tree--node-branch node branch) p2
+ (avl-tree--node-balance p2) 0)
+ t)))))
+
+(defun avl-tree--do-del-internal (node branch q)
+ (let ((br (avl-tree--node-branch node branch)))
+ (if (avl-tree--node-right br)
+ (if (avl-tree--do-del-internal br 1 q)
+ (avl-tree--del-balance node branch 1))
+ (setf (avl-tree--node-data q) (avl-tree--node-data br)
+ (avl-tree--node-branch node branch)
+ (avl-tree--node-left br))
+ t)))
+
+(defun avl-tree--do-delete (cmpfun root branch data test nilflag)
+ "Delete DATA from BRANCH of node ROOT.
+\(See `avl-tree-delete' for TEST and NILFLAG).
+
+Return cons cell (SHRUNK . DATA), where SHRUNK is t if the
+height of the tree has shrunk and nil otherwise, and DATA is
+the related data."
+ (let ((br (avl-tree--node-branch root branch)))
+ (cond
+ ;; DATA not in tree.
+ ((null br)
+ (cons nil nilflag))
+
+ ((funcall cmpfun data (avl-tree--node-data br))
+ (let ((ret (avl-tree--do-delete cmpfun br 0 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 0))
+ (cdr ret))))
+
+ ((funcall cmpfun (avl-tree--node-data br) data)
+ (let ((ret (avl-tree--do-delete cmpfun br 1 data test nilflag)))
+ (cons (if (car ret) (avl-tree--del-balance root branch 1))
+ (cdr ret))))
+
+ (t ; Found it.
+ ;; if it fails TEST, do nothing
+ (if (and test (not (funcall test (avl-tree--node-data br))))
+ (cons nil nilflag)
+ (cond
+ ((null (avl-tree--node-right br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-left br))
+ (cons t (avl-tree--node-data br)))
+
+ ((null (avl-tree--node-left br))
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-right br))
+ (cons t (avl-tree--node-data br)))
+
+ (t
+ (if (avl-tree--do-del-internal br 0 br)
+ (cons (avl-tree--del-balance root branch 0)
+ (avl-tree--node-data br))
+ (cons nil (avl-tree--node-data br))))
+ ))))))
+
+
+
+;; ----------------------------------------------------------------
+;; Entering data
+
+(defun avl-tree--enter-balance (node branch dir)
+ "Rebalance tree after insertion of NODE.
+NODE was inserted into the left (DIR=0) or right (DIR=1) sub-tree
+of the left (BRANCH=0) or right (BRANCH=1) child of NODE.
+Return t if the height of the tree has grown."
+ (let ((br (avl-tree--node-branch node branch))
+ ;; opposite direction: 0,1 -> 1,0
+ (opp (avl-tree--switch-dir dir))
+ ;; direction 0,1 -> sign factor -1,+1
+ (sgn (avl-tree--dir-to-sign dir))
+ p1 p2 b2)
+ (cond
+ ((< (* sgn (avl-tree--node-balance br)) 0)
+ (setf (avl-tree--node-balance br) 0)
+ nil)
+
+ ((= (avl-tree--node-balance br) 0)
+ (setf (avl-tree--node-balance br) sgn)
+ t)
+
+ (t
+ ;; Tree has grown => Rebalance.
+ (setq p1 (avl-tree--node-branch br dir))
+ (if (> (* sgn (avl-tree--node-balance p1)) 0)
+ ;; Single rotation.
+ (progn
+ (setf (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p1 opp))
+ (setf (avl-tree--node-branch p1 opp) br)
+ (setf (avl-tree--node-balance br) 0)
+ (setf (avl-tree--node-branch node branch) p1))
+
+ ;; Double rotation.
+ (setf p2 (avl-tree--node-branch p1 opp)
+ b2 (avl-tree--node-balance p2)
+ (avl-tree--node-branch p1 opp)
+ (avl-tree--node-branch p2 dir)
+ (avl-tree--node-branch p2 dir) p1
+ (avl-tree--node-branch br dir)
+ (avl-tree--node-branch p2 opp)
+ (avl-tree--node-branch p2 opp) br
+ (avl-tree--node-balance br)
+ (if (> (* sgn b2) 0) (- sgn) 0)
+ (avl-tree--node-balance p1)
+ (if (< (* sgn b2) 0) sgn 0)
+ (avl-tree--node-branch node branch) p2))
+ (setf (avl-tree--node-balance
+ (avl-tree--node-branch node branch))
+ 0)
+ nil))))
+
+(defun avl-tree--do-enter (cmpfun root branch data &optional updatefun)
+ "Enter DATA in BRANCH of ROOT node.
+\(See `avl-tree-enter' for UPDATEFUN).
+
+Return cons cell (GREW . DATA), where GREW is t if height
+of tree ROOT has grown and nil otherwise, and DATA is the
+inserted data."
+ (let ((br (avl-tree--node-branch root branch)))
+ (cond
+ ((null br)
+ ;; Data not in tree, insert it.
+ (setf (avl-tree--node-branch root branch)
+ (avl-tree--node-create nil nil data 0))
+ (cons t data))
+
+ ((funcall cmpfun data (avl-tree--node-data br))
+ (let ((ret (avl-tree--do-enter cmpfun br 0 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 0))
+ (cdr ret))))
+
+ ((funcall cmpfun (avl-tree--node-data br) data)
+ (let ((ret (avl-tree--do-enter cmpfun br 1 data updatefun)))
+ (cons (and (car ret) (avl-tree--enter-balance root branch 1))
+ (cdr ret))))
+
+ ;; Data already in tree, update it.
+ (t
+ (let ((newdata
+ (if updatefun
+ (funcall updatefun data (avl-tree--node-data br))
+ data)))
+ (if (or (funcall cmpfun newdata data)
+ (funcall cmpfun data newdata))
+ (error "avl-tree-enter: Updated data does not match existing data"))
+ (setf (avl-tree--node-data br) newdata)
+ (cons nil newdata)) ; return value
+ ))))
+
+(defun avl-tree--check (tree)
+ "Check the balance of TREE."
+ (avl-tree--check-node (avl-tree--root tree)))
+(defun avl-tree--check-node (node)
+ (if (null node) 0
+ (let ((dl (avl-tree--check-node (avl-tree--node-left node)))
+ (dr (avl-tree--check-node (avl-tree--node-right node))))
+ (cl-assert (= (- dr dl) (avl-tree--node-balance node)))
+ (1+ (max dl dr)))))
+
+;; ----------------------------------------------------------------
+
+
+;;; INTERNAL USE ONLY
+(defun avl-tree--mapc (map-function root dir)
+ "Apply MAP-FUNCTION to all nodes in the tree starting with ROOT.
+The function is applied in-order, either ascending (DIR=0) or
+descending (DIR=1).
+
+Note: MAP-FUNCTION is applied to the node and not to the data
+itself."
+ (let ((node root)
+ (stack nil)
+ (go-dir t))
+ (push nil stack)
+ (while node
+ (if (and go-dir
+ (avl-tree--node-branch node dir))
+ ;; Do the DIR subtree first.
+ (progn
+ (push node stack)
+ (setq node (avl-tree--node-branch node dir)))
+ ;; Apply the function...
+ (funcall map-function node)
+ ;; and do the opposite subtree.
+ (setq node (if (setq go-dir (avl-tree--node-branch
+ node (avl-tree--switch-dir dir)))
+ (avl-tree--node-branch
+ node (avl-tree--switch-dir dir))
+ (pop stack)))))))
+
+;;; INTERNAL USE ONLY
+(defun avl-tree--do-copy (root)
+ "Copy the AVL tree wiath ROOT as root.
+This function is highly recursive."
+ (if (null root)
+ nil
+ (avl-tree--node-create
+ (avl-tree--do-copy (avl-tree--node-left root))
+ (avl-tree--do-copy (avl-tree--node-right root))
+ (avl-tree--node-data root)
+ (avl-tree--node-balance root))))
+
+(cl-defstruct (avl-tree--stack
+ (:constructor nil)
+ (:constructor avl-tree--stack-create
+ (tree &optional reverse
+ &aux
+ (store
+ (if (avl-tree-empty tree)
+ nil
+ (list (avl-tree--root tree))))))
+ (:copier nil))
+ reverse store)
+
+(defalias 'avl-tree-stack-p #'avl-tree--stack-p
+ "Return t if OBJ is an avl-tree-stack, nil otherwise.
+\n(fn OBJ)")
+
+(defun avl-tree--stack-repopulate (stack)
+ "Recursively push children of STACK onto the front.
+This pushes the children of the node at the head of STACK onto
+the front of STACK, until a leaf node is reached."
+ (let ((node (car (avl-tree--stack-store stack)))
+ (dir (if (avl-tree--stack-reverse stack) 1 0)))
+ (when node ; check for empty stack
+ (while (setq node (avl-tree--node-branch node dir))
+ (push node (avl-tree--stack-store stack))))))
+
+
+;; ================================================================
+;;; The public functions which operate on AVL trees.
+
+;; define public alias for constructors so that we can set docstring
+(defalias 'avl-tree-create #'avl-tree--create
+ "Create an empty AVL tree.
+COMPARE-FUNCTION is a function which takes two arguments, A and B,
+and returns non-nil if A is less than B, and nil otherwise.
+\n(fn COMPARE-FUNCTION)")
+
+(defalias 'avl-tree-compare-function #'avl-tree--cmpfun
+ "Return the comparison function for the AVL tree TREE.
+\n(fn TREE)")
+
+(defun avl-tree-empty (tree)
+ "Return t if AVL TREE is empty, otherwise return nil."
+ (null (avl-tree--root tree)))
+
+(defun avl-tree-enter (tree data &optional updatefun)
+ "Insert DATA into the AVL tree TREE.
+
+If an element that matches DATA (according to the tree's
+comparison function, see `avl-tree-create') already exists in
+TREE, it will be replaced by DATA by default.
+
+If UPDATEFUN is supplied and an element matching DATA already
+exists in TREE, UPDATEFUN is called with two arguments: DATA, and
+the matching element. Its return value replaces the existing
+element. This value *must* itself match DATA (and hence the
+pre-existing data), or an error will occur.
+
+Returns the new data."
+ (cdr (avl-tree--do-enter (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data updatefun)))
+
+(defun avl-tree-delete (tree data &optional test nilflag)
+ "Delete the element matching DATA from the AVL TREE.
+Matching uses the comparison function previously specified in
+`avl-tree-create' when TREE was created.
+
+Returns the deleted element, or nil if no matching element was
+found.
+
+Optional argument NILFLAG specifies a value to return instead of
+nil if nothing was deleted, so that this case can be
+distinguished from the case of a successfully deleted null
+element.
+
+If supplied, TEST specifies a test that a matching element must
+pass before it is deleted. If a matching element is found, it is
+passed as an argument to TEST, and is deleted only if the return
+value is non-nil."
+ (cdr (avl-tree--do-delete (avl-tree--cmpfun tree)
+ (avl-tree--dummyroot tree)
+ 0 data test nilflag)))
+
+
+(defun avl-tree-member (tree data &optional nilflag)
+ "Return the element in the AVL TREE which matches DATA.
+Matching uses the comparison function previously specified in
+`avl-tree-create' when TREE was created.
+
+If there is no such element in the tree, nil is returned.
+Optional argument NILFLAG specifies a value to return instead of nil
+in this case. This allows non-existent elements to be distinguished
+from a null element. (See also `avl-tree-member-p', which does this
+for you.)"
+ (let ((node (avl-tree--root tree))
+ (compare-function (avl-tree--cmpfun tree)))
+ (catch 'found
+ (while node
+ (cond
+ ((funcall compare-function data (avl-tree--node-data node))
+ (setq node (avl-tree--node-left node)))
+ ((funcall compare-function (avl-tree--node-data node) data)
+ (setq node (avl-tree--node-right node)))
+ (t (throw 'found (avl-tree--node-data node)))))
+ nilflag)))
+
+
+(defun avl-tree-member-p (tree data)
+ "Return t if an element matching DATA exists in the AVL TREE.
+Otherwise return nil. Matching uses the comparison function
+previously specified in `avl-tree-create' when TREE was created."
+ (let ((flag '(nil)))
+ (not (eq (avl-tree-member tree data flag) flag))))
+
+
+(defun avl-tree-map (fun tree &optional reverse)
+ "Modify all elements in the AVL TREE by applying function FUN.
+
+Each element is replaced by the return value of FUN applied to
+that element.
+
+FUN is applied to the elements in ascending order, or descending
+order if REVERSE is non-nil."
+ (avl-tree--mapc
+ (lambda (node)
+ (setf (avl-tree--node-data node)
+ (funcall fun (avl-tree--node-data node))))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
+
+
+(defun avl-tree-mapc (fun tree &optional reverse)
+ "Apply function FUN to all elements in AVL TREE, for side-effect only.
+
+FUNCTION is applied to the elements in ascending order, or
+descending order if REVERSE is non-nil."
+ (avl-tree--mapc
+ (lambda (node)
+ (funcall fun (avl-tree--node-data node)))
+ (avl-tree--root tree)
+ (if reverse 1 0)))
+
+
+(defun avl-tree-mapf
+ (fun combinator tree &optional reverse)
+ "Apply FUN to all elements in AVL TREE, combine results using COMBINATOR.
+
+The FUNCTION is applied and the results are combined in ascending
+order, or descending order if REVERSE is non-nil."
+ (let (avl-tree-mapf--accumulate)
+ (avl-tree--mapc
+ (lambda (node)
+ (setq avl-tree-mapf--accumulate
+ (funcall combinator
+ (funcall fun
+ (avl-tree--node-data node))
+ avl-tree-mapf--accumulate)))
+ (avl-tree--root tree)
+ (if reverse 0 1))
+ (nreverse avl-tree-mapf--accumulate)))
+
+
+(defun avl-tree-mapcar (fun tree &optional reverse)
+ "Apply FUN to all elements in AVL TREE, and make a list of the results.
+
+The function is applied and the list constructed in ascending
+order, or descending order if REVERSE is non-nil.
+
+Note that if you don't care about the order in which FUN is
+applied, just that the resulting list is in the correct order,
+then
+
+ (avl-tree-mapf function \\='cons tree (not reverse))
+
+is more efficient."
+ (nreverse (avl-tree-mapf fun 'cons tree reverse)))
+
+
+(defun avl-tree-first (tree)
+ "Return the first element in TREE, or nil if TREE is empty."
+ (let ((node (avl-tree--root tree)))
+ (when node
+ (while (avl-tree--node-left node)
+ (setq node (avl-tree--node-left node)))
+ (avl-tree--node-data node))))
+
+(defun avl-tree-last (tree)
+ "Return the last element in TREE, or nil if TREE is empty."
+ (let ((node (avl-tree--root tree)))
+ (when node
+ (while (avl-tree--node-right node)
+ (setq node (avl-tree--node-right node)))
+ (avl-tree--node-data node))))
+
+(defun avl-tree-copy (tree)
+ "Return a copy of the AVL TREE."
+ (let ((new-tree (avl-tree-create (avl-tree--cmpfun tree))))
+ (setf (avl-tree--root new-tree) (avl-tree--do-copy (avl-tree--root tree)))
+ new-tree))
+
+(defun avl-tree-flatten (tree)
+ "Return a sorted list containing all elements of TREE."
+ (let ((treelist nil))
+ (avl-tree--mapc
+ (lambda (node) (push (avl-tree--node-data node) treelist))
+ (avl-tree--root tree) 1)
+ treelist))
+
+(defun avl-tree-size (tree)
+ "Return the number of elements in TREE."
+ (let ((treesize 0))
+ (avl-tree--mapc
+ (lambda (_) (setq treesize (1+ treesize)))
+ (avl-tree--root tree) 0)
+ treesize))
+
+(defun avl-tree-clear (tree)
+ "Clear the AVL TREE."
+ (setf (avl-tree--root tree) nil))
+
+
+(defun avl-tree-stack (tree &optional reverse)
+ "Return an object that behaves like a sorted stack of all elements of TREE.
+
+If REVERSE is non-nil, the stack is sorted in reverse order.
+\(See also `avl-tree-stack-pop').
+
+Note that any modification to TREE *immediately* invalidates all
+avl-tree-stacks created before the modification (in particular,
+calling `avl-tree-stack-pop' will give unpredictable results).
+
+Operations on these objects are significantly more efficient than
+constructing a real stack with `avl-tree-flatten' and using
+standard stack functions. As such, they can be useful in
+implementing efficient algorithms of AVL trees. However, in cases
+where mapping functions `avl-tree-mapc', `avl-tree-mapcar' or
+`avl-tree-mapf' would be sufficient, it is better to use one of
+those instead."
+ (let ((stack (avl-tree--stack-create tree reverse)))
+ (avl-tree--stack-repopulate stack)
+ stack))
+
+
+(defun avl-tree-stack-pop (avl-tree-stack &optional nilflag)
+ "Pop the first element from AVL-TREE-STACK.
+\(See also `avl-tree-stack').
+
+Returns nil if the stack is empty, or NILFLAG if specified.
+\(The latter allows an empty stack to be distinguished from
+a null element stored in the AVL tree.)"
+ (let (node next)
+ (if (not (setq node (pop (avl-tree--stack-store avl-tree-stack))))
+ nilflag
+ (when (setq next
+ (avl-tree--node-branch
+ node
+ (if (avl-tree--stack-reverse avl-tree-stack) 0 1)))
+ (push next (avl-tree--stack-store avl-tree-stack))
+ (avl-tree--stack-repopulate avl-tree-stack))
+ (avl-tree--node-data node))))
+
+
+(defun avl-tree-stack-first (avl-tree-stack &optional nilflag)
+ "Return the first element of AVL-TREE-STACK, without removing it from stack.
+
+Returns nil if the stack is empty, or NILFLAG if specified.
+\(The latter allows an empty stack to be distinguished from
+a null element stored in the AVL tree.)"
+ (or (car (avl-tree--stack-store avl-tree-stack))
+ nilflag))
+
+
+(defun avl-tree-stack-empty-p (avl-tree-stack)
+ "Return t if AVL-TREE-STACK is empty, nil otherwise."
+ (null (avl-tree--stack-store avl-tree-stack)))
+
+
+(provide 'avl-tree-core)
+
+;;; avl-tree-core.el ends here
diff --git a/lisp/emacs-lisp/avl-tree.el b/lisp/emacs-lisp/avl-tree.el
index b42017d28fb..03f1bb072f7 100644
--- a/lisp/emacs-lisp/avl-tree.el
+++ b/lisp/emacs-lisp/avl-tree.el
@@ -27,644 +27,17 @@
;;; Commentary:
-;; An AVL tree is a self-balancing binary tree. As such, inserting,
-;; deleting, and retrieving data from an AVL tree containing n elements
-;; is O(log n). It is somewhat more rigidly balanced than other
-;; self-balancing binary trees (such as red-black trees and AA trees),
-;; making insertion slightly slower, deletion somewhat slower, and
-;; retrieval somewhat faster (the asymptotic scaling is of course the
-;; same for all types). Thus it may be a good choice when the tree will
-;; be relatively static, i.e. data will be retrieved more often than
-;; they are modified.
-;;
-;; Internally, a tree consists of two elements, the root node and the
-;; comparison function. The actual tree has a dummy node as its root
-;; with the real root in the left pointer, which allows the root node to
-;; be treated on a par with all other nodes.
-;;
-;; Each node of the tree consists of one data element, one left
-;; sub-tree, one right sub-tree, and a balance count. The latter is the
-;; difference in depth of the left and right sub-trees.
-;;
-;; The functions with names of the form "avl-tree--" are intended for
-;; internal use only.
+;; This provides avl-tree-core plus an adaptor for the iterator
+;; interface. Requiring the generator library also requires cl-lib,
+;; which is not allowed in loadup.el
;;; Code:
(eval-when-compile (require 'cl-lib))
+(require 'avl-tree-core)
(require 'generator)
-;; ================================================================
-;;; Internal functions and macros for use in the AVL tree package
-
-
-;; ----------------------------------------------------------------
-;; Functions and macros handling an AVL tree.
-
-(cl-defstruct (avl-tree-
- ;; A tagged list is the pre-defstruct representation.
- ;; (:type list)
- :named
- (:constructor nil)
- (:constructor avl-tree--create (cmpfun))
- (:predicate avl-tree-p)
- (:copier nil))
- (dummyroot (avl-tree--node-create nil nil nil 0))
- cmpfun)
-
-(defmacro avl-tree--root (tree)
- "Return the root node for an AVL TREE. INTERNAL USE ONLY."
- `(avl-tree--node-left (avl-tree--dummyroot ,tree)))
-
-;; ----------------------------------------------------------------
-;; Functions and macros handling an AVL tree node.
-
-(cl-defstruct (avl-tree--node
- ;; We force a representation without tag so it matches the
- ;; pre-defstruct representation. Also we use the underlying
- ;; representation in the implementation of
- ;; avl-tree--node-branch.
- (:type vector)
- (:constructor nil)
- (:constructor avl-tree--node-create (left right data balance))
- (:copier nil))
- left right data balance)
-
-
-(defalias 'avl-tree--node-branch #'aref
- ;; This implementation is efficient but breaks the defstruct
- ;; abstraction. An alternative could be (funcall (aref [avl-tree-left
- ;; avl-tree-right avl-tree-data] branch) node)
- "Get value of a branch of a node.
-NODE is the node, and BRANCH is the branch.
-0 for left pointer, 1 for right pointer and 2 for the data.
-\n(fn BRANCH NODE)")
-
-
-;; The funcall/aref trick wouldn't work for the setf method, unless we
-;; tried to access the underlying setter function, but this wouldn't be
-;; portable either.
-(gv-define-simple-setter avl-tree--node-branch aset)
-
-
-
-;; ----------------------------------------------------------------
-;; Convenience macros
-
-(defmacro avl-tree--switch-dir (dir)
- "Return opposite direction to DIR (0 = left, 1 = right)."
- `(- 1 ,dir))
-
-(defmacro avl-tree--dir-to-sign (dir)
- "Convert direction DIR (0,1) to sign factor (-1,+1)."
- `(1- (* 2 ,dir)))
-
-(defmacro avl-tree--sign-to-dir (dir)
- "Convert sign factor in DIR (-x,+x) to direction (0,1)."
- `(if (< ,dir 0) 0 1))
-
-
-;; ----------------------------------------------------------------
-;; Deleting data
-
-(defun avl-tree--del-balance (node branch dir)
- "Rebalance a tree after deleting a NODE.
-The deletion was done from the left (DIR=0) or right (DIR=1) sub-tree
-of the left (BRANCH=0) or right (BRANCH=1) child of NODE.
-Return t if the height of the tree has shrunk."
- ;; (or is it vice-versa for BRANCH?)
- (let ((br (avl-tree--node-branch node branch))
- ;; opposite direction: 0,1 -> 1,0
- (opp (avl-tree--switch-dir dir))
- ;; direction 0,1 -> sign factor -1,+1
- (sgn (avl-tree--dir-to-sign dir))
- p1 b1 p2 b2)
- (cond
- ((> (* sgn (avl-tree--node-balance br)) 0)
- (setf (avl-tree--node-balance br) 0)
- t)
-
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) (- sgn))
- nil)
-
- (t
- ;; Rebalance.
- (setq p1 (avl-tree--node-branch br opp)
- b1 (avl-tree--node-balance p1))
- (if (<= (* sgn b1) 0)
- ;; Single rotation.
- (progn
- (setf (avl-tree--node-branch br opp)
- (avl-tree--node-branch p1 dir)
- (avl-tree--node-branch p1 dir) br
- (avl-tree--node-branch node branch) p1)
- (if (= 0 b1)
- (progn
- (setf (avl-tree--node-balance br) (- sgn)
- (avl-tree--node-balance p1) sgn)
- nil) ; height hasn't changed
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance p1) 0)
- t)) ; height has changed
-
- ;; Double rotation.
- (setf p2 (avl-tree--node-branch p1 dir)
- b2 (avl-tree--node-balance p2)
- (avl-tree--node-branch p1 dir)
- (avl-tree--node-branch p2 opp)
- (avl-tree--node-branch p2 opp) p1
- (avl-tree--node-branch br opp)
- (avl-tree--node-branch p2 dir)
- (avl-tree--node-branch p2 dir) br
- (avl-tree--node-balance br)
- (if (< (* sgn b2) 0) sgn 0)
- (avl-tree--node-balance p1)
- (if (> (* sgn b2) 0) (- sgn) 0)
- (avl-tree--node-branch node branch) p2
- (avl-tree--node-balance p2) 0)
- t)))))
-
-(defun avl-tree--do-del-internal (node branch q)
- (let ((br (avl-tree--node-branch node branch)))
- (if (avl-tree--node-right br)
- (if (avl-tree--do-del-internal br 1 q)
- (avl-tree--del-balance node branch 1))
- (setf (avl-tree--node-data q) (avl-tree--node-data br)
- (avl-tree--node-branch node branch)
- (avl-tree--node-left br))
- t)))
-
-(defun avl-tree--do-delete (cmpfun root branch data test nilflag)
- "Delete DATA from BRANCH of node ROOT.
-\(See `avl-tree-delete' for TEST and NILFLAG).
-
-Return cons cell (SHRUNK . DATA), where SHRUNK is t if the
-height of the tree has shrunk and nil otherwise, and DATA is
-the related data."
- (let ((br (avl-tree--node-branch root branch)))
- (cond
- ;; DATA not in tree.
- ((null br)
- (cons nil nilflag))
-
- ((funcall cmpfun data (avl-tree--node-data br))
- (let ((ret (avl-tree--do-delete cmpfun br 0 data test nilflag)))
- (cons (if (car ret) (avl-tree--del-balance root branch 0))
- (cdr ret))))
-
- ((funcall cmpfun (avl-tree--node-data br) data)
- (let ((ret (avl-tree--do-delete cmpfun br 1 data test nilflag)))
- (cons (if (car ret) (avl-tree--del-balance root branch 1))
- (cdr ret))))
-
- (t ; Found it.
- ;; if it fails TEST, do nothing
- (if (and test (not (funcall test (avl-tree--node-data br))))
- (cons nil nilflag)
- (cond
- ((null (avl-tree--node-right br))
- (setf (avl-tree--node-branch root branch)
- (avl-tree--node-left br))
- (cons t (avl-tree--node-data br)))
-
- ((null (avl-tree--node-left br))
- (setf (avl-tree--node-branch root branch)
- (avl-tree--node-right br))
- (cons t (avl-tree--node-data br)))
-
- (t
- (if (avl-tree--do-del-internal br 0 br)
- (cons (avl-tree--del-balance root branch 0)
- (avl-tree--node-data br))
- (cons nil (avl-tree--node-data br))))
- ))))))
-
-
-
-;; ----------------------------------------------------------------
-;; Entering data
-
-(defun avl-tree--enter-balance (node branch dir)
- "Rebalance tree after insertion of NODE.
-NODE was inserted into the left (DIR=0) or right (DIR=1) sub-tree
-of the left (BRANCH=0) or right (BRANCH=1) child of NODE.
-Return t if the height of the tree has grown."
- (let ((br (avl-tree--node-branch node branch))
- ;; opposite direction: 0,1 -> 1,0
- (opp (avl-tree--switch-dir dir))
- ;; direction 0,1 -> sign factor -1,+1
- (sgn (avl-tree--dir-to-sign dir))
- p1 p2 b2)
- (cond
- ((< (* sgn (avl-tree--node-balance br)) 0)
- (setf (avl-tree--node-balance br) 0)
- nil)
-
- ((= (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-balance br) sgn)
- t)
-
- (t
- ;; Tree has grown => Rebalance.
- (setq p1 (avl-tree--node-branch br dir))
- (if (> (* sgn (avl-tree--node-balance p1)) 0)
- ;; Single rotation.
- (progn
- (setf (avl-tree--node-branch br dir)
- (avl-tree--node-branch p1 opp))
- (setf (avl-tree--node-branch p1 opp) br)
- (setf (avl-tree--node-balance br) 0)
- (setf (avl-tree--node-branch node branch) p1))
-
- ;; Double rotation.
- (setf p2 (avl-tree--node-branch p1 opp)
- b2 (avl-tree--node-balance p2)
- (avl-tree--node-branch p1 opp)
- (avl-tree--node-branch p2 dir)
- (avl-tree--node-branch p2 dir) p1
- (avl-tree--node-branch br dir)
- (avl-tree--node-branch p2 opp)
- (avl-tree--node-branch p2 opp) br
- (avl-tree--node-balance br)
- (if (> (* sgn b2) 0) (- sgn) 0)
- (avl-tree--node-balance p1)
- (if (< (* sgn b2) 0) sgn 0)
- (avl-tree--node-branch node branch) p2))
- (setf (avl-tree--node-balance
- (avl-tree--node-branch node branch))
- 0)
- nil))))
-
-(defun avl-tree--do-enter (cmpfun root branch data &optional updatefun)
- "Enter DATA in BRANCH of ROOT node.
-\(See `avl-tree-enter' for UPDATEFUN).
-
-Return cons cell (GREW . DATA), where GREW is t if height
-of tree ROOT has grown and nil otherwise, and DATA is the
-inserted data."
- (let ((br (avl-tree--node-branch root branch)))
- (cond
- ((null br)
- ;; Data not in tree, insert it.
- (setf (avl-tree--node-branch root branch)
- (avl-tree--node-create nil nil data 0))
- (cons t data))
-
- ((funcall cmpfun data (avl-tree--node-data br))
- (let ((ret (avl-tree--do-enter cmpfun br 0 data updatefun)))
- (cons (and (car ret) (avl-tree--enter-balance root branch 0))
- (cdr ret))))
-
- ((funcall cmpfun (avl-tree--node-data br) data)
- (let ((ret (avl-tree--do-enter cmpfun br 1 data updatefun)))
- (cons (and (car ret) (avl-tree--enter-balance root branch 1))
- (cdr ret))))
-
- ;; Data already in tree, update it.
- (t
- (let ((newdata
- (if updatefun
- (funcall updatefun data (avl-tree--node-data br))
- data)))
- (if (or (funcall cmpfun newdata data)
- (funcall cmpfun data newdata))
- (error "avl-tree-enter: Updated data does not match existing data"))
- (setf (avl-tree--node-data br) newdata)
- (cons nil newdata)) ; return value
- ))))
-
-(defun avl-tree--check (tree)
- "Check the balance of TREE."
- (avl-tree--check-node (avl-tree--root tree)))
-(defun avl-tree--check-node (node)
- (if (null node) 0
- (let ((dl (avl-tree--check-node (avl-tree--node-left node)))
- (dr (avl-tree--check-node (avl-tree--node-right node))))
- (cl-assert (= (- dr dl) (avl-tree--node-balance node)))
- (1+ (max dl dr)))))
-
-;; ----------------------------------------------------------------
-
-
-;;; INTERNAL USE ONLY
-(defun avl-tree--mapc (map-function root dir)
- "Apply MAP-FUNCTION to all nodes in the tree starting with ROOT.
-The function is applied in-order, either ascending (DIR=0) or
-descending (DIR=1).
-
-Note: MAP-FUNCTION is applied to the node and not to the data
-itself."
- (let ((node root)
- (stack nil)
- (go-dir t))
- (push nil stack)
- (while node
- (if (and go-dir
- (avl-tree--node-branch node dir))
- ;; Do the DIR subtree first.
- (progn
- (push node stack)
- (setq node (avl-tree--node-branch node dir)))
- ;; Apply the function...
- (funcall map-function node)
- ;; and do the opposite subtree.
- (setq node (if (setq go-dir (avl-tree--node-branch
- node (avl-tree--switch-dir dir)))
- (avl-tree--node-branch
- node (avl-tree--switch-dir dir))
- (pop stack)))))))
-
-;;; INTERNAL USE ONLY
-(defun avl-tree--do-copy (root)
- "Copy the AVL tree wiath ROOT as root.
-This function is highly recursive."
- (if (null root)
- nil
- (avl-tree--node-create
- (avl-tree--do-copy (avl-tree--node-left root))
- (avl-tree--do-copy (avl-tree--node-right root))
- (avl-tree--node-data root)
- (avl-tree--node-balance root))))
-
-(cl-defstruct (avl-tree--stack
- (:constructor nil)
- (:constructor avl-tree--stack-create
- (tree &optional reverse
- &aux
- (store
- (if (avl-tree-empty tree)
- nil
- (list (avl-tree--root tree))))))
- (:copier nil))
- reverse store)
-
-(defalias 'avl-tree-stack-p #'avl-tree--stack-p
- "Return t if OBJ is an avl-tree-stack, nil otherwise.
-\n(fn OBJ)")
-
-(defun avl-tree--stack-repopulate (stack)
- "Recursively push children of STACK onto the front.
-This pushes the children of the node at the head of STACK onto
-the front of STACK, until a leaf node is reached."
- (let ((node (car (avl-tree--stack-store stack)))
- (dir (if (avl-tree--stack-reverse stack) 1 0)))
- (when node ; check for empty stack
- (while (setq node (avl-tree--node-branch node dir))
- (push node (avl-tree--stack-store stack))))))
-
-
-;; ================================================================
-;;; The public functions which operate on AVL trees.
-
-;; define public alias for constructors so that we can set docstring
-(defalias 'avl-tree-create #'avl-tree--create
- "Create an empty AVL tree.
-COMPARE-FUNCTION is a function which takes two arguments, A and B,
-and returns non-nil if A is less than B, and nil otherwise.
-\n(fn COMPARE-FUNCTION)")
-
-(defalias 'avl-tree-compare-function #'avl-tree--cmpfun
- "Return the comparison function for the AVL tree TREE.
-\n(fn TREE)")
-
-(defun avl-tree-empty (tree)
- "Return t if AVL TREE is empty, otherwise return nil."
- (null (avl-tree--root tree)))
-
-(defun avl-tree-enter (tree data &optional updatefun)
- "Insert DATA into the AVL tree TREE.
-
-If an element that matches DATA (according to the tree's
-comparison function, see `avl-tree-create') already exists in
-TREE, it will be replaced by DATA by default.
-
-If UPDATEFUN is supplied and an element matching DATA already
-exists in TREE, UPDATEFUN is called with two arguments: DATA, and
-the matching element. Its return value replaces the existing
-element. This value *must* itself match DATA (and hence the
-pre-existing data), or an error will occur.
-
-Returns the new data."
- (cdr (avl-tree--do-enter (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0 data updatefun)))
-
-(defun avl-tree-delete (tree data &optional test nilflag)
- "Delete the element matching DATA from the AVL TREE.
-Matching uses the comparison function previously specified in
-`avl-tree-create' when TREE was created.
-
-Returns the deleted element, or nil if no matching element was
-found.
-
-Optional argument NILFLAG specifies a value to return instead of
-nil if nothing was deleted, so that this case can be
-distinguished from the case of a successfully deleted null
-element.
-
-If supplied, TEST specifies a test that a matching element must
-pass before it is deleted. If a matching element is found, it is
-passed as an argument to TEST, and is deleted only if the return
-value is non-nil."
- (cdr (avl-tree--do-delete (avl-tree--cmpfun tree)
- (avl-tree--dummyroot tree)
- 0 data test nilflag)))
-
-
-(defun avl-tree-member (tree data &optional nilflag)
- "Return the element in the AVL TREE which matches DATA.
-Matching uses the comparison function previously specified in
-`avl-tree-create' when TREE was created.
-
-If there is no such element in the tree, nil is returned.
-Optional argument NILFLAG specifies a value to return instead of nil
-in this case. This allows non-existent elements to be distinguished
-from a null element. (See also `avl-tree-member-p', which does this
-for you.)"
- (let ((node (avl-tree--root tree))
- (compare-function (avl-tree--cmpfun tree)))
- (catch 'found
- (while node
- (cond
- ((funcall compare-function data (avl-tree--node-data node))
- (setq node (avl-tree--node-left node)))
- ((funcall compare-function (avl-tree--node-data node) data)
- (setq node (avl-tree--node-right node)))
- (t (throw 'found (avl-tree--node-data node)))))
- nilflag)))
-
-
-(defun avl-tree-member-p (tree data)
- "Return t if an element matching DATA exists in the AVL TREE.
-Otherwise return nil. Matching uses the comparison function
-previously specified in `avl-tree-create' when TREE was created."
- (let ((flag '(nil)))
- (not (eq (avl-tree-member tree data flag) flag))))
-
-
-(defun avl-tree-map (fun tree &optional reverse)
- "Modify all elements in the AVL TREE by applying function FUN.
-
-Each element is replaced by the return value of FUN applied to
-that element.
-
-FUN is applied to the elements in ascending order, or descending
-order if REVERSE is non-nil."
- (avl-tree--mapc
- (lambda (node)
- (setf (avl-tree--node-data node)
- (funcall fun (avl-tree--node-data node))))
- (avl-tree--root tree)
- (if reverse 1 0)))
-
-
-(defun avl-tree-mapc (fun tree &optional reverse)
- "Apply function FUN to all elements in AVL TREE, for side-effect only.
-
-FUNCTION is applied to the elements in ascending order, or
-descending order if REVERSE is non-nil."
- (avl-tree--mapc
- (lambda (node)
- (funcall fun (avl-tree--node-data node)))
- (avl-tree--root tree)
- (if reverse 1 0)))
-
-
-(defun avl-tree-mapf
- (fun combinator tree &optional reverse)
- "Apply FUN to all elements in AVL TREE, combine results using COMBINATOR.
-
-The FUNCTION is applied and the results are combined in ascending
-order, or descending order if REVERSE is non-nil."
- (let (avl-tree-mapf--accumulate)
- (avl-tree--mapc
- (lambda (node)
- (setq avl-tree-mapf--accumulate
- (funcall combinator
- (funcall fun
- (avl-tree--node-data node))
- avl-tree-mapf--accumulate)))
- (avl-tree--root tree)
- (if reverse 0 1))
- (nreverse avl-tree-mapf--accumulate)))
-
-
-(defun avl-tree-mapcar (fun tree &optional reverse)
- "Apply FUN to all elements in AVL TREE, and make a list of the results.
-
-The function is applied and the list constructed in ascending
-order, or descending order if REVERSE is non-nil.
-
-Note that if you don't care about the order in which FUN is
-applied, just that the resulting list is in the correct order,
-then
-
- (avl-tree-mapf function \\='cons tree (not reverse))
-
-is more efficient."
- (nreverse (avl-tree-mapf fun 'cons tree reverse)))
-
-
-(defun avl-tree-first (tree)
- "Return the first element in TREE, or nil if TREE is empty."
- (let ((node (avl-tree--root tree)))
- (when node
- (while (avl-tree--node-left node)
- (setq node (avl-tree--node-left node)))
- (avl-tree--node-data node))))
-
-(defun avl-tree-last (tree)
- "Return the last element in TREE, or nil if TREE is empty."
- (let ((node (avl-tree--root tree)))
- (when node
- (while (avl-tree--node-right node)
- (setq node (avl-tree--node-right node)))
- (avl-tree--node-data node))))
-
-(defun avl-tree-copy (tree)
- "Return a copy of the AVL TREE."
- (let ((new-tree (avl-tree-create (avl-tree--cmpfun tree))))
- (setf (avl-tree--root new-tree) (avl-tree--do-copy (avl-tree--root tree)))
- new-tree))
-
-(defun avl-tree-flatten (tree)
- "Return a sorted list containing all elements of TREE."
- (let ((treelist nil))
- (avl-tree--mapc
- (lambda (node) (push (avl-tree--node-data node) treelist))
- (avl-tree--root tree) 1)
- treelist))
-
-(defun avl-tree-size (tree)
- "Return the number of elements in TREE."
- (let ((treesize 0))
- (avl-tree--mapc
- (lambda (_) (setq treesize (1+ treesize)))
- (avl-tree--root tree) 0)
- treesize))
-
-(defun avl-tree-clear (tree)
- "Clear the AVL TREE."
- (setf (avl-tree--root tree) nil))
-
-
-(defun avl-tree-stack (tree &optional reverse)
- "Return an object that behaves like a sorted stack of all elements of TREE.
-
-If REVERSE is non-nil, the stack is sorted in reverse order.
-\(See also `avl-tree-stack-pop').
-
-Note that any modification to TREE *immediately* invalidates all
-avl-tree-stacks created before the modification (in particular,
-calling `avl-tree-stack-pop' will give unpredictable results).
-
-Operations on these objects are significantly more efficient than
-constructing a real stack with `avl-tree-flatten' and using
-standard stack functions. As such, they can be useful in
-implementing efficient algorithms of AVL trees. However, in cases
-where mapping functions `avl-tree-mapc', `avl-tree-mapcar' or
-`avl-tree-mapf' would be sufficient, it is better to use one of
-those instead."
- (let ((stack (avl-tree--stack-create tree reverse)))
- (avl-tree--stack-repopulate stack)
- stack))
-
-
-(defun avl-tree-stack-pop (avl-tree-stack &optional nilflag)
- "Pop the first element from AVL-TREE-STACK.
-\(See also `avl-tree-stack').
-
-Returns nil if the stack is empty, or NILFLAG if specified.
-\(The latter allows an empty stack to be distinguished from
-a null element stored in the AVL tree.)"
- (let (node next)
- (if (not (setq node (pop (avl-tree--stack-store avl-tree-stack))))
- nilflag
- (when (setq next
- (avl-tree--node-branch
- node
- (if (avl-tree--stack-reverse avl-tree-stack) 0 1)))
- (push next (avl-tree--stack-store avl-tree-stack))
- (avl-tree--stack-repopulate avl-tree-stack))
- (avl-tree--node-data node))))
-
-
-(defun avl-tree-stack-first (avl-tree-stack &optional nilflag)
- "Return the first element of AVL-TREE-STACK, without removing it from stack.
-
-Returns nil if the stack is empty, or NILFLAG if specified.
-\(The latter allows an empty stack to be distinguished from
-a null element stored in the AVL tree.)"
- (or (car (avl-tree--stack-store avl-tree-stack))
- nilflag))
-
-
-(defun avl-tree-stack-empty-p (avl-tree-stack)
- "Return t if AVL-TREE-STACK is empty, nil otherwise."
- (null (avl-tree--stack-store avl-tree-stack)))
-
(iter-defun avl-tree-iter (tree &optional reverse)
"Return an AVL tree iterator object.
diff --git a/lisp/emacs-lisp/transitive-closure.el b/lisp/emacs-lisp/transitive-closure.el
new file mode 100644
index 00000000000..48c4817c527
--- /dev/null
+++ b/lisp/emacs-lisp/transitive-closure.el
@@ -0,0 +1,543 @@
+;;; transitive-closure.el -*- lexical-binding: t -*-
+;;; Efficient implementation of transitive closure on a graph of symbols
+;;; Based on Nuutila's thesis - https://www.cs.hut.fi/~enu/thesis.pdf, page 62
+;;; Interface
+;;; (tc-transitive-closure nodes edges) => tc--graph structures
+;;; (tc-graph-scc tc--graph node) => the equivalence class of nodes for node
+;;; (tc-graph-successors tc-graph node) => list of nodes reachable from node
+;;; (tc-graph-ordering tc-graph) =>
+;;; array of lists of nodes consistent with partial ordering
+;;; i.e nodes in list 0 have no dependencies
+;;; nodes in list 1 only have dependencies in list 0
+;;; nodes in list 2 only have dependencies in list 0 or 1
+;;; etc.
+
+(eval-when-compile (require 'cl-lib))
+(eval-when-compile (require 'cl-macs))
+(require 'avl-tree-core)
+
+(cl-defstruct tc--graph
+ nodes edges roots reachable node->idx node-ordering
+ idx->node idx->scc idx->successors
+ scc-edges scc->order scc-ordering
+ scc->rep scc->nodes scc->succs)
+
+(defvar tc--edges nil)
+(defvar tc--nodes nil)
+(defvar tc--roots nil)
+(defvar tc--size-nodes nil)
+(defvar tc--node->idx nil)
+(defvar tc--idx->visited nil)
+(defvar tc--idx->node nil)
+(defvar tc--idx->root nil)
+(defvar tc--idx->self-edge nil)
+(defvar tc--idx->height nil)
+(defvar tc--idx->scc nil)
+(defvar tc--idx->successors nil)
+(defvar tc--scc->rep nil)
+(defvar tc--sccs nil)
+(defvar tc--scc-edges nil)
+(defvar tc--scc->nodes nil)
+(defvar tc--visit-idx nil)
+(defvar tc--cstack nil)
+(defvar tc--vstack nil)
+(defvar tc--idx nil)
+(defvar tc--root nil)
+(defvar tc--scc->scc-node nil)
+(defvar tc--scc->successors nil)
+(defvar tc--scc-count nil)
+(defvar tc--cstack-height nil)
+(defvar tc--scc-succs nil)
+(defvar tc--scc-succ-gens nil)
+(defvar tc--scc->node-successor-sets nil)
+(defvar tc--scc->order nil)
+(defvar tc--scc-ordering nil)
+(defvar tc--reachable-nodes nil)
+
+;;; nodes is a list of symbols
+;;; edges is an alist specifying directed graph edges from each node
+
+(defun tc--init (nodes edges roots)
+ "Initialize state variables for transitive closure calculation"
+ (setq tc--edges edges
+ tc--nodes nodes
+ tc--roots roots
+ tc--size-nodes (length tc--nodes)
+ tc--reachable-nodes nil
+ tc--idx->node (make-vector tc--size-nodes nil)
+ tc--node->idx (make-hash-table :size tc--size-nodes))
+ (let ((ls nodes)
+ (i 0)
+ (v nil))
+ (while ls
+ (setq v (pop ls))
+ (puthash v i tc--node->idx)
+ (aset tc--idx->node i v)
+ (setq i (1+ i))))
+ (setq tc--idx->visited (make-vector tc--size-nodes nil)
+ tc--idx->root (make-vector tc--size-nodes nil)
+ tc--idx->self-edge (make-vector tc--size-nodes nil)
+ tc--idx->scc (make-vector tc--size-nodes nil)
+ tc--idx->height (make-vector tc--size-nodes nil)
+ tc--sccs (make-vector tc--size-nodes nil)
+ tc--scc->rep (make-vector tc--size-nodes nil)
+ tc--scc-edges nil
+ tc--idx->successors (make-vector (length tc--nodes) nil)
+ tc--scc->node-successor-sets nil
+ ;; this is wasteful of space, but a convenient method for creating
+ ;; component nodes
+ tc--scc->scc-node (make-vector (length tc--nodes) nil)
+ tc--scc->successors (make-vector (length tc--nodes) nil)
+ tc--scc->order (make-vector (length tc--nodes) -1)
+ tc--scc-ordering nil
+ tc--scc-count 0
+ tc--cstack nil
+ tc--vstack nil
+ tc--visit-idx 0
+ tc--cstack-height 0
+ tc--scc-succs (make-bool-vector (length tc--nodes) nil)
+ tc--scc-succ-gens (make-bool-vector (length tc--nodes) nil)))
+
+(defun tc--get-node-index (v)
+ (gethash v tc--node->idx))
+(defun tc--make-scc-set ()
+ (avl-tree-create #'<))
+(defun tc--scc-< (a b)
+ (and (avl-tree-member-p
+ (aref tc--scc->successors a)
+ b)
+ (/= a b)))
+(defun tc--scc-<= (a b)
+ (or (= a b)
+ (avl-tree-member-p
+ (aref tc--scc->successors a)
+ b)))
+
+(defun tc--scc-set-null (ss)
+ (avl-tree-empty ss))
+(defun tc--scc-set-member (elt ss)
+ (avl-tree-member-p ss elt))
+(defun tc--scc-set-del (elt ss)
+ (avl-tree-delete ss elt)
+ ss)
+(defun tc--scc-set-add (elt ss)
+ (avl-tree-enter ss elt)
+ ss)
+(defun tc--scc-set->list (ss)
+ (avl-tree-flatten ss))
+(defun tc--scc-set-seq (ss)
+ (avl-tree-stack ss))
+(defun tc--scc-set-seq-null (ss)
+ (avl-tree-stack-empty-p ss))
+(defun tc--scc-set-seq-first (ss)
+ (avl-tree-stack-first ss))
+(defun tc--scc-set-seq-pop (ss)
+ (avl-tree-stack-pop ss))
+(defun tc--scc-set-mapcar (f ss)
+ (avl-tree-mapcar f ss))
+(defun tc--scc-set-mapcan (f ss)
+ (apply #'nconc (avl-tree-mapcar f ss)))
+(defun tc--scc-set-mapc (f ss)
+ (avl-tree-mapc f ss))
+
+(defun tc--scc-set-union (ss0 &rest ss-rest)
+ (let ((acc (avl-tree-copy ss0))
+ idxs)
+ (while ss-rest
+ (setq idxs (tc--scc-set-seq (car ss-rest)))
+ (setq ss-rest (cdr ss-rest))
+ (while (not (tc--scc-set-seq-null idxs))
+ (tc--scc-set-add (tc--scc-set-seq-pop idxs)
+ acc)))
+ acc))
+
+(defun tc--scc-set-union-accumulate (acc ss1)
+ (let ((idxs (tc--scc-set-seq ss1)))
+ (while (not (tc--scc-set-seq-null idxs))
+ (tc--scc-set-add (tc--scc-set-seq-pop idxs)
+ acc)))
+ acc)
+
+
+(defun tc--add-to-meet-generators (d gens)
+ (let ((gs (tc--scc-set-seq gens))
+ (to-remove nil))
+ (while (and (> d -1) (not (tc--scc-set-seq-null gs)))
+ (let ((u (tc--scc-set-seq-pop gs)))
+ (cond
+ ((tc--scc-<= u d) (setq d -1))
+ ((tc--scc-< d u) (push u to-remove)))))
+ (when (and (< d 0)
+ to-remove)
+ (error "Transitive closure: Inconsistent topological sorted successor components"))
+ (when to-remove
+ (mapc (lambda (x) (tc--scc-set-del x gens)) to-remove))
+ (when (>= d 0)
+ (tc--scc-set-add d gens)))
+ gens)
+
+(defun tc--stack-tc-visit (v v-idx v-visited w)
+ (if (eq w v)
+ (aset tc--idx->self-edge v-idx t)
+ (let ((w-idx (tc--get-node-index w))
+ fwd-edge w-visited)
+ ;; v -> w is a forward edge if
+ ;; (a) w has already been visited, and
+ ;; (b) v is visited before w
+ (setq w-visited (aref tc--idx->visited w-idx))
+ (when (and w-visited
+ (< v-visited w-visited))
+ (setq fwd-edge t))
+ (unless w-visited
+ (tc--stack-tc w w-idx)
+ (setq w-visited (aref tc--idx->visited w-idx)))
+ (let ((w-scc (aref tc--idx->scc w-idx)))
+ (cond
+ ((null w-scc)
+ (aset tc--idx->root v-idx
+ (min (aref tc--idx->root v-idx)
+ (aref tc--idx->root w-idx))))
+ ((not fwd-edge)
+ (push w-scc tc--cstack)
+ (setq tc--cstack-height (1+ tc--cstack-height))))))))
+
+(defun tc--stack-tc-determine-meet-generators (h0)
+ (let ((gens (tc--make-scc-set))
+ d)
+ (while (> tc--cstack-height h0)
+ (setq d (pop tc--cstack)
+ tc--cstack-height (1- tc--cstack-height))
+ ;; skip if this component has already been processed
+ (unless (aref tc--scc-succs d)
+ ;; see if d is in successors of existing
+ ;; component or vice versa
+ (aset tc--scc-succs d t)
+ (setq gens
+ (tc--add-to-meet-generators d gens))))
+ gens))
+
+(defun tc--stack-tc-collect-scc-succs (c c-succs gens)
+ (let ((gs (tc--scc-set-seq gens))
+ (order -1)
+ d d-succs)
+ (while (not (tc--scc-set-seq-null gs))
+ (setq d (tc--scc-set-seq-pop gs))
+ (setq order (max order (aref tc--scc->order d)))
+ (setq d-succs (aref tc--scc->successors d))
+ (setq c-succs
+ (tc--scc-set-add d c-succs))
+ (setq c-succs
+ (tc--scc-set-union-accumulate c-succs d-succs)))
+ (aset tc--scc->order c (1+ order)))
+ (aset tc--scc->successors c c-succs)
+ c-succs)
+
+
+(defun tc--stack-tc-collect-scc (v-idx)
+ (let ((c tc--scc-count)
+ ;; note c-succs is a set of scc indices, not indices of original nodes
+ (c-succs (tc--make-scc-set))
+ c-elts gens)
+ (aset tc--scc->rep c v-idx)
+ (fillarray tc--scc-succs nil)
+ (setq tc--scc-count (1+ tc--scc-count))
+ (when (or (/= (car tc--vstack) v-idx)
+ (aref tc--idx->self-edge v-idx))
+ (tc--scc-set-add c c-succs))
+ (setq gens
+ (tc--stack-tc-determine-meet-generators
+ (aref tc--idx->height v-idx)))
+ (push `(,c ,@(tc--scc-set->list gens)) tc--scc-edges)
+ (setq c-succs
+ (tc--stack-tc-collect-scc-succs c c-succs gens))
+ ;; Finally determine members of c
+ (let ((w-idx (pop tc--vstack)))
+ (aset tc--idx->scc w-idx c)
+ (push w-idx c-elts)
+ (while (/= w-idx v-idx)
+ (setq w-idx (pop tc--vstack))
+ (aset tc--idx->scc w-idx c)
+ (push w-idx c-elts)))
+ (aset tc--sccs c c-elts)))
+
+(defun tc--stack-tc (v v-idx)
+ "Compute the transitive closure of tc--graph"
+ (when (aref tc--idx->visited v-idx)
+ (error "Visiting %S %S twice" v v-idx))
+ (aset tc--idx->visited v-idx tc--visit-idx )
+ (setq tc--visit-idx (1+ tc--visit-idx))
+ (aset tc--idx->root v-idx v-idx)
+ (aset tc--idx->height v-idx tc--cstack-height)
+ (push v-idx tc--vstack)
+ (let ((succs (assq v tc--edges))
+ (v-visited (aref tc--idx->visited v-idx)))
+ (when succs
+ (pop succs))
+ (while succs
+ (tc--stack-tc-visit v v-idx v-visited (pop succs))))
+ (when (= v-idx (aref tc--idx->root v-idx))
+ (tc--stack-tc-collect-scc v-idx)))
+
+(defun tc-transitive-closure (nodes edges &optional roots)
+ "Compute the transitive closure of tc--graph.
+Returns a tc-graph structure."
+ (unless roots
+ (setq roots nodes))
+ (tc--init nodes edges roots)
+ (let ((ls roots)
+ v v-idx)
+ (while ls
+ (setq v (pop ls))
+ (setq v-idx (tc--get-node-index v))
+ (unless (aref tc--idx->visited v-idx)
+ (tc--stack-tc v v-idx))))
+ (setq tc--scc->rep (make-vector tc--scc-count nil))
+ (let ((i 0)
+ (max-order 0)
+ (o -1)
+ (scc->order (make-vector tc--scc-count nil))
+ (scc->rep (make-vector tc--scc-count nil))
+ (scc->nodes (make-vector tc--scc-count nil)))
+ (while (< i tc--scc-count)
+ (aset scc->nodes i (aref tc--sccs i))
+ (aset scc->order i (aref tc--scc->order i))
+ (setq max-order (max max-order (aref scc->order i)))
+ (aset scc->rep i (aref tc--scc->rep i))
+ (setq i (1+ i)))
+ (setq tc--scc-ordering (make-vector (1+ max-order) nil)
+ i 0)
+ (while (< i tc--scc-count)
+ (setq o (aref scc->order i))
+ (aset tc--scc-ordering
+ o
+ (cons i
+ (aref tc--scc-ordering o)))
+ (setq i (1+ i)))
+ (setq tc--scc->rep scc->rep)
+ (setq tc--scc->order scc->order)
+ (setq tc--sccs scc->nodes)
+ (setq i (1- tc--size-nodes))
+ (while (>= i 0)
+ (when (aref tc--idx->visited i)
+ (push (aref tc--idx->node i) tc--reachable-nodes))
+ (setq i (1- i))))
+ (make-tc--graph
+ :nodes tc--nodes
+ :edges tc--edges
+ :roots tc--roots
+ :reachable tc--reachable-nodes
+ :node->idx tc--node->idx
+ :idx->node tc--idx->node
+ :idx->scc tc--idx->scc
+ :idx->successors tc--idx->successors
+ :scc-edges tc--scc-edges
+ :scc->rep tc--scc->rep
+ :scc->order tc--scc->order
+ :scc-ordering tc--scc-ordering
+ :scc->nodes tc--sccs
+ :scc->succs tc--scc->successors))
+
+
+(defun tc-graph-scc (tcg v)
+ (unless (memq v (tc--graph-nodes tcg))
+ (error "%S is not a node of the graph" v))
+ (let ((v-idx (gethash v (tc--graph-node->idx tcg)))
+ (idx->node (tc--graph-idx->node tcg))
+ (idx->scc (tc--graph-idx->scc tcg))
+ (scc->nodes (tc--graph-scc->nodes tcg)))
+ (let ((scc (mapcar (lambda (idx) (aref idx->node idx))
+ (aref scc->nodes
+ (aref idx->scc v-idx)))))
+ scc)))
+
+(defun tc-graph-reachable (tcg &optional v)
+ (if (null v)
+ (tc--graph-reachable tcg)
+ (let ((v-idx (gethash v (tc--graph-node->idx tcg)))
+ (idx->node (tc--graph-idx->node tcg))
+ (idx->scc (tc--graph-idx->scc tcg))
+ (scc->succs (tc--graph-scc->succs tcg))
+ (scc->nodes (tc--graph-scc->nodes tcg))
+ (idx->successors (tc--graph-idx->successors tcg))
+ scc scc-succs v-succs)
+ (unless (aref idx->successors v-idx)
+ (setq scc (aref idx->scc v-idx))
+ (setq scc-succs (aref scc->succs scc))
+ (setq v-succs
+ (tc--scc-set-mapcan
+ (lambda (c)
+ (mapcar (lambda (idx)
+ (aref idx->node idx))
+ (aref scc->nodes c)))
+ scc-succs))
+ (aset idx->successors v-idx v-succs))
+ (aref idx->successors v-idx))))
+
+(defun tc-graph-order (tcg v)
+ (let ((v-idx (gethash v (tc--graph-node->idx tcg)))
+ (idx->scc (tc--graph-idx->scc tcg))
+ (scc->order (tc--graph-scc->order tcg)))
+ (aref scc->order
+ (aref idx->scc v-idx))))
+
+(defun tc-graph-ordering (tcg)
+ (let ((o (tc--graph-node-ordering tcg)))
+ (unless o
+ (setq o (copy-sequence (tc--graph-scc-ordering tcg)))
+ (let ((n (length o))
+ (scc->nodes (tc--graph-scc->nodes tcg))
+ (idx->node (tc--graph-idx->node tcg))
+ (i 0))
+ (while (< i n)
+ (aset o i
+ (mapcan
+ (lambda (scc)
+ (mapcar (lambda (idx)
+ (aref idx->node idx))
+ (aref scc->nodes scc)))
+ (aref o i)))
+ (setq i (1+ i))))
+ (setf (tc--graph-node-ordering tcg) o))
+ o))
+
+(defun tc-invert-edges (nodes edges)
+ (let ((inv-map (make-hash-table :size (length nodes)))
+ (inv-als nil)
+ (ls edges)
+ to from tols fromls)
+ (while ls
+ (setq tols (pop ls))
+ (setq from (pop tols))
+ (while tols
+ (setq to (pop tols))
+ (setq fromls (gethash to inv-map nil))
+ (push from fromls)
+ (puthash to fromls inv-map)))
+ (maphash (lambda (k v)
+ (push `(,k . ,v) inv-als))
+ inv-map)
+ inv-als))
+
+;; specified graph provides reverse of desired ordering wrt specified roots
+(defun tc-reverse-rooted-graph (nodes edges &optional roots)
+ (let (inv-edges
+ tcg-fwd tcg-back
+ reachable-nodes reachable reachable-edges)
+ (setq inv-edges (tc-invert-edges nodes edges))
+ (setq tcg-fwd (tc-transitive-closure nodes inv-edges roots))
+ (setq reachable-nodes (tc--graph-reachable tcg-fwd))
+ (setq reachable (make-hash-table :size (length reachable-nodes)))
+ (mapc (lambda (v) (puthash v t reachable)) reachable-nodes)
+ (setq reachable-edges
+ (mapcan (lambda (apr)
+ (let ((from (car apr))
+ (tols (cdr apr))
+ result)
+ (when (gethash from reachable nil)
+ (setq result
+ `((,from
+ ,@(seq-filter
+ (lambda (to)
+ (gethash to reachable nil))
+ tols)))))
+ result))
+ edges))
+ (setq tcg-back (tc-transitive-closure reachable-nodes reachable-edges))
+ tcg-back))
+
+
+;;; Tests
+
+;; (defvar tst-nodes nil)
+;; (setq tst-nodes '(a b c d e))
+;; (defvar tst-edges0 nil)
+;; (setq tst-edges0 '())
+;; (defvar tst-edges1 nil)
+;; (setq tst-edges1 '((a)
+;; (b)
+;; (c)
+;; (d)
+;; (e)))
+;; (defvar tst-edges2 nil)
+;; (setq tst-edges2 '((a)
+;; (b a)
+;; (c b)
+;; (d c)
+;; (e d)))
+;; (defvar tst-edges3 nil)
+;; (setq tst-edges3 '((a b)
+;; (b c)
+;; (c d)
+;; (d e)
+;; (e)))
+;; (defvar tst-edges4 nil)
+;; (setq tst-edges4 '((a a)
+;; (b a b c)
+;; (c d)
+;; (d a b)
+;; (e e b)))
+;; (defvar tst-edges5 nil)
+;; (setq tst-edges5 '((a e)
+;; (b d)
+;; (c a)
+;; (d e)
+;; (e)))
+
+;; (defvar test-tc0 nil)
+;; (setq test-tc0 (tc-transitive-closure tst-nodes tst-edges0))
+;; (defvar test-tc1 nil)
+;; (setq test-tc1 (tc-transitive-closure tst-nodes tst-edges1))
+;; (defvar test-tc2 nil)
+;; (setq test-tc2 (tc-transitive-closure tst-nodes tst-edges2))
+;; (tc-graph-scc test-tc2 'a)
+;; (tc-graph-scc test-tc2 'b)
+;; (tc-graph-scc test-tc2 'c)
+;; (tc-graph-scc test-tc2 'd)
+;; (tc-graph-scc test-tc2 'e)
+;; (tc-graph-successors test-tc2 'a)
+;; (tc-graph-successors test-tc2 'b)
+;; (tc-graph-successors test-tc2 'c)
+;; (tc-graph-successors test-tc2 'd)
+;; (tc-graph-successors test-tc2 'e)
+;; (defvar test-tc3 nil)
+;; (setq test-tc3 (tc-transitive-closure tst-nodes tst-edges3))
+;; (tc-graph-scc test-tc3 'a)
+;; (tc-graph-scc test-tc3 'b)
+;; (tc-graph-scc test-tc3 'c)
+;; (tc-graph-scc test-tc3 'd)
+;; (tc-graph-scc test-tc3 'e)
+;; (tc-graph-successors test-tc3 'a)
+;; (tc-graph-successors test-tc3 'b)
+;; (tc-graph-successors test-tc3 'c)
+;; (tc-graph-successors test-tc3 'd)
+;; (tc-graph-successors test-tc3 'e)
+;; (defvar test-tc4 nil)
+;; (setq test-tc4 (tc-transitive-closure tst-nodes tst-edges4))
+;; (tc-graph-scc test-tc4 'a)
+;; (tc-graph-scc test-tc4 'b)
+;; (tc-graph-scc test-tc4 'c)
+;; (tc-graph-scc test-tc4 'd)
+;; (tc-graph-scc test-tc4 'e)
+;; (tc-graph-successors test-tc4 'a)
+;; (tc-graph-successors test-tc4 'b)
+;; (tc-graph-successors test-tc4 'c)
+;; (tc-graph-successors test-tc4 'd)
+;; (tc-graph-successors test-tc4 'e)
+;; (defvar test-tc5 nil)
+;; (setq test-tc5 (tc-transitive-closure tst-nodes tst-edges5))
+;; (tc-graph-scc test-tc5 'a)
+;; (tc-graph-scc test-tc5 'b)
+;; (tc-graph-scc test-tc5 'c)
+;; (tc-graph-scc test-tc5 'd)
+;; (tc-graph-scc test-tc5 'e)
+;; (tc-graph-successors test-tc5 'a)
+;; (tc-graph-successors test-tc5 'b)
+;; (tc-graph-successors test-tc5 'c)
+;; (tc-graph-successors test-tc5 'd)
+;; (tc-graph-successors test-tc5 'e)
+;; (defvar test-tc5-rev nil)
+;; (setq test-tc5-rev (tc-reverse-rooted-graph tst-nodes tst-edges5 '(e)))
+;; (tc-graph-ordering test-tc5-rev)
+;; (defvar test-tc5-rev2 nil)
+;; (setq test-tc5-rev2 (tc-reverse-rooted-graph tst-nodes tst-edges5 '(d a)))
+;; (tc-graph-ordering test-tc5-rev2)
diff --git a/lisp/loadup.el b/lisp/loadup.el
index 46b26750cd5..4209859c1f7 100644
--- a/lisp/loadup.el
+++ b/lisp/loadup.el
@@ -354,6 +354,8 @@
;; elisp-mode.elc is outdated.
(load "progmodes/elisp-mode")
+(load "emacs-lisp/avl-tree-core")
+(load "emacs-lisp/transitive-closure")
;; Preload some constants and floating point functions.
(load "emacs-lisp/float-sup")
diff --git a/lisp/startup.el b/lisp/startup.el
index 9ae53f4e50b..b02c622a4c3 100644
--- a/lisp/startup.el
+++ b/lisp/startup.el
@@ -280,6 +280,9 @@ command-line-ns-option-alist
(defvar before-init-hook nil
"Normal hook run after handling urgent options but before loading init files.")
+(defvar before-init-with-frame-hook nil
+ "Normal hook run after setting up the frame but before loading init files.")
+
(defvar after-init-hook nil
"Normal hook run after initializing the Emacs session.
It is run after Emacs loads the init file, `default' library, the
@@ -1306,8 +1309,9 @@ command-line
(mapc #'custom-reevaluate-setting
;; Initialize them in the same order they were loaded, in
;; case there are dependencies between them.
- (reverse custom-delayed-init-variables))))
- (setq custom-delayed-init-variables t)
+ (reverse custom-delayed-init-variables))
+ (setq custom-delayed-init-variables t))
+ (custom-do-startup-settings))
;; Warn for invalid user name.
(when init-file-user
@@ -1458,6 +1462,10 @@ command-line
(or (eq initial-window-system 'pc)
(tty-register-default-colors))
+ ;; allow hooks to run once the frame has been setup
+ ;; needed for loading wid-edit
+ (run-hooks 'before-init-with-frame-hook)
+
(let ((old-scalable-fonts-allowed scalable-fonts-allowed)
(old-face-ignored-fonts face-ignored-fonts))
^ permalink raw reply related [flat|nested] only message in thread
only message in thread, other threads:[~2023-02-23 2:33 UTC | newest]
Thread overview: (only message) (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-02-23 2:33 bug#61721: Improving support for setting customization at startup in redumped images Lynn Winebarger
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.