* New version 2.26

[alpine.git] / pith / sort.c

/*
 * ========================================================================
 * Copyright 2013-2022 Eduardo Chappa
 * Copyright 2006-2007 University of Washington
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * ========================================================================
 */

#include "../pith/headers.h"
#include "../pith/sort.h"
#include "../pith/state.h"
#include "../pith/status.h"
#include "../pith/msgno.h"
#include "../pith/flag.h"
#include "../pith/pineelt.h"
#include "../pith/thread.h"
#include "../pith/search.h"
#include "../pith/pattern.h"
#include "../pith/util.h"
#include "../pith/signal.h"
#include "../pith/busy.h"
#include "../pith/icache.h"


/*
 * global place to store mail_sort and mail_thread results
 */
struct global_sort_data g_sort;


/*
 * Internal prototypes
 */
void    sort_sort_callback(MAILSTREAM *, unsigned long *, unsigned long);
int     percent_sorted(void);
int     pine_compare_long(const qsort_t *, const qsort_t *);
int     pine_compare_long_rev(const qsort_t *, const qsort_t *);
int     pine_compare_scores(const qsort_t *, const qsort_t *);
void    build_score_array(MAILSTREAM *, MSGNO_S *);
void    free_score_array(void);


/*----------------------------------------------------------------------
    Map sort types to names
  ----*/
char *    
sort_name(SortOrder so)
{
    /*
     * Make sure the first upper case letter of any new sort name is
     * unique.  The command char and label for sort selection is 
     * derived from this name and its first upper case character.
     * See mailcmd.c:select_sort().
     */
    return((so == SortArrival)  ? "Arrival" :
            (so == SortDate)     ? "Date" :
             (so == SortSubject)  ? "Subject" :
              (so == SortCc)       ? "Cc" :
               (so == SortFrom)     ? "From" :
                (so == SortTo)       ? "To" :
                 (so == SortSize)     ? "siZe" :
                  (so == SortSubject2) ? "OrderedSubj" :
                   (so == SortScore)    ? "scorE" :
                     (so == SortThread)  ? "tHread" :
                                          "BOTCH");
}


/*----------------------------------------------------------------------
    Sort the current folder into the order set in the msgmap

Args: msgmap --
      new_sort --
      new_rev -- 

    The idea of the deferred sort is to let the user interrupt a long sort
    and have a chance to do a different command, such as a sort by arrival
    or a Goto.  The next newmail call will increment the deferred variable,
    then the user may do a command, then the newmail call after that
    causes the sort to happen if it is still needed.
  ----*/
