| blob | ba1b644562366cc95f201271aba8b4686d31b6ef |
1 ;;; nnvirtual.el --- virtual newsgroups access for Gnus
3 ;; Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002,
4 ;; 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
6 ;; Author: David Moore <dmoore@ucsd.edu>
7 ;; Lars Magne Ingebrigtsen <larsi@gnus.org>
8 ;; Masanobu UMEDA <umerin@flab.flab.fujitsu.junet>
9 ;; Keywords: news
11 ;; This file is part of GNU Emacs.
13 ;; GNU Emacs is free software; you can redistribute it and/or modify
14 ;; it under the terms of the GNU General Public License as published by
15 ;; the Free Software Foundation; either version 2, or (at your option)
16 ;; any later version.
18 ;; GNU Emacs is distributed in the hope that it will be useful,
19 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ;; GNU General Public License for more details.
23 ;; You should have received a copy of the GNU General Public License
24 ;; along with GNU Emacs; see the file COPYING. If not, write to the
25 ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
26 ;; Boston, MA 02110-1301, USA.
28 ;;; Commentary:
30 ;; The other access methods (nntp, nnspool, etc) are general news
31 ;; access methods. This module relies on Gnus and can not be used
32 ;; separately.
34 ;;; Code:
49 "If non-nil, always scan groups for unread articles when entering a group.
50 If this variable is nil and you read articles in a component group
51 after the virtual group has been activated, the read articles from the
60 \f
67 "Table of rules on how to map between component group and article number to virtual article number.")
76 "Compressed sequence of read articles on the virtual group as computed from the unread status of individual component groups.")
79 "Compressed marks alist for the virtual group as computed from the marks of individual component groups.")
82 "T if we have already installed the group info for this group, and shouldn't blast over it again.")
89 \f
91 ;;; Interface functions.
97 server fetch-old)
103 'headers
108 cgroup carticle article result prefix)
118 ;; FIX FIX FIX we want to check the cache!
119 ;; This is probably evil if people have set
120 ;; gnus-use-cache to nil themselves, but I
121 ;; have no way of finding the true value of it.
124 articles cgroup nil))))
126 ;; If we got HEAD headers, we convert them into NOV
127 ;; headers. This is slow, inefficient and, come to think
128 ;; of it, downright evil. So sue me. I couldn't be
129 ;; bothered to write a header parse routine that could
130 ;; parse a mixed HEAD/NOV buffer.
140 ;; We remove this article from the articles list, if
141 ;; anything is left in the articles list after going through
142 ;; the entire buffer, then those articles have been
143 ;; expired or canceled, so we appropriately update the
144 ;; component group below. They should be coming up
145 ;; generally in order, so this shouldn't be slow.
150 ;; This line has no reverse mapping, that means it
151 ;; was an extra article reference returned by nntp.
155 ;; Otherwise insert the virtual article number,
156 ;; and clean up the xrefs.
159 prefix system-name)
161 )
166 ;; Anything left in articles is expired or canceled.
167 ;; Could be smart and not tell it about articles already known?
170 )
172 ;; The headers are ready for reading, so they are inserted into
173 ;; the nntp-server-buffer, which is where Gnus expects to find
174 ;; them.
180 ;; FIX FIX FIX, we should be able to sort faster than
181 ;; this if needed, since each cgroup is sorted, we just
182 ;; need to merge
193 ;; This is a fetch by Message-ID.
204 nnvirtual-last-accessed-component-group)))
207 ;; This is a fetch by number.
223 ;; We bind this here to avoid double decoding.
232 defs))
235 t
237 nnvirtual-mapping-offsets nil
238 nnvirtual-mapping-len 0
239 nnvirtual-mapping-reads nil
240 nnvirtual-mapping-marks nil
241 nnvirtual-info-installed nil)
243 ;; Go through the newsrc alist and find all component groups.
245 group)
248 ;; Add this group to the list of component groups.
253 t)))
267 nnvirtual-always-rescan)
274 nnvirtual-mapping-len nnvirtual-mapping-len group))))
279 'unknown
285 nnvirtual-last-accessed-component-group nil))))
292 ;; The component group might be a virtual group.
296 mark)
303 t)
321 ;; Install the precomputed lists atomically, so the virtual group
322 ;; is not left in a half-way state in case of C-g.
330 t))
336 ;; copy over existing marks first, in case they set anything
338 ;; do a catchup on all component groups
341 ;; Make sure all groups are activated.
346 nnvirtual-component-groups)
353 "Return the real group and article for virtual GROUP and ARTICLE."
377 group article))
382 \f
383 ;;; Internal functions.
386 "Convert HEAD headers into NOV headers."
391 header)
398 "Edit current NOV header in current buffer to have an xref to the component group, and also server prefix any existing xref lines."
399 ;; Move to beginning of Xref field, creating a slot if needed.
407 ;; Remove any spaces at the beginning of the Xref field.
416 ;; If there were existing xref lines, clean them up to have the correct
417 ;; component server prefix.
428 nil t)
438 ;; Ensure a trailing \t.
451 "Copy marks from the virtual group to the component groups.
452 If READ-P is not nil, update the (un)read status of the components.
453 If UPDATE-P is not nil, call gnus-group-update-group on the components."
463 nil
468 mark type groups carticles info entry)
470 ;; Ok, atomically move all of the (un)read info, clear any old
471 ;; marks, and move all of the current marks. This way if someone
472 ;; hits C-g, you won't leave the component groups in a half-way state.
474 ;; move (un)read
475 ;; bind for workaround guns-update-read-articles
480 ;; clear all existing marks on the component groups
486 info
489 nil))))
491 ;; Ok, currently type-marks is an assq list with keys of a mark type,
492 ;; with data of an assq list with keys of component group names
493 ;; and the articles which correspond to that key/group pair.
499 nil t))))
501 ;; possibly update the display, it is really slow
509 "Return the prefixed name of the current nnvirtual group."
514 ;;; This is currently O(kn^2) to merge n lists of length k.
515 ;;; You could do it in O(knlogn), but we have a small n, and the
516 ;;; overhead of the other approach is probably greater.
518 "Merge many sorted lists of numbers."
524 ;;; We map between virtual articles and real articles in a manner
525 ;;; which keeps the size of the virtual active list the same as the
526 ;;; sum of the component active lists.
528 ;;; To achieve fair mixing of the groups, the last article in each of
529 ;;; N component groups will be in the last N articles in the virtual
530 ;;; group.
532 ;;; If you have 3 components A, B and C, with articles 1-8, 1-5, and
533 ;;; 6-7 respectively, then the virtual article numbers look like:
534 ;;;
535 ;;; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
536 ;;; A1 A2 A3 A4 B1 A5 B2 A6 B3 A7 B4 C6 A8 B5 C7
538 ;;; To compute these mappings we generate a couple tables and then
539 ;;; do some fast operations on them. Tables for the example above:
540 ;;;
541 ;;; Offsets - [(A 0) (B -3) (C -1)]
542 ;;;
543 ;;; a b c d e
544 ;;; Mapping - ([ 3 0 1 3 0 ]
545 ;;; [ 6 3 2 9 3 ]
546 ;;; [ 8 6 3 15 9 ])
547 ;;;
548 ;;; (note column 'e' is different in real algorithm, which is slightly
549 ;;; different than described here, but this gives you the methodology.)
550 ;;;
551 ;;; The basic idea is this, when going from component->virtual, apply
552 ;;; the appropriate offset to the article number. Then search the first
553 ;;; column of the table for a row where 'a' is less than or equal to the
554 ;;; modified number. You can see that only group A can therefore go to
555 ;;; the first row, groups A and B to the second, and all to the last.
556 ;;; The third column of the table is telling us the number of groups
557 ;;; which might be able to reach that row (it might increase by more than
558 ;;; 1 if several groups have the same size).
559 ;;; Then column 'b' provides an additional offset you apply when you have
560 ;;; found the correct row. You then multiply by 'c' and add on the groups
561 ;;; _position_ in the offset table. The basic idea here is that on
562 ;;; any given row we are going to map back and forth using X'=X*c+Y and
563 ;;; X=(X'/c), Y=(X' mod c). Then once you've done this transformation,
564 ;;; you apply a final offset from column 'e' to give the virtual article.
565 ;;;
566 ;;; Going the other direction, you instead search on column 'd' instead
567 ;;; of 'a', and apply everything in reverse order.
569 ;;; Convert component -> virtual:
570 ;;; set num = num - Offset(group)
571 ;;; find first row in Mapping where num <= 'a'
572 ;;; num = (num-'b')*c + Position(group) + 'e'
574 ;;; Convert virtual -> component:
575 ;;; find first row in Mapping where num <= 'd'
576 ;;; num = num - 'e'
577 ;;; group_pos = num mod 'c'
578 ;;; num = (num / 'c') + 'b' + Offset(group_pos)
580 ;;; Easy no? :)
581 ;;;
582 ;;; Well actually, you need to keep column e offset smaller by the 'c'
583 ;;; column for that line, and always add 1 more when going from
584 ;;; component -> virtual. Otherwise you run into a problem with
585 ;;; unique reverse mapping.
588 "Return a cons of the component group and article corresponding to the given virtual ARTICLE."
590 entry group-pos)
603 ))
604 ))
609 "Return the virtual article number corresponding to the given component GROUP and ARTICLE."
613 entry)
615 group-pos))))
618 group-pos))))
627 group-pos
631 )))
635 "Return list of virtual article numbers for all ARTICLES in GROUP.
636 The ARTICLES should be sorted, and can be a compressed sequence.
637 If any of the article numbers has no corresponding virtual article,
638 then it is left out of the result."
645 j a)
649 ;; If this is slow, you can optimize by moving article checking
650 ;; into here. You don't have to recompute the group-pos,
651 ;; nor scan the table every time.
659 "Return an association list of component article numbers.
660 These are indexed by elements of nnvirtual-component-groups, based on
661 the sequence ARTICLES of virtual article numbers. ARTICLES should be
662 sorted, and can be a compressed sequence. If any of the article
663 numbers has no corresponding component article, then it is left out of
664 the result."
668 nnvirtual-component-groups))
669 a i j article entry)
673 j a)
682 carticles)
683 carticles))
687 "Build the tables necessary to map between component (group, article) to virtual article.
688 Generate the set of read messages and marks for the virtual group
689 based on the marks on the component groups."
694 actives all-unreads all-marks
695 active min max size unreads marks
696 next-M next-tot
697 reads beg)
698 ;; Ok, we loop over all component groups and collect a lot of
699 ;; information:
700 ;; Into actives we place (g size max), where size is max-min+1.
701 ;; Into all-unreads we put (g unreads).
702 ;; Into all-marks we put (g marks).
703 ;; We also increment cnt and tot here, and compute M (max of sizes).
709 ;; store active information
711 ;; collect unread/mark info for later
717 marks))
720 ;; count groups, total #articles, and max size
725 nnvirtual-component-groups)
727 ;; Number of articles in the virtual group.
731 ;; We want the actives list sorted by size, to build the tables.
734 ;; Build the offset table. Largest sized groups are at the front.
741 actives))))
743 ;; Build the mapping table.
750 ;; make current row in table
752 nnvirtual-mapping-table)
753 ;; update M and tot
756 ;; subtract the current size from all entries.
758 ;; remove anything that went to 0.
765 ;; Now that the mapping tables are generated, we can convert
766 ;; and combine the separate component unreads and marks lists
767 ;; into single lists of virtual article numbers.
772 all-unreads)))
778 'nnvirtual-merge-sorted-lists
783 all-marks)))))
784 gnus-article-mark-lists))
786 ;; Remove any empty marks lists, and store.
793 ;; We need to convert the unreads to reads. We compress the
794 ;; sequence as we go, otherwise it could be huge.
796 unreads)
799 ;; try to get a range.
807 ))
813 ;; Store the reads list for later use.
816 ;; Throw flag to show we changed the info.
818 ))
822 ;;; arch-tag: ca8c8ad9-1bd8-4b0f-9722-90dc645a45f5
823 ;;; nnvirtual.el ends here