head 1.1;A access ; symbols ; locks ; strict; comment @ * @; 1.1 date 85.03.31.18.10.53; author bbanerje; state Exp; branches ; next ; desc @@ 1.1 log @Initial revision @ text @#define ACT /* Update screen according to screen lines generated by xdisp.c Copyright (c) 1981,1980 James Gosling Enhancements copyright (c) 1984 Fen Labalme, Chris Torek and Richard Stallman. Distributed by Fen Labalme, with permission from James Gosling. This file is part of GNU Emacs. GNU Emacs is distributed in the hope that it will be useful, but without any warranty. No author or distributor accepts responsibility to anyone for the consequences of using it or for whether it serves any particular purpose or works at all, unless he says so in writing. Everyone is granted permission to copy, modify and redistribute GNU Emacs, but only under the conditions described in the document "GNU Emacs copying permission notice". An exact copy of the document is supposed to have been given to you along with GNU Emacs so that you can know how you may redistribute it all. It should be in a file named COPYING. Among other things, the copyright notice and this notice must be preserved on all copies. */ /**************************************************************** /-------------\ / \ / \ / \ | XXXX XXXX | | XXXX XXXX | | XXX XXX | \ X / --\ XXX /-- | | XXX | | | | | | | I I I I I I I | | I I I I I I | \ / -- -- \-------/ XXX XXX XXXXX XXXXX XXXXXXXXX XXXXXXXXXX XXXXX XXXXX XXXXXXX XXXXX XXXXX XXXXXXXXX XXXXXXXXXX XXXXX XXXXX XXX XXX ************** * BEWARE!! * ************** All ye who enter here: Most of the code in this module is twisted beyond belief! Tread carefully. If you think you understand it, You Don't, So Look Again. ****************************************************************/ #include "config.h" #include "display.h" #include #undef NULL #include #define min(a,b) ((a)<(b) ? (a) : (b)) #define max(a,b) ((a)>(b) ? (a) : (b)) #define hidden static #define visible #define procedure #define function hidden CheckForInput; /* -ve iff UpdateLine should bother checking for input */ /* Returns a pointer to a new line object, either from the free list or from the general unix pool */ struct display_line * new_display_line () { register struct display_line *p = FreeLines; if (p) { FreeLines = p -> next; if (p -> hash != 12345) { FreeLines = 0; return new_display_line (); } } else p = (struct display_line *) malloc (sizeof *p + ScreenWidth - MScreenWidth); p -> length = 0; p -> hash = 0; p -> highlighted = 0; p -> physical = 0; return p; } /* 'ReleaseLine' returns a line object to the free list. It is ok to try to free the same line twice; it really gets freed only once. */ ReleaseLine (p) register struct display_line *p; { if (p && p->hash != 12345) { p -> next = FreeLines; p -> hash = 12345; FreeLines = p; } } /* 'hashline' computes a hash value for a line, unless the hash value is already known. This hash code has a few important properties: - it is independant of the number of leading and trailing spaces - it will never be zero As a side effect, an estimate of the cost of redrawing the line is calculated */ hidden procedure hashline (p) register struct display_line *p; { register char *c, *l; register h; if (!p || p -> hash) { if (p && p->hash==12345) printf ("****Free line in screen"); return; } h = 0; /* c gets pointer to start of line body, l pointer to after end of it */ c = p->body; l = p->body + p->length; /* narrow the two pointers in, to flush leading and trailing spaces */ while (l >= c && *--l == ' ') p->length --; if (!tt.t_needspaces) while (c <= l && *c == ' ') c++; /* Determine cost and hash from what remains within */ p -> DrawCost = l - c + 1; if (p -> highlighted) { p -> hash = -200; return; } while (c <= l) h = (h << 5) + h + *c++; p -> hash = h!=12345 && h ? h : 1; } /* j 1 2 3 4 ... +---+---+---+---+--- 1 | | | | | +---+---+---+---+--- Each Mij represents the minimum cost of 2 | | \| ^ | | rearranging the first i lines to map onto i +---+---\-|-+---+--- the first j lines (the j direction 3 | | <-+Mij| | represents the desired contents of a line, +---+---+---+---+--- i the current contents). 4 | | | | | +---+---+---+---+--- . | | | | | . . The algorithm used is a dynamic programming one, where M[i,j] = min (M[i-1,j]+dcost, # UP, implies delete M[i,j-1]+icost+redraw cost, # LEFT, implies ins+redraw M[i-1,j-1]+rewrite cost) # BACK, implies rewrite (It is not necessary to count a redraw cost for UPs as they force an equivalent number of LEFTs at some point.) The rewrite cost for a line is its redraw cost, unless line i matches line j, where it is free. The UP and LEFT cases must also add the cost for doing an insert or delete. This is actually rather tricky: the cost for an ID varies with the position above the bottom of the screen, and sometimes with the number of line IDs. As it turns out we can just look at the UP'th or LEFT'th cell to see whether this is the first of a sequence. After we have finished putting UPs, LEFTs, and BACKs in the matrix, we start at the lower right corner and work backward, following the arrows up, left, or back, eventually reaching the top left. Going up implies a deletion; going left implies insertion and rewrite; and every back implies a rewrite of old line i to new line j. There is an exception: UPs along the right edge of the matrix, and LEFTs along the bottom, are merely establishing a starting position and do not cause I/D operations (doing I/D there would be pointless anyway). (LEFTs do still cause redraws.) Note that the elements along the left edge (j=0) are constant, and that the elements along the top (i=0) are constants plus the redraw sum for all lines <= j. */ static calcM (matrix) struct Msquare *matrix; { register struct Msquare *p, *p_up; register struct display_line *l; register int i; register fixedpoint cost; int istart; static fixedpoint *ILp, *ILnp, *DLp, *DLnp; if (!IDValid) CalcIDCosts (); #ifdef DisplayDebug if (IDdebug >= 2) PrintIDCosts (); #endif DisplayDebug if (tt.t_window) { /* If WindowSize != ScreenLength, then the screen has effectively been made smaller and ILcost etc. should change. As it turns out the change can be simulated by starting in the middle of ILcost etc., so we set up these pointers. (They are declared 'static' simply because that produces better code. This routine is never called recursively.) */ i = ScreenLength - WindowSize; } else i = 0; ILp = &ILcost[i]; ILnp = &ILncost[i]; DLp = &DLcost[i]; DLnp = &DLncost[i]; /* Deal with any lines at top of screen that require no change */ for (istart = 0; istart <= WindowSize; istart++) { if (!DesiredScreen[istart] || (PhysScreen[istart] && PhysScreen[istart]->hash == DesiredScreen[istart]->hash)) { p = matrix + istart * (WindowSize + 1) + istart; p->cost = 0; p->fromi = istart - 1; p->fromj = istart - 1; } else break; } { /* First, set up the cost values along the edges of the matrix */ register fixedpoint *ip = ILinit + istart - 1; register fixedpoint dc; cost = itofixp (0); dc = DLcost[istart - 1]; p_up = p; for (i = istart; i <= WindowSize; i++) { if (l = DesiredScreen[i]) cost += itofixp (l -> DrawCost); p_up++; /* p_up points to M[istart - 1][i] */ p_up -> cost = cost + *ip++; p_up -> fromi = istart - 1; p_up -> fromj = istart - 1; p += WindowSize + 1; /* p points to M[i][istart - 1] */ p -> cost = dc; dc += DLncost[istart - 1]; p -> fromi = istart - 1; p -> fromj = istart - 1; } } /* Now fill in the entire interior of the matrix. */ for (i = istart; i <= WindowSize; i++) { register int j, from, IsBack; p = matrix + i * (WindowSize + 1) + istart - 1; p_up = p - WindowSize - 1; for (j = istart; j <= WindowSize; j++) { /* p = &M[i][j]; */ p++; p_up++; if (l = DesiredScreen[j]) { if (PhysScreen[i] && PhysScreen[i] -> hash == l -> hash) cost = itofixp (0); else cost = itofixp (l -> DrawCost); } else cost = itofixp (0); /* start by assuming BACK */ /* p -> cost = cost + M[i - 1][j - 1].cost; */ p -> cost = cost + p_up[-1].cost; p -> fromi = i - 1; p -> fromj = j - 1; /* then see if we want an UP (delete) */ /* cost = M[i - 1][j].cost + dcost (); */ cost = p_up -> cost; if (cost < p -> cost) {/* figure out dcost() */ IsBack = 0; if (p_up -> fromj != j) { from = i - 1; if (p_up -> fromi != from) IsBack++; if (j != WindowSize) cost += DLp[from];/* first of a sequence */ } else { from = p_up -> fromi; if (j != WindowSize) cost += DLnp[from];/* another UP */ } if (cost < p -> cost + IsBack) { p -> cost = cost;/* delete wins */ p -> fromi = from; p -> fromj++; } } /* and finally see if we really want a LEFT (insert) */ /* cost = M[i][j - 1].cost + reDrawCost + icost (); */ cost = p[-1].cost; cost += l ? itofixp (l -> DrawCost) : itofixp (0); if (cost < p -> cost) {/* figure out icost () */ IsBack = 0; if (p[-1].fromi != i) { from = j - 1; if (p_up -> fromj != from) IsBack++; if (i != WindowSize) cost += ILp[from];/* first of a sequence */ } else { from = p[-1].fromj; if (i != WindowSize) cost += ILnp[from];/* another LEFT */ } if (cost < p -> cost + IsBack) { p -> cost = cost;/* insert wins */ p -> fromi = i; p -> fromj = from; } } } } #ifdef DisplayDebug if (IDdebug) PrintM (matrix); #endif DisplayDebug } /* modify current screen line 'old' to match desired line 'new', the old line is at position ln. Each line is scanned and partitioned into 4 regions: <----m1-----><-od--><----m2-----> old: " Twas brillig and the slithy toves" new: " Twas brillig where a slithy toves" <-nsp--><----m1-----><-nd--><----m2-----> nsp, osp - number of leading spaces on each line m1 - length of a leading matching sequence m2 - length of a trailing matching sequence nd, od - length of the differing sequences */ UpdateLine (old, new, ln) register struct display_line *old, *new; { register char *op, *np, *ol, *nl; int osp, nsp, m1, m2, od, nd, OldHL, NewHL, t, OldLineWipeTo; if (old == new) return; if (old) { op = old -> body; ol = &old -> body[OldLineWipeTo = old -> length]; OldHL = old -> highlighted; } else op = "", ol = op, OldHL = 0, OldLineWipeTo = 1; if (new) { np = new -> body; nl = &new -> body[new -> length]; NewHL = new -> highlighted; } else np = "", nl = np, NewHL = 0; osp = nsp = m1 = m2 = od = nd = 0; /* calculate the magic parameters */ if (NewHL == OldHL) { while (*--ol == ' ' && ol >= op) --OldLineWipeTo; while (*--nl == ' ' && nl >= np); while (*op == ' ' && op <= ol) op++, osp++; while (*np == ' ' && np <= nl) np++, nsp++; #ifdef ACT if (!NewHL && ol < op && !tt.t_needspaces) osp = nsp; #endif if (tt.t_delchars || osp == nsp) while (*op == *np && op <= ol && np <= nl) op++, np++, m1++; #ifdef ACT if (!NewHL && op > ol && !tt.t_needspaces) while (*np == ' ' && np <= nl) np++, m1++; #endif /* Avoid doing insert/delete char just cause number of leading spaces differs when the following text does not match. */ if (m1 == 0 && osp != nsp) { if (osp > nsp) op -= osp - nsp, osp = nsp; else np -= nsp - osp, nsp = osp; } if (tt.t_delchars || ol - op == nl - np) while (*ol == *nl && op <= ol && np <= nl) ol--, nl--, m2++; } else { ol--; nl--; osp = 0; while (*np == ' ' && np < nl) np++, nsp++; } od = ol - op + 1; nd = nl - np + 1; /* forget matches which would be expensive to capitalize on */ if (m1 || m2) { register fixedpoint c0, c1, c2, c3; if (!DCICValid) CalcDCIC (); c0 = itofixp (nsp + m1 + m2); c1 = DCICcost[nsp - osp]; c3 = DCICcost[nd - od]; c2 = DCICcost[(nsp + nd) - (osp + od)]; c3 += c1; c1 += itofixp (m2); c2 += itofixp (m1); if (m2 && (c0 < c2 && c0 < c3 || c1 < c2 && c1 < c3)) { nd += m2; od += m2; ol += m2; nl += m2; m2 = 0; } if (m1 && (c0 < c1 && c0 < c3 || c2 < c1 && c2 < c3)) { nd += m1; od += m1; np -= m1; op -= m1; m1 = 0; } } if (RDdebug && (m1 || m2 || nd || od)) { fprintf (stderr, "%2d nsp=%2d osp=%2d m1=%2d nd=%2d od=%2d m2=%2d", ln, nsp, osp, m1, nd, od, m2); } (*tt.t_HLmode) (NewHL); if (NewHL != OldHL) { topos (ln, 1); wipeline (1, OldLineWipeTo); OldLineWipeTo = 1; } /* Perform the update. Note that, if not supposed to ins/del chars, we must have osp == nsp and od == nd at this point. The code below should be careful never to insert or delete characters when those equalities hold. */ if (m1 == 0) if (m2 == 0) { if (od == 0 && nd == 0) goto cleanup; #ifndef ACT if (od == 0 && !tt.t_needspaces) osp = nsp; #endif topos (ln, (t = min (nsp, osp)) + 1); INSmode (0); if (nsp > osp) blanks (nsp - osp); dumpstring (np, nl); if (nsp + nd < osp + od) wipeline (0, OldLineWipeTo); } else { /* m1==0 && m2!=0 && (nd!=0 || od!=0) */ t = (nsp + nd) - (osp + od); topos (ln, min (nsp, osp) + 1); if (nsp > osp) np -= nsp - osp; if (t >= 0) { if (nl - t >= np) INSmode (0), dumpstring (np, nl - t); if (t > 0) INSmode (1), dumpstring (nl - t + 1, nl); } else INSmode (0), dumpstring (np, nl), deletechars (-t); } else { /* m1!=0 */ register lsp = osp; if (nsp < osp) { topos (ln, 1); deletechars (osp - nsp); OldLineWipeTo -= osp - nsp; lsp = nsp; } if (m2 == 0) { if (nd == 0 && od == 0) { if (nsp > osp) { topos (ln, 1); INSmode (1); blanks (nsp - osp); } goto cleanup; } #ifndef ACT if (od == 0 && !tt.t_needspaces) while (*np==' ') np++, m1++; #endif topos (ln, lsp + m1 + 1); INSmode (0); dumpstring (np, nl); if (nd < od) wipeline (0, OldLineWipeTo); if (nsp > osp) { topos (ln, 1); INSmode (1); blanks (nsp - osp); } } else { /* m1!=0 && m2!=0 && (nd!=0 || od!=0) */ topos (ln, lsp + m1 + 1); t = nd - od; if (nd > 0 && od > 0) INSmode (0), dumpstring (np, np + min (nd, od) - 1); if (nd < od) deletechars (od - nd); else if (nd > od) INSmode (1), dumpstring (np + od, nl); if (nsp > osp) { topos (ln, 1); INSmode (1); blanks (nsp - osp); } } } cleanup: /* Mark physical screen as containing the line `new' */ PhysScreen[ln] = new; #ifdef FIONREAD if(--CheckForInput<0 && ((stdout->_ptr - stdout->_base) > 20)) { fflush (stdout); #ifdef TIOCOUTQ /* prevent system I/O buffering */ if (baud_rate < 2400) { int outq; ioctl (fileno (stdin), TIOCOUTQ, &outq); outq *= 100; outq /= baud_rate; /* outq is now in 1/10th of seconds */ /* COMPILER BUG: (unsigned) cast on parameter to sleep makes the division be unsigned, instead of the result. */ if (outq >= 15) sleep ((outq - 5) / 10); } #endif detect_input_pending (); CheckForInput = baud_rate / 2400; } #endif } /* At the time this function is called, no line is common to PhysScreen and DesiredScreen. That is true again when this function returns. */ /* `force' nonzero means do not stop for pending input */ /* Value is nonzero if redisplay stopped due to pending input */ visible procedure UpdateScreen (force, inhibit_hairy_id) int force; int inhibit_hairy_id; { register int n; register int c; int pause; struct Msquare *matrix; extern input_pending; CheckForInput = baud_rate / 2400; if (ScreenGarbaged) { reset (); fflush (stdout); ScreenGarbaged = 0; inhibit_hairy_id = 1; for (n = 0; n <= ScreenLength; n++) { ReleaseLine (PhysScreen[n]); PhysScreen[n] = 0; } } bcopy (PhysScreen, OPhysScreen, sizeof PhysScreen); detect_input_pending (); if (tt.t_UpdateBegin) (*tt.t_UpdateBegin) (); if (tt.t_ILov == MissingFeature || tt.t_DLov == MissingFeature) inhibit_hairy_id = 1; /* Don't compute for i/d line if just want cursor motion. */ for (n = 1; n <= ScreenLength; n++) if (DesiredScreen[n]) break; if (n > ScreenLength) inhibit_hairy_id = 1; if (!inhibit_hairy_id) { for (n = 1; n <= ScreenLength; n++) { if (DesiredScreen[n] == 0) DesiredScreen[n] = PhysScreen[n]; else hashline (DesiredScreen[n]); hashline (PhysScreen[n]); } c = baud_rate / 2400; if (c > 3) c = 3; /* Count number of lines changed. If small enough, skip i/d calc */ for (n = ScreenLength; n >= 1 && c >= 0; n--) if (PhysScreen[n] != DesiredScreen[n] && PhysScreen[n] && DesiredScreen[n] -> hash != PhysScreen[n] -> hash) c--; /* If changes small, force to completion, don't allow preemption. */ if (c >= 0) force = 1; else { /* Perhaps can omit last few lines from i/d calc, for more speed */ for (n = ScreenLength; n >= 1 && (PhysScreen[n] == DesiredScreen[n] || (PhysScreen[n] ? DesiredScreen[n]->hash == PhysScreen[n]->hash : DesiredScreen[n]->length == 0)); n--); WindowSize = n; if (tt.t_window) (*tt.t_window) (n); /* Calculate and perform the insert/delete */ matrix = (struct Msquare *) alloca ((WindowSize + 1) * (WindowSize + 1) * sizeof *matrix); calcM (matrix); do_scrolling (matrix); } } /* Update the individual lines as needed. Do bottom line first. */ if (DesiredScreen[ScreenLength] && DesiredScreen[ScreenLength] != PhysScreen[ScreenLength]) UpdateLine (PhysScreen[ScreenLength], DesiredScreen[ScreenLength], ScreenLength); for (n = 1; n <= ScreenLength && (force || !input_pending); n++) { if (DesiredScreen[n] && PhysScreen[n] != DesiredScreen[n]) UpdateLine (PhysScreen[n], DesiredScreen[n], n); } pause = (n <= ScreenLength); display_completed = !pause; /* RMS: free any lines still in desired screen but not in phys screen */ /* Free any lines that used to be in phys screen but are no longer */ for (n = 1; n <= ScreenLength; n++) if (PhysScreen[n]) PhysScreen[n]->physical = 1; for (n = 1; n <= ScreenLength; n++) { if (DesiredScreen[n]) { if (!DesiredScreen[n]->physical) ReleaseLine (DesiredScreen[n]); DesiredScreen[n] = 0; } if (OPhysScreen[n]) { if (!OPhysScreen[n]->physical) ReleaseLine (OPhysScreen[n]); } } for (n = 1; n <= ScreenLength; n++) if (PhysScreen[n]) PhysScreen[n]->physical = 0; (*tt.t_HLmode) (0); if (!pause) topos (cursY, max (min (cursX, ScreenWidth), 1)); if (tt.t_UpdateEnd) (*tt.t_UpdateEnd) (); fflush (stdout); return pause; } /* Terminal driver function for the user's terminal. Most often it is TrmTERM. */ int (*terminal_driver) (); char *terminal_type; /* Initialization done when Emacs fork is started, before doing stty. */ /* Determine terminal type and set terminal_driver */ /* Then invoke its decoding routine to set up variables in the terminal package */ init_display () { struct termtype { char *name; int cmplen; int (*startup) (); }; /* A terminal driver is selected by looking up the value of the environment variable TERM in the following table. The string is matched against the name, considering at most "cmplen" characters to be significant. "startup" points to the function that sets up the terminal driver. The driver is called with the terminal type as a parameter and is free to use that to specialize itself. */ struct termtype *p; extern TrmAmb (); extern TrmC100 (); extern TrmVT100 (); extern TrmTERM (); static struct termtype termtable[] = { "aaa", 3, TrmAmb, "amb", 99, TrmAmb, "ambassador", 99, TrmAmb, "C10", 3, TrmC100, "c10", 3, TrmC100, "Concept", 7, TrmC100, "concept", 7, TrmC100, "perq", 4, TrmC100, "vt1", 3, TrmVT100, 0, 0, 0 }; register char *tname = (char *) getenv ("TERM"); extern short ospeed; static short baud_convert[] = { 0, 50, 75, 110, 135, 150, 200, 300, 600, 1200, 1800, 2400, 4800, 9600, 19200, 300 }; struct sgttyb sg; bzero (&tt, sizeof tt); MetaFlag = 0; terminal_type = tname; for (p = termtable; p -> name; p++) if (strncmp (p -> name, tname, p -> cmplen) == 0) { terminal_driver = (*p -> startup); break; } if (p -> name == 0) terminal_driver = TrmTERM; gtty (fileno (stdin), &sg); ospeed = sg.sg_ospeed; baud_rate = sg.sg_ospeed == 0 ? 1200 : sg.sg_ospeed < sizeof baud_convert / sizeof baud_convert[0] ? baud_convert[sg.sg_ospeed] : 9600; /* Now call terminal driver to initialize the contents of tt */ (*terminal_driver) (terminal_type); /* Fix up the contents of tt */ if (tt.t_length > MScreenLength) tt.t_length = MScreenLength; if (tt.t_width > MScreenWidth) tt.t_width = MScreenWidth; free_all_display_lines (); RDdebug = 0; /* line redraw debug switch */ IDdebug = 0; /* line insertion/deletion debug */ cursX = 1; /* X and Y coordinates of the cursor */ cursY = 1; /* between updates. */ } /* Reinitialize the terminal and I/O system. Called from InitDsp */ term_init () { (*tt.t_init) (baud_rate); (*tt.t_reset) (); } /* Debugging routines -- called from sdb only */ #ifdef DisplayDebug static PrintM (matrix) register struct Msquare *matrix; { register i, j; register struct Msquare *p; fprintf (stderr, "\nM:\n"); for (i = 0; i <= WindowSize; i++) { p = matrix + (ScreenLength + 1) * i; for (j = 0; j <= WindowSize; j++) { fprintf (stderr, "%5.2f(%d,%d)%c", fixptofl (p -> cost), p -> fromi, p -> fromj, p -> fromi == i ? '<' : p -> fromj == j ? '^' : '\\'); p++; } fprintf (stderr, "\n"); } fflush (stderr); } #endif DisplayDebug visible procedure NoOperation () {} @