void
sort_folder(MAILSTREAM *stream, MSGNO_S *msgmap, SortOrder new_sort,
            int new_rev, unsigned int flags)
{
    long           raw_current, i, j;
    unsigned long *sort = NULL;
    int            we_cancel = 0;
    char           sort_msg[MAX_SCREEN_COLS+1];
    SortOrder      current_sort;
    int            current_rev;
    MESSAGECACHE  *mc;

    dprint((2, "Sorting by %s%s\n",
               sort_name(new_sort), new_rev ? "/reverse" : ""));

    if(!msgmap)
      return;

    current_sort = mn_get_sort(msgmap);
    current_rev = mn_get_revsort(msgmap);
    /*
     * If we were previously threading (spare == 1) and now we're switching
     * sorts (other than just a rev switch) then erase the information
     * about the threaded state (collapsed and so forth).
     */
    if(stream && stream->spare && (current_sort != new_sort))
      erase_threading_info(stream, msgmap);

    if(mn_get_total(msgmap) <= 1L
       && !(mn_get_total(msgmap) == 1L
            && (new_sort == SortThread || new_sort == SortSubject2))){
        mn_set_sort(msgmap, new_sort);
        mn_set_revsort(msgmap, new_rev);
        if(!mn_get_mansort(msgmap))
          mn_set_mansort(msgmap, (flags & SRT_MAN) ? 1 : 0);
          
        return;
    }

    raw_current = mn_m2raw(msgmap, mn_get_cur(msgmap));

    if(new_sort == SortArrival){
        /*
         * NOTE: RE c-client sorting, our idea of arrival is really
         *       just the natural sequence order.  C-client, and probably
         *       rightly so, considers "arrival" the order based on the
         *       message's internal date.  This is more costly to compute
         *       since it means touching the message store (say "nntp"?),
         *       so we just preempt it here.
         *
         *       Someday c-client will support "unsorted" and do what
         *       we're doing here.  That day this gets scrapped.
         */

        mn_set_sort(msgmap, new_sort);
        mn_set_revsort(msgmap, new_rev);

        if(current_sort != new_sort || current_rev != new_rev ||
           any_lflagged(msgmap, MN_EXLD))
          clear_index_cache(stream, 0);

        if(any_lflagged(msgmap, MN_EXLD)){
            /*
             * BEWARE: "exclusion" may leave holes in the unsorted sort order
             * so we have to do a real sort if that is the case.
             */
            qsort(msgmap->sort+1, (size_t) mn_get_total(msgmap),
                  sizeof(long),
                  new_rev ? pine_compare_long_rev : pine_compare_long);
        }
        else if(mn_get_total(msgmap) > 0L){
            if(new_rev){
                clear_index_cache(stream, 0);
                for(i = 1L, j = mn_get_total(msgmap); j >= 1; i++, j--)
                  msgmap->sort[i] = j;
            }
            else
              for(i = 1L; i <= mn_get_total(msgmap); i++)
                msgmap->sort[i] = i;
        }

        /* reset the inverse array */
        msgno_reset_isort(msgmap);
    }
    else if(new_sort == SortScore){

        /*
         * We have to build a temporary array which maps raw msgno to
         * score. We use the index cache machinery to build the array.
         */

        mn_set_sort(msgmap, new_sort);
        mn_set_revsort(msgmap, new_rev);
        
        if(flags & SRT_VRB){
            /* TRANSLATORS: tell user they are waiting for Sorting of %s, the foldername */
            snprintf(sort_msg, sizeof(sort_msg), _("Sorting \"%s\""),
                    strsquish(tmp_20k_buf + 500, 500, ps_global->cur_folder,
                              ps_global->ttyo->screen_cols - 20));
            we_cancel = busy_cue(sort_msg, NULL, 0);
        }

        /*
         * We do this so that we don't have to lookup the scores with function
         * calls for each qsort compare.
         */
        build_score_array(stream, msgmap);

        qsort(msgmap->sort+1, (size_t) mn_get_total(msgmap),
              sizeof(long), pine_compare_scores);
        free_score_array();
        clear_index_cache(stream, 0);

        if(we_cancel)
          cancel_busy_cue(1);

        /*
         * Flip the sort if necessary (cheaper to do it once than for
         * every comparison in pine_compare_scores.
         */
        if(new_rev && mn_get_total(msgmap) > 1L){
            long *ep = &msgmap->sort[mn_get_total(msgmap)],
                 *sp = &msgmap->sort[1], tmp;

            do{
                tmp   = *sp;
                *sp++ = *ep;
                *ep-- = tmp;
            }
            while(ep > sp);
        }

        /* reset the inverse array */
        msgno_reset_isort(msgmap);
    }
    else{

        mn_set_sort(msgmap, new_sort);
        mn_set_revsort(msgmap, new_rev);
        clear_index_cache(stream, 0);

        if(flags & SRT_VRB){
            int (*sort_func)() = NULL;

            /*
             * IMAP sort doesn't give us any way to get progress,
             * so just spin the bar rather than show zero percent
             * forever while a slow sort's going on...
             */
            if(!(stream && stream->dtb && stream->dtb->name
                 && !strucmp(stream->dtb->name, "imap")
                 && LEVELSORT(stream)))
              sort_func = percent_sorted;

            snprintf(sort_msg, sizeof(sort_msg), _("Sorting \"%s\""),
                    strsquish(tmp_20k_buf + 500, 500, ps_global->cur_folder,
                              ps_global->ttyo->screen_cols - 20));
            we_cancel = busy_cue(sort_msg, sort_func, 0);
        }

        /*
         * Limit the sort/thread if messages are hidden from view 
         * by lighting searched bit of every interesting msg in 
         * the folder and call c-client thread/sort to do the dirty work.
         *
         * Unfortunately it isn't that easy. IMAP servers are not able to
         * handle medium to large sized sequence sets (more than 1000
         * characters in the command line breaks some) so we have to try
         * to handle it locally. By lighting the searched bits and
         * providing a NULL search program we get a special c-client
         * interface. This means that c-client will attempt to send the
         * sequence set with the SORT or THREAD but it may get back
         * a BAD response because of long command lines. In that case,
         * if it is a SORT call, c-client will issue the full SORT
         * without the sequence sets and will then filter the results
         * locally. So sort_sort_callback will see the correctly
         * filtered results. If it is a mail_thread call, a similar thing
         * will be done. If a BAD is received, then there is no way to
         * easily filter the results. C-client (in this special case where
         * we provide a NULL search program) will set tree->num to zero
         * for nodes of the thread tree which were supposed to be
         * filtered out of the thread. Then pine, in sort_thread_callback,
         * will treat those as dummy nodes (nodes which are part of the
         * tree logically but where we don't have access to the messages).
         * This will give us a different answer than we would have gotten
         * if the restricted thread would have worked, but it's something.
         *
         * It isn't in general possible to give some shorter search set
         * in place of the long sequence set because the long sequence set
         * may be the result of several filter rules or of excluded
         * messages in news (in this 2nd case maybe we could give
         * a shorter search set).
         *
         * We note also that the too-long commands in imap is a general
         * imap deficiency. It comes up in particular also in SEARCH
         * commands. Pine likes to exclude the hidden messages from the
         * SEARCH. SEARCH will be handled transparently by the local
         * c-client by first issuing the full SEARCH command, if that
         * comes back with a BAD and there is a pgm->msgno at the top
         * level of pgm, then c-client will re-issue the SEARCH command
         * but without the msgno sequence set in hopes that the resulting
         * command will now be short enough, and then it will filter out
         * the sequence set locally. If that doesn't work, it will
         * download the messages and do the SEARCH locally. That is
         * controllable by a flag bit.
         */
        for(i = 1L; i <= stream->nmsgs; i++)
          if((mc = mail_elt(stream, i)) != NULL)
            mc->searched = !get_lflag(stream, NULL, i, MN_EXLD);
        
        g_sort.msgmap = msgmap;
        if(new_sort == SortThread || new_sort == SortSubject2){
            THREADNODE *thread;

            /*
             * Install callback to collect thread results
             * and update sort mapping.  Problem this solves
             * is that of receiving exists/expunged events
             * within sort/thread response.  Since we update
             * the sorted table within those handlers, we
             * can get out of sync when we replace possibly
             * stale sort/thread results once the function
             * call's returned.  Make sense?  Thought so.
             */
            mail_parameters(NULL, SET_THREADRESULTS,
                            (void *) sort_thread_callback);

            thread = mail_thread(stream,
                                 (new_sort == SortThread)
                                   ? "REFERENCES" : "ORDEREDSUBJECT",
                                 NULL, NULL, 0L);

            mail_parameters(NULL, SET_THREADRESULTS, (void *) NULL);

            if(!thread){
                new_sort = current_sort;
                new_rev  = current_rev;
                q_status_message1(SM_ORDER, 3, 3,
                                  "Sort Failed!  Restored %.200s sort.",
                                  sort_name(new_sort));
            }

            if(thread)
              mail_free_threadnode(&thread);
        }
        else{
            /*
             * Set up the sort program.
             * NOTE: we deal with reverse bit below.
             */
            g_sort.prog = mail_newsortpgm();
            g_sort.prog->function = (new_sort == SortSubject)
                                     ? SORTSUBJECT
                                     : (new_sort == SortFrom)
                                        ? SORTFROM
                                        : (new_sort == SortTo)
                                           ? SORTTO
                                           : (new_sort == SortCc)
                                              ? SORTCC
                                              : (new_sort == SortDate)
                                                 ? SORTDATE
                                                 : (new_sort == SortSize)
                                                    ? SORTSIZE
                                                    : SORTARRIVAL;

            mail_parameters(NULL, SET_SORTRESULTS,
                            (void *) sort_sort_callback);

            /* Where the rubber meets the road. */
            sort = mail_sort(stream, NULL, NULL, g_sort.prog, 0L);

            mail_parameters(NULL, SET_SORTRESULTS, (void *) NULL);

            if(!sort){
                new_sort = current_sort;
                new_rev  = current_rev;
                q_status_message1(SM_ORDER, 3, 3,
                                  "Sort Failed!  Restored %s sort.",
                                  sort_name(new_sort));
            }

            if(sort)
              fs_give((void **) &sort);

            mail_free_sortpgm(&g_sort.prog);
        }

        if(we_cancel)
          cancel_busy_cue(1);

        /*
         * Flip the sort if necessary (cheaper to do it once than for
         * every comparison underneath mail_sort()
         */
        if(new_rev && mn_get_total(msgmap) > 1L){
            long *ep = &msgmap->sort[mn_get_total(msgmap)],
                 *sp = &msgmap->sort[1], tmp;

            do{
                tmp   = *sp;
                *sp++ = *ep;
                *ep-- = tmp;
            }
            while(ep > sp);

            /* reset the inverse array */
            msgno_reset_isort(msgmap);

            /*
             * Flip the thread numbers around.
             * This puts us in a weird state that requires keeping track
             * of. The direction of the thread list hasn't changed, but the
             * thrdnos have and the display direction has.
             *
             * For Sort   thrdno 1       thread list head
             *            thrdno 2              |
             *            thrdno .              v  nextthd this direction
             *            thrdno .
             *            thrdno n       thread list tail
             *
             * Rev Sort   thrdno 1       thread list tail
             *            thrdno 2
             *            thrdno .              ^  nextthd this direction
             *            thrdno .              |
             *            thrdno n       thread list head
             */
            if(new_sort == SortThread || new_sort == SortSubject2){
                PINETHRD_S *thrd;

                thrd = fetch_head_thread(stream);
                for(j = msgmap->max_thrdno; thrd && j >= 1L; j--){
                    thrd->thrdno = j;

                    if(thrd->nextthd)
                      thrd = fetch_thread(stream,
                                          thrd->nextthd);
                    else
                      thrd = NULL;
                }
            }
        }
    }

    /* Fix up sort structure */
    mn_set_sort(msgmap, new_sort);
    mn_set_revsort(msgmap, new_rev);
    /*
     * Once a folder has been sorted manually, we continue treating it
     * as manually sorted until it is closed.
     */
    if(!mn_get_mansort(msgmap))
      mn_set_mansort(msgmap, (flags & SRT_MAN) ? 1 : 0);
    
    if(!msgmap->hilited){
        /*
         * If current is hidden, change current to visible parent.
         * It can only be hidden if we are threading.
         *
         * Don't do this if hilited is set, because it means we're in the
         * middle of an aggregate op, and this will mess up our selection.
         * "hilited" means we've done a pseudo_selected, which we'll later
         * fix with restore_selected.
         */
        if(THREADING())
          mn_reset_cur(msgmap, first_sorted_flagged(new_rev ? F_NONE : F_SRCHBACK,
                                                    stream,
                                                    mn_raw2m(msgmap, raw_current),
                                                    FSF_SKIP_CHID));
        else
          mn_reset_cur(msgmap, mn_raw2m(msgmap, raw_current));
    }

    msgmap->top = -1L;

    if(!sp_mail_box_changed(stream))
      sp_set_unsorted_newmail(stream, 0);

    /*
     * Turn off the MN_USOR flag. Don't bother going through the
     * function call and the message number mappings.
     */
    if(THREADING()){
        PINELT_S *pelt;

        for(i = 1L; i <= stream->nmsgs; i++)
          if((mc = mail_elt(stream, i)) != NULL && (pelt = mc->sparep) != NULL)
            pelt->unsorted = 0;
    }
}


