#if !defined(lint) && !defined(DOS) static char rcsid[] = "$Id: sort.c 1142 2008-08-13 17:22:21Z hubert@u.washington.edu $"; #endif /* * ======================================================================== * Copyright 2013-2021 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" #include "../pith/rules.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; char *rule_result; SortOrder new_sort = EndofList; int is_rev; rule_result = get_rule_result(FOR_SORT, ps_global->cur_folder, V_SORT_RULES); if (rule_result && *rule_result){ new_sort = (SortOrder) translate(rule_result, 1); is_rev = (SortOrder) translate(rule_result, 0) == EndofList ? 0 : 1; fs_give((void **)&rule_result); } if (new_sort != EndofList){ the_sort_order = new_sort; sort_is_rev = is_rev; } else{ /* 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); } SortOrder translate(char *order, int is_rev) { int rev = 0; if (!strncmp(order,"tHread", 6) || (rev = !strncmp(order,"Reverse tHread", 14))) return is_rev || rev ? SortThread : EndofList; if (!strncmp(order,"OrderedSubj", 11) || (rev = !strncmp(order,"Reverse OrderedSubj", 19))) return is_rev || rev ? SortSubject2 : EndofList; if (!strncmp(order,"Subject", 7) || (rev = !strncmp(order,"Reverse SortSubject", 15))) return is_rev || rev ? SortSubject : EndofList; if (!strncmp(order,"Arrival", 7) || (rev = !strncmp(order,"Reverse Arrival", 15))) return is_rev || rev ? SortArrival : EndofList; if (!strncmp(order,"From", 4) || (rev = !strncmp(order,"Reverse From", 12))) return is_rev || rev ? SortFrom : EndofList; if (!strncmp(order,"To", 2) || (rev = !strncmp(order,"Reverse To", 10))) return is_rev || rev ? SortTo : EndofList; if (!strncmp(order,"Cc", 2) || (rev = !strncmp(order,"Reverse Cc", 10))) return is_rev || rev ? SortCc : EndofList; if (!strncmp(order,"Date", 4) || (rev = !strncmp(order,"Reverse Date", 12))) return is_rev || rev ? SortDate : EndofList; if (!strncmp(order,"siZe", 4) || (rev = !strncmp(order,"Reverse siZe", 12))) return is_rev || rev ? SortSize : EndofList; if (!strncmp(order,"scorE", 5) || (rev = !strncmp(order,"Reverse scorE", 13))) return is_rev || rev ? SortScore : EndofList; return EndofList; }