void
sort_sort_callback(MAILSTREAM *stream, long unsigned int *list, long unsigned int nmsgs)
{
    long i;

    dprint((2, "sort_sort_callback\n"));

    if(mn_get_total(g_sort.msgmap) < nmsgs)
      alpine_panic("Message count shrank after sort!");

    /* copy ulongs to array of longs */
    for(i = nmsgs; i > 0; i--)
      g_sort.msgmap->sort[i] = list ? (long) list[i-1] : i-1;

    /* reset the inverse array */
    msgno_reset_isort(g_sort.msgmap);

    dprint((2, "sort_sort_callback done\n"));
}


/*
 * Return value for use by progress bar.
 */
int
percent_sorted(void)
{
    /*
     * C-client's sort routine exports two types of status
     * indicators.  One's the progress thru loading the cache (typically
     * the elephantine bulk of the delay, and the progress thru the
     * actual sort (typically qsort).  Our job is to balance the two
     */
    
    return(g_sort.prog && g_sort.prog->nmsgs
      ? (((((g_sort.prog->progress.cached * 100)
                                         / g_sort.prog->nmsgs) * 9) / 10)
         + (((g_sort.prog->progress.sorted) * 10)
                                         / g_sort.prog->nmsgs))
      : 0);
}


/*
 * This is only used at startup time.  It sets ps->def_sort and
 * ps->def_sort_rev.  The syntax of the sort_spec is type[/reverse].
 * A reverse without a type is the same as arrival/reverse.  A blank
 * argument also means arrival/reverse.
 */
int
decode_sort(char *sort_spec, SortOrder *def_sort, int *def_sort_rev)
{
    char *sep;
    char *fix_this = NULL;
    int   x, reverse;

    if(!sort_spec || !*sort_spec){
        *def_sort = SortArrival;
        *def_sort_rev = 0;
        return(0);
    }

    if(struncmp(sort_spec, "reverse", strlen(sort_spec)) == 0){
        *def_sort = SortArrival;
        *def_sort_rev = 1;
        return(0);
    }
     
    reverse = 0;
    if((sep = strindex(sort_spec, '/')) != NULL){
        *sep = '\0';
        fix_this = sep;
        sep++;
        if(struncmp(sep, "reverse", strlen(sep)) == 0)
          reverse = 1;
        else{
            *fix_this = '/';
            return(-1);
        }
    }

    for(x = 0; ps_global->sort_types[x] != EndofList; x++)
      if(struncmp(sort_name(ps_global->sort_types[x]),
                  sort_spec, strlen(sort_spec)) == 0)
        break;

    if(fix_this)
      *fix_this = '/';

    if(ps_global->sort_types[x] == EndofList)
      return(-1);

    *def_sort     = ps_global->sort_types[x];
    *def_sort_rev = reverse;
    return(0);
}


/*----------------------------------------------------------------------
  Compare raw message numbers 
 ----*/
int
pine_compare_long(const qsort_t *a, const qsort_t *b)
{
    long *mess_a = (long *)a, *mess_b = (long *)b, mdiff;

    return((mdiff = *mess_a - *mess_b) ? ((mdiff > 0L) ? 1 : -1) : 0);
}

/*
 * reverse version of pine_compare_long
 */
int
pine_compare_long_rev(const qsort_t *a, const qsort_t *b)
{
    long *mess_a = (long *)a, *mess_b = (long *)b, mdiff;

    return((mdiff = *mess_a - *mess_b) ? ((mdiff < 0L) ? 1 : -1) : 0);
}


long *g_score_arr;

/*
 * This calculate all of the scores and also puts them into a temporary array
 * for speed when sorting.
 */
void
build_score_array(MAILSTREAM *stream, MSGNO_S *msgmap)
{
    SEARCHSET *searchset;
    long       msgno, cnt, nmsgs, rawmsgno;
    long       score;
    MESSAGECACHE *mc;

    nmsgs = mn_get_total(msgmap);
    g_score_arr = (long *) fs_get((nmsgs+1) * sizeof(score));
    memset(g_score_arr, 0, (nmsgs+1) * sizeof(score));

    /*
     * Build a searchset that contains everything except those that have
     * already been looked up.
     */

    for(msgno=1L; msgno <= stream->nmsgs; msgno++)
      if((mc = mail_elt(stream, msgno)) != NULL)
        mc->sequence = 0;

    for(cnt=0L, msgno=1L; msgno <= nmsgs; msgno++){
        rawmsgno = mn_m2raw(msgmap, msgno);
        if(get_msg_score(stream, rawmsgno) == SCORE_UNDEF
           && rawmsgno > 0L && stream && rawmsgno <= stream->nmsgs
           && (mc = mail_elt(stream, rawmsgno))){
            mc->sequence = 1;
            cnt++;
        }
    }

    if(cnt){
        searchset = build_searchset(stream);
        (void)calculate_some_scores(stream, searchset, 0);
        mail_free_searchset(&searchset);
    }

    /*
     * Copy scores to g_score_arr. They should all be defined now but if
     * they aren't assign score zero.
     */
    for(rawmsgno = 1L; rawmsgno <= nmsgs; rawmsgno++){
        score = get_msg_score(stream, rawmsgno);
        g_score_arr[rawmsgno] = (score == SCORE_UNDEF) ? 0L : score;
    }
}


void
free_score_array(void)
{
    if(g_score_arr)
      fs_give((void **) &g_score_arr);
}


/*----------------------------------------------------------------------
  Compare scores
 ----*/
int
pine_compare_scores(const qsort_t *a, const qsort_t *b)
{
    long *mess_a = (long *)a, *mess_b = (long *)b, mdiff;
    long  sdiff;

    return((sdiff = g_score_arr[*mess_a] - g_score_arr[*mess_b])
            ? ((sdiff > 0L) ? 1 : -1)
            : ((mdiff = *mess_a - *mess_b) ? ((mdiff > 0) ? 1 : -1) : 0));
}


void
reset_sort_order(unsigned int flags)
{
    long rflags = ROLE_DO_OTHER;
    PAT_STATE     pstate;
    PAT_S        *pat;
    SortOrder     the_sort_order;
    int           sort_is_rev;

    /* set default order */
    the_sort_order = ps_global->def_sort;
    sort_is_rev    = ps_global->def_sort_rev;

    if(ps_global->mail_stream && nonempty_patterns(rflags, &pstate)){
        for(pat = first_pattern(&pstate); pat; pat = next_pattern(&pstate)){
            if(match_pattern(pat->patgrp, ps_global->mail_stream, NULL,
                             NULL, NULL, SE_NOSERVER|SE_NOPREFETCH))
              break;
        }

        if(pat && pat->action && !pat->action->bogus
           && pat->action->sort_is_set){
            the_sort_order = pat->action->sortorder;
            sort_is_rev    = pat->action->revsort;
        }
    }

    sort_folder(ps_global->mail_stream, ps_global->msgmap,
                the_sort_order, sort_is_rev, flags);
}