.Vx 17 11 November 87 1 32 "ROB PIKE" "THE TEXT EDITOR SAM"
.ds DY "31 May 1987
.ds DR "Revised 1 July 1987
.de CW \" puts first arg in CW font, same as UL; maintains font
\%\&\\$3\f(CW\\$1\fP\&\\$2
..
.de Cs
.br
.fi
.ft 2
.ps -2
.vs -2
..
.de Ce
.br
.nf
.ft 1
.ps
.vs
.sp
..
.TL
El Editor de Texto \&\f(CWsam\fP
.AU
Rob Pike
rob@plan9.bell-labs.com
.AB
.LP
.CW Sam
es un editor de texto multi-fichero interactivo pensado para pantallas gr�ficas.
Un lenguage de comandos textual suplementa el interfaz gr�fico basado en el rat�n y en copiar y pegar para hacer f�cil la especificaci�n de tareas repetitivas o complejas.
El lenguaje se caracteriza por la composici�n de expresiones regulares que describen la estructura del texto que est� siendo modificado.
El tratamiento de los ficheros como bases de datos, con los cambios guardados como transacciones at�micas, gu�a la implementaci�n y hace que el mecanismo de deshacer general sea directo.
.PP
.CW Sam
est� implementado como dos procesos conectados por un stream de bajo ancho de banda, un proceso que maneja la pantalla y otro los algoritmos de edici�n. Por tanto puede ejecutarse con el proceso de manejo de pantalla en un terminal gr�fico y el del propio editor en un host local, con ambos procesos en un host con pantalla gr�fica o con el proceso de pantalla en un terminal y el editor en un host remoto.
Suprimiendo el proceso de pantalla, puede ejecutarse incluso sin ning�na terminal gr�fica.
.PP
Este documento est� reimpreso de Software\(emPractice and Experience,
Vol 17, number 11, pp. 813-845, November 1987.
El documento no ha sido actualizado para los manuales de Plan 9. Aunque
.CW Sam
no ha cambiado mucho desde que fu� escrito, el sistema que lo rodea s�.
A�n as�, la descripci�n todav�a se mantiene como la mejor introducci�n a este editor.
.AE
.SH
Introducci�n
.LP
.CW Sam
es un editor de texto interactivo que combina la edici�n interactiva de cortar y pegar con un inusual lenguaje de comandos basado en la composici�n de expresiones regulares.
Est� escrito como dos programas: uno, la parte "host", corre en un sistema UNIX, implementa el lenguaje de comandos y proporciona acceso a los ficheros; la otra, la parte "terminal", corre as�ncronamente en una m�quina con rat�n y pantalla gr�fica y soporta la edici�n interactiva.
La parte host puede incluso correr aislada de cualquier terminal ordinario para editar textos usando el lenguaje dfe comandos, m�s bien como un editor de lineas tradicional, sin asistencia de rat�n o pantalla.
Generalmente, la parte de terminal corre en un terminal Blit\u\s-4\&1\s+4\d (realmente en un Teletype DMD 5620, la versi�n de producci�n del Blit), cuya conexi�n a host es un enlace RS232 ordinario a 9600 bps; en el ordenador SUN los procesos de host y de terminal corren en una sola m�quina, conectados por un pipe.
.PP
.CW Sam
edita texto ASCII sin interpretar. No tiene capacidad para tipos de letra, graficos o tablas, a diferencia de MacWrite,\u\s-4\&2\s+4\d Bravo,\u\s-4\&3\s+4\d Tioga\u\s-4\&4\s+4\d
or Lara.\u\s-4\&5\s+4\d
Tambi�n, a diferencia de ellos, tiene un lenguaje de comandos rico.
Also unlike them, it has a rich command language.
(En este documento, la frase
.I
lenguaje de comandos
.R
se refiere a comandos de texto; los comandos activados desde el rat�n forman el
.I lenguaje de rat�n.)
.CW Sam
desarrollado como editor para programadores, intenta unir los estilos del editor de texto de UNIX
.CW ed \u\s-4\&6,7\s+4\d
con el de los editores interactivos con copy-paste para proporcionar un interfaz de rat�n confortable con un lenguaje de comandos s�lido basado en expresiones regulares.
El lenguaje de comandos se desarroll� m�s que el lenguaje de rat�n, y adquiri� una notaci�n para describir la estructura de los ficheros de un modo mas rico que como una simple secuencia de lineas, usando una sintaxis de flujo de datos para especificar cambios.
.PP
El estilo interactivo est� influenciado por
.CW jim ,\u\s-4\&1\s+4\d
un antiguo editor con copy-paste para el Blit, y por
.CW mux ,\u\s-4\&8\s+4\d
el sistema de ventanas del Blit.
.CW Mux
mezcla el sistema de ventanas original de Blit,
.CW mpx ,\u\s-4\&1\s+4\d
con la edici�n copy-paste, formando algo como una versi�n multiplexada de
.CW jim
que edita la salida (y la entrada tambi�n) de sesiones de comandos en lugar de ficheros.
.PP
La primera parte de este documento describe el lenguaje de comandos, luego el lenguaje de rat�n y c�mo ambos interact�an.
Luego se describe la implementaci�n, primero de la parte de host y luego de la de terminal.
Un principio que influenci�n el dise�o de
.CW sam
es que no debe tener l�mites expl�citos, como tama�o de fichero, o longitud de linea.
Una consideraci�n secundaria es que sea eficiente.
Para conseguir estos dos objetivos se requiere un m�todo que maneje de manera eficiente cadenas gigantes (ficheros) sin romperlas en lineas, quiz� mientras se realizan cientos de cambios bajo el control del lenguaje de comandos.
El m�todo de
.CW sam
consiste en tratar el fichero como una base de datos con transacciones, implementando los cambios como actualizaciones at�micas. Estas actualizaciones pueden volverse atr�s f�cilmente para deshacer cambios.
La eficiencia se consigue por medio de una colecci�n de cach�s que minimizan el tr�fico de disco y el movimiento de datos, tanto en cada parte del programa como entre ambas.
.PP
La parte de terminal de
.CW sam
es bastante directa.
Lo mas interesante es c�mo las dos mitades del editor permanecen sincronizadas cuando alguna de ellas inicia in cambio.
Esto se consigue por medio de una estructura de datos que organiza las comunicaciones y que es mantenida en paralelo por ambas mitades.
.PP
La �ltima parte del documento es una cr�nica de la escritura de
.CW sam
y explica las lecciones que fueron aprendidads a trav�s de su desarrollo y uso.
.PP
El documento es largo, pero esta compuesto de dos partes de una longitud razonable:
la descripci�n del interfaz de usuario de
.CW sam
y la explicaci�n de su implementaci�n.
Est�n combinadas dado que la implementaci�n est� fuertemente influenciada por el interfaz de usuario, y viceversa.
.SH
El interfaz
.LP
.CW Sam
es un editor de texto para m�ltiples ficheros.
Los nombres de fichero pueden proporcionarse cuando es invocado:
.P1
sam file1 file2 ...
.P2
y hay comandos para agregar nuevos ficheros y descartar los que no se necesitan.
Los ficheros no se leen hasta que es necesario completar alg�n comando.
Las operaciones de edici�n se aplican a una copia interna que se hace cuando el fichero se lee; el fichero UNIX asociado con la copia se cambia solamente con un comando expl�cito.
Para simplificar explicaci�n, llamaremos a la copia interna
.I fichero ,
mientras que a la copia residente en disco
.I
fichero en disco.
.R
.PP
.CW Sam
est� normalmente conectado a una pantalla gr�fica que presenta un editor con copy-paste basado en rat�n.
En este modo el lenguaje de comandos est� todav�a disponible:
el texto se escribe en una ventana especial llamada
.I ventana,
.CW sam.
es interpretado como comandos que han de ejecutarse en el fichero actual.
La edici�n copy-paste puede usarse en cualquier ventana
\(em incluso en la ventana
.CW sam
para construir comandos.
El otro modo de operaci�n, invocado arrancando
.CW sam
con la opci�n
.CW -d
(de "no download"), no utiliza el rat�n ni la pantalla grafica, pero a�n permite editar usando el lenguaje de comandos de texto, incluso en un terminal ordinario, interactivamente o desde un script.
.PP
Las siguientes secciones describen primero el lenguaje de comandos (bajo
.CW sam\ -d
y la ventana
.CW sam
), y despu�s el interfaz de rat�n.
Estos dos lenguajes son casi independientes, pero se conectan por medio del
.I texto
.I actual,
que se describe m�s abajo.
.SH 2
El Lenguaje de Comandos
.LP
Un fichero consiste en sus contenidos, que es un array de caracteres, (es decir, una cadena); el
.I nombre
del fichero en disco asociado; el
.I
bit de modificaci�n
.R
que dice si los contenidos corresponden a los del fichero en disco;
y una subcadena de sus contenidos, llamada el
.I
texto actual
.R
�
.I punto
(ver Figuras 1 y 2).
??????????
Si el texto actual es la cadena vac�a, el punto est� entre caracteres.
If the current text is a null string, dot falls between characters.
??????????
El
.I valor
del punto es la situaci�n del texto actual; los
.I contenidos
del punto son los caracteres que contiene.
.CW Sam
imprime al texto una interpretaci�n no bi-dimensional, como filas y columnas: el texto es siempre uni-dimensional.
Incluso la idea de una "linea" de texto es entendida por la mayor�a de programas UNIX como \(em una secuencia de caracteres terminados por un caracter de newline \(em es solo ligeramente soportada.
.PP
El
.I
fichero actual
.R
es el fichero al que se refieren los comandos de edici�n.
El texto actual es en cambio el punto del fichero actual.
Si un comando no nombra expl�citamente un fichero o pieza de texto concretos, se asume que se aplica al texto actual.
is the file to which editing commands refer.
De momento, ign�rese la presencia de m�ltiples ficheros, considerando que hay solamente uno.
.KF L
.BP fig1.ps 3.5i
.Cs
Figura 1. Una t�pica pantalla de
.CW sam
presentando el men� de edici�n.
La ventana de comandos
.CW sam
esta en medio, con ventanas de ficheros encima y debajo.
(El interfaz de usuario facilita la creaci�n de estas ventanas contiguas.)
(The user interface makes it easy to create these abutting windows.)
La ventana parcialmente cubierta es la de un tercer fichero.
La ventana superior es en la que se aplican los caracteres tecleados y las operaciones de rat�n, lo cual se indica con su borde mas grueso.
Cada ventana tiene su texto actual resaltado en video inverso.
El texto actual de la ventana de
.CW sam
es la cadena vac�a, en la �ltima linea visible, indicada por la barra vertical.
Ver tambi�n la Figura 2.
.Ce
.KE
.PP
Los comandos tienen nombres de una letra.
Excepto para los de no-edici�n, como escribir el fichero a disco, la mayor�a de ellos hacen alg�n cambio al texto del punto y hacen que �ste valga el texto resultante del cambio.
Por ejemplo, el comando delete
.CW d ,
borra el texto en el punto, reemplazandolo por la cadena vac�a y poniendo el punto al resultado.
El comando change
.CW c ,
reemplaza el punto por el texto delimitado por caracteres de puntuaci�n arbitrarios, convencionalmente la barra inclinada.
As�,
.P1
c/Peter/
.P2
reemplaza el texto del punto por la cadena
.CW Peter .
De manera parecida,
.P1
a/Peter/
.P2
(append) agrega la cadena despu�s del punto, y
.P1
i/Peter/
.P2
(insert) inserta la cadena antes del punto.
Los tres dejan el punto con el valor del nuevo texto,
.CW Peter .
.PP
Los saltos de linea son parte de la sintaxis de los comandos:
el caracter newline lexicamente termina un comando.
Dentro de un texto insertado, sin embargo, los saltos de linea nunca est�n implicitos.
Pero dado que a veces es conveniente insertar m�ltiples lineas de texto,
.CW sam
tiene una sintaxis especial para ese caso:
.P1
a
algunas lineas de texto a insertar en el fichero, terminadas por una
linea que consta de un �nico punto.
\&.
.P2
En la sintaxis on-line, el caracter newline puede especificarse con un
escape estilo C, as� que
.P1
c/\en/
.P2
reemplaza el punto por un solo caracter newline.
.PP
.CW Sam
tiene tambien un comando substitute (sustituir),
.CW s :
.P1
s/\f2expresi�n\fP/\f2sustituci�n\fP/
.P2
sustituye el texto sustituci�n en la primera ocurrencia en el punto de la expresi�n regular.
As�, si el punto es la cadena
.CW Peter ,
el comando
.P1
s/t/st/
.P2
lo cambia por
.CW Pester .
En general,
.CW s
es innecesario, pero se ha heredado de
.CW ed
y tiene algunas variaciones convenientes.
Por ejemplo, el texto de sustituci�n puede incluir texto encontrado, especificado por
.CW & :
.P1
s/Peter/Oh, &, &, &, &!/
.P2
.PP
Hay tambi�n tres comandos que aplican programas al texto:
.P1
< \f2programa UNIX\fP
.P2
reemplaza el punto por la salida del programa UNIX.
De modo parecido, el comando
.CW >
ejecuta el programa con el punto como su entrada estandar, y
.CW |
hace ambas cosas. Por ejemplo,
.P1
| sort
.P2
reemplaza el punto por el resultado de aplicarle la utilidad estandar de ordenaci�n.
Una vez m�s, los saltos de linea no tienen especial significado para estos comandos de
.CW sam.
El texto sobre el que actuan estos comandos o que es resultado de ellos no debe estar necesariamente separado por saltos de linea, aunque para la conexi�n entre programas UNIX, pueden ser necesarios para obedecer a las convenciones.
.PP
Un comando m�s:
.CW p
muestra los contenidos del punto.
La tabla I resume los comandos de
.CW sam.
.KF
.TS
center;
c s
lfCW l.
Tabla I. \f(CWSam\fP commands
.sp .4
.ft CW
_
.ft
.sp .4
\f1Comandos de texto\fP
.sp .4
_
.sp .4
a/\f2texto\fP/ Agrega texto despu�s del punto
c/\f2texto\fP/ Cambia el texto del punto
i/\f2texto\fP/ Inserta texto antes del punto
d Borra el texto del punto
s/\f2regexp\fP/\f2texto\fP/ Sustituye coincidencias de la expresi�n regular en el punto por texto
m \f2direcci�n\fP Mueve el texto del punto a despu�s de la direcci�n
t \f2direcci�n\fP Copia el texto del punto a despu�s de la direcci�n
.sp .4
_
.sp .4
\f1Comandos de pantalla\fP
.sp .4
_
.sp .2
p Muestra el contenido del punto
\&= Muestra el valor (numeros de linea y caracteres) del punto
.sp .4
_
.sp .4
\f1Comandos de fichero\fP
.sp .4
_
.sp .2
b \f2lista-de-ficheros\fP Pone como fichero actual el primer fichero de la lista que \f(CWsam\fP tiene en el men�
B \f2lista-de-ficheros\fP Igual que \f(CWb\fP, pero carga nuevos ficheros
n Muestra un men� con los nombres de todos los ficheros
D \f2lista-de-ficheros\fP Borra esos ficheros de \f(CWsam\fP
.sp .4
_
.sp .4
\f1Comandos de E/S\fP
.sp .4
_
.sp .2
e \f2nombrefichero\fP Reemplaza el fichero con el fichero en disco de ese nombre
r \f2nombrefichero\fP Reemplaza el punto por el contenido de ese fichero en disco
w \f2nombrefichero\fP Escribe el fichero actual en ese fichero en disco
f \f2nombrefichero\fP Asigna ese nombre al fichero y muestra una linea de men�
< \f2comando-UNIX\fP Reemplaza el punto por la salida estandar del comando
> \f2comando-UNIX\fP Envia el punto a la entrada estandar del comando
| \f2comando-UNIX\fP Reemplaza el punto por el resultado del comando aplicado al punto
! \f2comando-UNIX\fP Ejecuta el comando
.sp .4
_
.sp .4
\f1Bucles y condiciones\fP
.sp .4
_
.sp .2
x/\f2regexp\fP/ \f2comando\fP Para cada coincidencia de la expresi�n regular, pone el punto y ejecuta el comando
y/\f2regexp\fP/ \f2comando\fP Entre coincidencias adyacentes de la expresi�n regular, pone el punto y ejecuta el comando
X/\f2regexp\fP/ \f2comando\fP Ejecuta el comando en cada fichero cuya linea en el men� coincida con la expresi�n regular
Y/\f2regexp\fP/ \f2comando\fP Ejecuta el comando en cada fichero cuyo nombre no corresponda a una linea del men�
g/\f2regexp\fP/ \f2comando\fP Si el punto contiene una coincidencia de la expresi�n regular, ejecuta el comando
v/\f2regexp\fP/ \f2comando\fP Si el punto no contiene una coincidencia de la expresi�n regular, ejecuta el comando
.sp .4
_
.sp .4
\f1Miscelanea\fP
.sp .4
_
.sp .2
k Pone la direcci�n al valor del punto
q Sale
u \f2n\fP Deshace (Undo) los �ltimos \f2n\fP (por defecto 1) cambios
{ } Las llaves agrupan comandos
.sp .3
.ft CW
_
.ft
.TE
.sp
.KE
.PP
El valor del punto puede cambiarse especificando una
.I direcci�n
para el comando.
La direcci�n m�s simple es un n�mero de linea:
.P1
3
.P2
se refiere a la tercera linea del fichero, as� que
.P1
3d
.P2
borra la tercera lina del fichero, e impl�citamente renumera las lineas de forma que la antigua linea 4 es ahora la 4.
(Este es uno de los pocos sitios en los que
.CW sam
trata con lineas directamente.)
La linea
.CW 0
es la cadena vac�a al principio del fichero.
Si un comando consiste en solo una direcci�n, se ejecuta un comando
.CW p
as� que tecleando un simple
.CW 3
se muestra la linea 3 en el terminal.
Hay un par de direcciones b�sicas m�s:
el caracter (.) se refiere al punto; y un signo de dolar
.CW $ ) (
se refiere a la cadena vac�a que hay al final del fichero.
.PP
Una direcci�n es siempre una subcadena de un fichero.
As�, la direcci�n
.CW 3
se refiere a los caracteres que hay desde la segunda linea hasta el final de la tercera en el fichero.
Una
.I
direcci�n compuesta
.R
se construye con el operador coma
.P1
\f2direcci�n1\fP,\f2direcci�n2\fP
.P2
y se refiere a la subcadena del fichero desde el principio de
.I direcci�n1
hasta el final de
.I direcci�n2.
Por ejemplo, el comando
.CW 3,5p
muestra desde la tercera a la quinta lineas del fichero, y
.CW .,$d
borra el texto desde el principio del punto hasta el fin del fichero.
.PP
Estas direcciones son todas posiciones absolutas en el fichero, pero
.CW sam
tiene tambi�n direcciones relativas, indicadas por
.CW +
�
.CW - .
Por ejemplo,
.P1
$-3
.P2
es la tercera linea desde el final del fichero y
.P1
\&.+1
.P2
es la linea que est� despues del punto.
Si no aparece ninguna direcci�n a la izquierda del
.CW +
o del
.CW - ,
se asume el punto; si no aparece nada a la derecha se asume
.CW 1.
De este modo,
.CW .+1
puede ser abreviado a solamente un signo m�s.
.PP
El operador
.CW +
act�a relativo al final de su primer argumento, mientras que el operador
.CW -
act�a relativo al principio. As�,
.CW .+1
se reciere a la primera linea despu�s del punto,
.CW .-
indica la primera linea antes del punto, y
.CW +-
la linea que contiene el final del punto. (El punto puede extenderse a lo largo de varias linas y
.CW +
selecciona la linea que hay despu�s del punto, y luego
.CW -
vuelve atr�s una linea.)
.PP
El �ltimo tipo de direcci�n es una expresi�n regular, que se refiere al texto que coincide con la expresi�n. La expresi�n se encierra entre barras, como en
.P1
/\f2expresi�n\fP/
.P2
Las expresiones son las mismas que las del programa UNIX
.CW egrep ,\u\s-4\&6,7\s+4\d
e incluyen ?????????? closures ??????????, alternancias, etc.
Encuentran la cadena m�s larga empezando por la izquierda que coincide con la expresi�n, es decir, la primera coincidencia desde el lugar donde empieza la b�squeda y si m�s de una correspondencia empieza en el mismo lugar, se toma la m�s larga.
(Se asume cierta familiaridad con la sintaxis de las expresiones regulares en programas UNIX .\u\s-4\&9\s+4\d)
Por ejemplo,
.P1
/x/
.P2
coincide con el siguiente car�cter
.CW x
en el fichero,
.P1
/xx*/
.P2
coincide con la siguiente aparici�n de una o m�s
.CW x,
y
.P1
/x|Peter/
.P2
coincide con la siguiente
.CW x
o con
.CW Peter .
Para compatibiilidad con otros programas UNIX, el operador "cualquier car�cter", un punto, no coincide con un salto de linea, as� que
.P1
/.*/
.P2
coincide con el texto desde el punto hasta el final de la linea, pero excluye el salto de linea, y no pasa a la siguiente linea.
.PP
Las expresiones regulares son siempre direcciones relativas.
Su orientacion es, por defecto, hacia adelante, as�
.CW /Peter/
es realmente una abreviaci�n de
.CW +/Peter/ .
La b�squeda puede invertirse con el signo menos, por lo que
.P1
.CW -/Peter/
.P2
encontrar� el primer
.CW Peter
antes del punto.
Las expresiones regulares pueden usarse con otras formas de direccionamiento, as� que
.CW 0+/Peter/
encuentra el primer
.CW Peter
en el fichero y
.CW $-/Peter/
encuentra el �ltimo.
La Tabla II resume los modos de direccionamiento de
.CW sam.
.KF
.TS
center;
c s
lfCW l.
Tabla II. Direcciones \f(CWSam\fP
.sp .4
.ft CW
_
.ft
.sp .4
\f1Direcciones simples\fP
.sp .4
_
.sp .2
#\f2n\fP La cadena vac�a despu�s del caracter \f2n\fP
\f2n\fP Linea \f2n\fP.
/\f2regexp\fP/ La siguiente coincidencia de la expresi�n regular
-/\f2regexp\fP/ La anterior coincidencia de la expresi�n regular
$ La cadena vac�a al final del fichero
\&. El punto
\&' La marca de direcci�n puesta por el comando\f(CWk\fP
"\f2regexp\fP" El punto en el fichero cuyo nombre coincida con la expresi�n regular
.sp .4
_
.sp .4
\f1Direcciones compuestas\fP
.sp .4
_
.sp .2
\f2a1\fP+\f2a2\fP La direcci�n \f2a2\fP evaluada empezando a la derecha de \f2a1\fP
\f2a1\fP-\f2a2\fP \f2a2\fP evaluada en la direcci�n inversa empezando a la izquierda de \f2a1\fP
\f2a1\fP,\f2a2\fP Desde la izquierda de \f2a1\fP a la derecha de \f2a2\fP (por defecto \f(CW0,$\fP)
\f2a1\fP;\f2a2\fP Como \f(CW,\fP pero pone el punto despu�s de evaluar \f2a1\fP
.sp .4
_
.sp .4
.T&
c s.
T{
Los operadores
.CW +
y
.CW -
son de mayor precedencia, mientras que
.CW ,
y
.CW ;
son de menor.
En ambas formas,
.CW +
y
.CW -
.I a2
vale por defecto 1 y
.I a1
vale por defecto el punto
Si los dos,
.I a1
y
.I a2
estan presentes,
.CW +
puede ser eludido.
T}
.sp .5
.ft CW
_
.ft
.TE
.sp
.KE
.PP
El lenguaje comentado hasta ahora no parecera nada nuevo para la gente que ha usado editores de texto en UNIX como
.CW ed
�
.CW vi .\u\s-4\&9\s+4\d
M�s a�n, la clase de operaciones de edici�n que estos comandos permiten, con la excepci�n de expresiones regulares y n�meros de linea, son claramente mejor manejados por un interfaz basado en el rat�n.
En su lugar,
.CW sam
el lenguaje de rat�n (explicado m�s arriba) es el medio por el cu�l se realizan normalmente los cambios simples.
Para cambios largos y repetitivos, sin embargo, un lenguaje de texto sobrepasa a un interfaz manual
.PP
Imagina que, en lugar de borrar solo un caso de la cadena
.CW Peter ,
queremos eliminar cada
.CW Peter .
Lo que se necesita es un iterador que ejecute un comando para ocurrencia de algun texto.
El iterador de
.CW sam
se llama
.CW x ,
(de eXtract):
.P1
x/\f2expresi�n\fP/ \f2comando\fP
.P2
encuentra todas las coincidencias del punto en la expresi�n especificada, y para cada una, pone el punto al texto coincidente y ejecuta el comando.
O sea que para borrar todos los
.CW Peters:
.P1
0,$ x/Peter/ d
.P2
(Los espacios en blanco en estos ejemplos solo son para mejorar la legibilidad;
.CW sam
no los requiere ni los interpreta.)
Esto busca en todo el fichero
.CW 0,$ ) (
ocurrencias de la cadena
.CW Peter ,
y ejecuta el comando
.CW d
con el punto puesto a cada ocurrencia.
(Por el contrario, el comando comparable de
.CW ed
borrar�a todas las
.I lines
que contengan
.CW Peter ;
.CW sam
borra solo las palabras
.CW Peter .)
La direcci�n
.CW 0,$
se usa normalmente, y puede abreviarse a tan solo una coma.
Como otro ejemplo,
.P1
, x/Peter/ p
.P2
muestra una lista de
.CW Peters,
una para cada aparici�n en el fichero sin texto en medio (ni siquiera saltos de linea para separarlas).
.PP
Por supuesto, el texto extra�do por
.CW x
??????????
puede ser seleccionado por una expresi�n regular, lo cual complica la decisi�n de qu� grupo de coincidencias se elige \(em las coincidencias pueden solaparse.
may be selected by a regular expression,
which complicates deciding what set of matches is chosen \(em
matches may overlap.
??????????
Esto se resuelve generando las coincidencias empezando desde el principio del punto y usando la regla de el-m�s-largo-m�s-a-la-izquierda, y buscando cada coincidencia empezando desde el final de la anterior.
Las expresiones regulares pueden tambien coincidir con cadenas vac�as, pero una coincidencia nula adyacente a una no nula no es nunca seleccionada, al menos un caracter debe intervenir.
Por ejemplo,
.P1
, c/AAA/
x/B*/ c/-/
, p
.P2
produce como salida
.P1
-A-A-A-
.P2
porque el patr�n
.CW B*
coincide con la cadena vac�a que separa las
.CW A .
.PP
El comando
.CW x
tiene un complementario
.CW y ,
con una sintaxis similar, que ejecuta el comando con el punto puesto al texto
.I entre
las coincidencias de la expresi�n.
Por ejemplo,
.P1
, c/AAA/
y/A/ c/-/
, p
.P2
produce el mismo resultado que el ejemplo anterior.
.PP
Los comandos
.CW x
e
.CW y
son construcciones de bucle, y
.CW sam
tiene un par de comandos condicionales que van con ellas.
Tienen una sintaxis similar:
.P1
g/\f2expresi�n\fP/ \f2commando\fP
.P2
(guarda)
ejecuta el comando exactamente una vez si el punto contiene una coincidencia de la expresi�n.
Esto es distinto de
.CW x ,
que ejecuta el comando para
.I cada
coincidencia:
.CW x
repite;
.CW g
simplemente comprueba, sin cambiar el valor del punto.
As�,
.P1
, x/Peter/ d
.P2
borra todas las ocurrencias de
.CW Peter ,
pero
.P1
, g/Peter/ d
.P2
borra el fichero entero (lo reduce a la cadena vac�a) si
.CW Peter
aparece en alguna parte del texto.
La condici�n complementaria es
.CW v ,
que ejecuta el comando si
.I no
hay coincidencias de la expresi�n.
.PP
Estos comandos de tipo estructura de control pueden componerse para construir operaciones relacionadas. Por ejemplo, para mostrar todas las lineas del texto que contienen la cadena
.CW Peter :
.P1
, x/.*\en/ g/Peter/ p
.P2
La
.CW x
divide el fichero en lineas, la
.CW g
selecciona las lineas que contengan
.CW Peter ,
y la
.CW p
las muestra.
Este comando da una direcci�n para el comando
.CW x
(el fichero entero), pero puesto que
.CW g
no tiene una direcci�n expl�cita, se aplica al valor del punto producido por el comando
.CW x
es decir, a cada linea.
Todos los comandos en
.CW sam
excepto el de escribir el fichero a disco, usan el punto como direcci�n por defecto.
.PP
La composici�n puede continuarse indefinidamente.
.P1
, x/.*\en/ g/Peter/ v/SaltPeter/ p
.P2
muestra las lineas que contienen
.CW Peter
pero
.I no
las que contienen
.CW SaltPeter .
.SH 2
Expresiones Regulares Estructurales
.LP
A diferencia de otros editores UNIX, incluyendo los no interactivos como
.CW sed
y
.CW awk ,\u\s-4\&7\s+4\d
.CW sam
es bueno manipulando ficheros con "registros" multi linea.
Un ejemplo es un list�n telef�nico compuesto de registros separados por lineas en blanco, de la forma
.P1
Herbert Tic
44 Turnip Ave., Endive, NJ
201-5555642
Norbert Twinge
16 Potato St., Cabbagetown, NJ
201-5553145
\&...
.P2
El formato puede codificarse como una expresi�n regular:
.P1
(.+\en)+
.P2
es decir, una secuencia de una o m�s lineas no vac�as.
El comando para imprimir el registro entero del se�or Tic ser�a
.P1
, x/(.+\en)+/ g/^Herbert Tic$/ p
.P2
y el de extraer solamente su n�mero de tel�fono
.P1
, x/(.+\en)+/ g/^Herbert Tic$/ x/^[0-9]*-[0-9]*\en/ p
.P2
Este �ltimo divide el fichero en registros, elige el del se�or Tic, extrae el n�mero de tel�fono, y finalmente lo muestra.
.PP
Un problema m�s complejo es el de renombrar una variable concreta, pongamos
.CW n ,
a
.CW num
en un programa en C.
El primer intento obio
.P1
, x/n/ c/num/
.P2
es defectuoso: cambia no solo la variable
.CW n
sino cualquier letra
.CW n
que aparezca.
Necesitamos extraer todas las variables, y seleccionar aquellas que coincidan con
.CW n
y solamente
.CW n :
.P1
, x/[A-Za-z_][A-Za-z_0-9]*/ g/n/ v/../ c/num/
.P2
El patr�n
.CW [A-Za-z_][A-Za-z_0-9]*
coincide con los identificadores de C.
Luego
.CW g/n/
selecciona los que contengan una
.CW n .
Despu�s
.CW v/../
rechaza los que contienen dos (o m�s) caracteres, y finalmente
.CW c/num/
cambia el resto ( los identificadores
.CW n )
a
.CW num .
Esta versi�n funciona claramente mucho mejor, pero puede todav�a dar problemas. Por ejemplo, en las constantes de car�cter y de cadena en C, la secuencia
.CW \en
es interpretada como un car�cter de salto de linea, y no queremos cambiarlo a
.CW \enum.
El problema puede prevenirse con un comando
.CW y
:
.P1
, y/\e\en/ x/[A-Za-z_][A-Za-z_0-9]*/ g/n/ v/../ c/num/
.P2
(el segundo
.CW \e
es necesario debido a las convenciones l�xicas en las expresiones regulares), o podr�amos incluso rechazar directamente las constantes:
.P1 0
,y/'[^']*'/ y/"[^"]*"/ x/[A-Za-z_][A-Za-z_0-9]*/ g/n/ v/../ c/num/
.P2
Los comandos
.CW y
en esta versi�n excluyen todas las constantes de car�cter y de cadena.
El �nico problema restante es tratar la posible aparici�n de
.CW \e'
� de
.CW \e"
dentro de las secuencias, pero es f�cil ver c�mo se resuelve esta dificultad.
.PP
La base de estos comandos compuestos es el refinamiento sucesivo.
Se intenta una versi�n simple del comando, y si no es suficientemente buena, se afina agreg�ndola una � dos cl�usular.
(Se pueden deshacer los errores; ver m�s abajo. Tambi�n el lenguaje de rat�n hace innecesario reescribir el comando cada vez.)
Las cadenas de comandos resultantes son una especie de reminiscencia de las pipelines del shell.
\u\s-4\&7\s+4\d
A diferencia de las pipelines, sin embargo, que van pas�ndose los
.I datos ,
modificados,
los comandos de
.CW sam
se pasan una
.I vista
de los datos.
El texto de cada paso del comando es el mismo, pero la selecci�n de las piezas se va refinando en cada paso hasta que la pieza correcta esta disponible para el paso final de la linea del comando, que, finalmente, realiza el cambio.
.PP
In otros programas UNIX, las expresiones regulares se usan solo para selecci�n, como en el comando
.CW g
de
.CW sam
nunca para su extracci�n, como en los comandos
.CW x
o
.CW y
command.
Por ejemplo, los patrones en
.CW awk \u\s-4\&7\s+4\d
se usan para seleccionar lineas en las que operar, pero no pueden usarse para describir el formato del texto de entrada, o para manejar texto libre de saltos de linea. El uso de las expresiones regulares para describir la estructura de una pieza de texto, el lugar de su contenido, como en el comando
.CW x
tiene un nombre:
.I
expresiones regulares estructurales.
.R
Cuando se componen, como en el ejemplo anterior, son agradablemente expresivas.
Su uso se explica con m�s detalle en otra parte del documento.\u\s-4\&10\s+4\d
.PP
.SH 2
Ficheros m�ltiples
.LP
.CW Sam
tiene algunos comandos m�s, la mayor�a relacionados con entrada y salida.
.P1
e ficheroendisco
.P2
reemplaza el contenido y el nombre del fichero actual con los del fichero en disco nombrado;
.P1
w ficheroendisco
.P2
escribe los contenidos al fichero en disco nombrado; y
.P1
r ficheroendisco
.P2
reemplaza el punto con los contenidos del fichero en disco nombrado.
Todos estos comandos usan el nombre de fichero actual si no se especifica ninguno.
Finalmente,
.P1
f ficheroendisco
.P2
cambia el nombre asociado al fichero y muestra el resultado:
.P1
\&'-. ficheroendisco
.P2
Esta salida se llama
.I
linea de men�
.R
de ficheros porque contiene las lineas del men� del bot�n 3 del rat�n (descrito en la siguiente secci�n).
Los primeros tres caracteres son una notaci�n concisa del estado del fichero. El ap�strofe significa que el fichero est� modificado.
El signo menos indica el n�mero de ventanas abiertas en el fichero (ver la siguiente secci�n):
.CW -
significa ninguna
.CW +
significa una, y
.CW *
significa m�s de una.
Finalmente, el punto indica que ese es el fichero actual.
Estos caracteres son �tiles para controlar el comando
.CW X
, descrito brevemente.
.PP
.CW Sam
puede ser arrancado con un conjunto de ficheros en disco (como todos los fuentes de un programa) invocandolo con una lista de nombres de ficheros como argumentos, y se pueden agregar o borrar m�s seg�n se necesite.
.P1
B ficheroendisco1 ficheroendisco2 ...
.P2
agrega los ficheros nombrados a la lista de
.CW sam
y
.P1
D ficheroendisco1 ficheroendisco2 ...
.P2
los elimina de la memoria de
.CW sam
(sin ning�n efecto en los ficheros en disco asociados).
Ambos comandos tienen una sintaxis para usar el shell \u\s-4\&7\s+4\d
(el int�rprete de comandos de UNIX) para generar las listas:
.P1
B <echo *.c
.P2
agregara todos los ficheros C, y
.P1
B <grep -l variable *.c
.P2
agregar� todos los ficheros C que hagan referencia a esa variable
(el comando UNIX
.CW grep\ -l
lista todos los ficheros en sus argumentos que contienen coincidencias de la expresi�n regular especificada).
Finalmente,
.CW D
sin argumentos borra el fichero actual.
.PP
Hay dos maneras de cambiar de fichero actual:
.P1
b fichero
.P2
convierte en actual el fichero nombrado.
El comando
.CW B
hace lo mismo, pero tambi�n agrega cualquier nuevo fichero a la lista de
.CW sam.
(En la pr�ctica, por supuesto, el fichero actual es usualmente elegido por medio de acciones de rat�n, no por comandos de texto.)
La otra forma es usar una forma de direcci�n que se refiere a ficheros:
.P1
"\f2expresi�n\fP" \f2direcci�n\fP
.P2
se refiere a la direcci�n evaluada en el fichero cuyo nombre en el men� coincida con la expresi�n (debe haber solo una coincidencia).
Por ejemplo:
.P1
"peter.c" 3
.P2
se refiere a la tercera linea del fichero cuyo nombre coincide con
.CW peter.c .
Esto es muy util en los comandos move (
.CW m )
y copy (
.CW t ):
.P1
0,$ t "peter.c" 0
.P2
hace una copia del fichero actual al principio de
.CW peter.c .
.PP
El comando
.CW X
es una construcci�n de bucle, como
.CW x ,
que se refiere a ficheros en lugar de a cadenas:
.P1
X/\f2expressi�n\fP/ \f2commando\fP
.P2
ejecuta el comando en todos los ficheros cuyo nombre en el menu coincida con la expresi�n. El mejor ejemplo es
.P1
X/'/ w
.P2
que escribe en el disco todos los ficheros modificados.
.CW Y
es el complementario de
.CW X :
ejecuta el comando en todos los ficheros cuyo nombre en el men� no coincida con la expresi�n:
.P1
Y/\e.c/ D
.P2
borra todos los ficheros que no tienen
.CW \&.c
en sus nombres, es decir, deja solamente los ficheros C y borra los demas.
.PP
Las llaves permiten agrupar comandos, as�
.P1
{
\f2comando1\fP
\f2comando2\fP
}
.P2
es sint�cticamente un solo comando que ejecuta otros dos.
Entonces,
.P1
X/\e.c/ ,g/variable/ {
f
, x/.*\en/ g/variable/ p
}
.P2
encuentra todas las ocurrencias de
.CW variable
en ficheros fuente C y muestra el nombre del fichero y las lineas que coinciden.
La sem�ntica concreta de las operaciones compuestas se explica en las secciones de implementaci�n, m�s abajo.
.PP
Finalmente, el comando deshacer
.CW u ,
(undo) deshace el �ltimo comando, no importa cu�ntos ficheros hayan sido afectados.
Operaciones deshacer m�ltiples retroceden en el tiempo, as� que
.P1
u
u
.P2
(que puede abreviarse como
.CW u2 )
deshace los dos �ltimos comandos. Una acci�n deshacer no puede deshacerse, as� como un comando que agrege o borre ficheros.
Todo lo demas puede deshacerse, por ejemplo, los comandos
.CW e
.P1
e fichero
u
.P2
restablece el estado del fichero completamente, incluyendo su nombre, punto y bit de modificaci�n. Por esta raz�n, los comandos potencialmente peligrosos no estan protegidos por confirmaciones. Solo
.CW D ,
que destruye la informaci�n necesaria para restablecerse, es protegido.
No borrar� un fichero modificado, pero un segundo
.CW D
en el mismo fichero s� que lo har�.
El comando
.CW q
que sale de
.CW sam ,
est� protegido de igual manera.
.SH 2
Interfaz de rat�n
.LP
.CW Sam
se ejecuta comunmente conectado a una pantalla grafica con rat�n para la edici�n interactiva. La �nica diferencia en el lenguaje de comandos entre el t�pico
.CW sam
manejado por rat�n y
.CW sam\ -d
es que si una direcci�n se proporciona sin un comando,
.CW sam\ -d
mostrar� el texto referenciado por la direcci�n, pero el
.CW sam
normal lo resltar� en pantalla \(em de hecho, el punto est� siempre resaltado (ver Figura 2).
.WS 1
.KF
.BP fig3.ps 2.04i
.Cs
Figura 2. A
La ventana
.CW sam.
La barra de desplazamiento abajo a la izquierda representa el fichero, con :
window, y el asa representa la fracci�n de texto visible en la ventana.
La barra puede ser manipulada por el rat�n para hojear. El texto actual, que est� resaltado, no necesita entrar en una sola linea. Aqu� consiste en parte de una linea, una linea completa y parte de otra.
.Ce
.KE
.PP
Cada fichero puede tener cero o m�s ventanas abiertas en pantalla.
En cualquier momento, solo una de las ventanas de
.CW sam
es la
.I
ventana actual.
.R
es decir, la ventana a la que se refieren las teclas pulsadas y las acciones de rat�n;
esta puede ser la ventana de
.CW sam
(donde se teclean los comandos)
o una de las ventanas de fichero.
Cuando un fichero tiene m�ltiples ventanas, la imagen del texto se mantiene actualizada siempre en todas.
El fichero actual es el �ltimo fichero afectado por un comando, as� que si la ventana de
.CW sam
es la actual, la ventana actual no es la ventana del fichero actual.
Sin embargo, cada ventana de un fichero tiene su propio valor del punto, por eso, cambiando entre las ventanas de un solo fichero, el valor del punto de ese fichero ir� cambiando.
Es decir, el cambio entre ventanas se comporta en la manera m�s conveniente y mas obvia.
.PP
El rat�n en el Blit tiene tres botones, numerados de izquierda a derecha.
El bot�n 3 tiene una lista de comandos para manipular ventanas, seguido de una lista de "lineas de men�" exactamente las que muestra el comando
.CW f
, una por fichero (no una por ventana).
Estas lineas de men� est�n ordenadas por nombre de fichero.
Si la lista es larga, el men� software del Blit la har� m�s manejable generando un men� desplazable, en lugar de una lista demasiado larga.
Usando el men� para seleccionar un fichero de la lista se convierte en fichero actual, y la ventana actual pasa a ser la �ltima que fu� ventana actual del fichero.
Pero si el fichero ya es el fichero actual, seleccion�ndolo en el men�, se avanza por las ventanas del mismo; este simple truco evita un men� especial para escojer entre las ventanas de un fichero.
Si no hay una ventana abierta con el fichero,
.CW sam
cambia el puntero del rat�n para pedir al usuario que cree una.
.PP
Los comandos del men� del bot�n 3 son directos (ver Figura 3), y son como los comandos para manipular ventanas en
.CW mux ,\u\s-4\&8\s+4\d
el sistema de ventanas del Blit.
.CW New
crea un fichero nuevo, y le da una ventana vac�a, cuyo tama�o se determina por el rect�ngulo trazado por el rat�n.
.CW Zerox
espera a que se seleccione una ventana, y hace una copia de ella; as� es como se crean m�ltiples ventanas para un fichero.
.CW Reshape
cambia el tama�o de la ventana indicada, y
.CW close
la borra. Si esta es la �ltima ventana abierta de un fichero,
.CW close
antes hace un comando
.CW D
para el fichero.
.CW Write
es id�ntico al comando
.CW w
en el fichero; est� en el men� solamente por conveniencia.
Finalmente
.CW ~~sam~~
es la linea de menu que aparece entre los comandos y los nombres de ficheros.
is a menu item that appears between the commands and the file names.
Seleccion�ndola se hace la ventana de
.CW sam
ventana actual, y las siguientes teclas ser�n interpretadas como comandos.
.KF
.BP fig2.ps 2.74i
.Cs
Figura 3. El men� en el bot�n 3.
El rect�ngulo negro a la izquierda es una barra de desplazamiento; el men� est� limitado a la longitud mostrada, para prevenir que se haga inmanejable.
Encima de la linea
.CW ~~sam~~
esta la lista de comandos;
debajo, la lista de ficheros, presentada exactamente como en el comando
.CW f.
.Ce
.KE
.PP
Cuando
.CW sam
solicita que se trace una ventana, en respuesta a
.CW new ,
.CW zerox
�
.CW reshape ,
cambia la forma del cursor del rat�n, de la flecha usual a una caja con una peque�a flecha.
En este estado, el rat�n puede usarse para indicar un rect�ngulo arbitrario pulsando el bot�n 3 en una esquina y solt�ndolo en la esquina opuesta.
M�s convenientemente, basta con hacer un solo click, con lo que
.CW sam
crear� un rect�ngulo que contenga el cursor y que linde con la ventana de
.CW sam.
Colocando la ventana de
.CW sam
en el medio de la pantalla, el usuario puede definir dos regiones (una encima y otra debajo), en las que se pueden apilar ventanas sin ning�n problema (ver Figura 1). Este simple interfaz de usuario hace la creaci�n de ventanas notablemente facil.
.PP
El editor de copy-paste es esencialmente el mismo que el de Smalltalk-80 \u\s-4\&11\s+4\d
El texto del punto est� siempre resaltado en pantalla.
Cuando un caracter se teclea, reemplaza al punto, y lo pone a la cadena vac�a despu�s de ese car�cter. As�, simplemente tecleando se inserta texto.
El bot�n 1 se usa para seleccionar:
pulsando el bot�n, moviendo el rat�n, y solt�ndo el bot�n se selecciona (sepone en el punto) el texto entre los lugares en los que se puls� y solt�.
Pulsando y soltando en el mismo punto, se seleciona una cadena vac�a, esto se llama "hacer clic". Haciendo clic dos veces r�pidamente, es decir, haciendo
.I
doble click
.R
se seleccionan objetos mas grandes; por ejemplo, el doble click en una palabra la selecciona entera, el doble clic justo despu�s de una llave abierta selecciona todo el bloque entre las llaves (manejando correctamente el anidamiento), y de igual manera para los par�ntesis, comillas, etc.
Las reglas del doble clic reflejan cierta inclinaci�n por los programadores.
Si
.CW sam
estuviese m�s pensado para el procesamiento de textos, los doble clic ser�an probablemente para seleccionar estructuras ling�isticas, como frases.
.PP
Si el bot�n 1 se pulsa fuera de la ventana actual, pone como actual la ventana indicada
Esa es la forma mas f�cil de cambiar entre ventanas y ficheros.
.PP
Pulsando el bot�n 2 se muestra un men� de funciones de edici�n (ver Figura 4). La mayor�a de ellas se aplican al texto seleccionado:
.CW cut
borra el texto seleccionadi, y lo recuerda en un buffer oculto llamado
.I
snarf buffer,
.R
.CW paste
reemplaza el texto seleccionado por los contenidos del snarf buffer,
.CW snarf
solo copia el texto seleccionado al snarf buffer,
.CW look
busca hacia adelante en el texto por la siguiente ocurrencia del texto seleccionado, y
.CW <mux>
intercambia el buffer de snarf con el del sistema de ventanas en el que
.CW sam
se esta ejecutando.
Finalmente, la �ltima expresion regular usada aparece como entrada de men� para buscar hacia adelante la siguiente ocurrencia de la misma.
.WS 1
.KF
.BP fig4.ps 1.20i
.Cs
Figura 4. El men� del bot�n 2.
La entrada inferior muestra la expresi�n regular usada �ltimamente, que puede ser texto literal.
.Ce
.KE
.PP
La relaci�n entre el lenguaje de comandos y el lenguaje de rat�n es enteramente debida a la igualdad entre el punto y el texto seleccionado elegido con el bot�n 1 del rat�n.
Por ejemplo, para hacer un conjunto de cambios en una subrutina C, el punto puede ponerse haciendo doble clic en la llave izquierda de la misma.
que pone el punto en el lenguaje de comandos.
Un comando sin direcci�n, cuando es tecleado en la ventana de
.CW sam
se aplicar� entonces solo en el texto que hay entre las llaves.
La idea es seleccionar lo que se necesita y luego decir lo que se desea hacer con ello, sea mediante una selecci�n de menu o mediante un comando tecleado.
Y por su puesto, el valor del punto ser� resaltado en pantalla despu�s de que se complete el comando.
Esta relaci�n entre el interfaz de rat�n y lenguaje de comandos es dificil de explicar, pero confortable, e incluso natural, en la pr�ctica.
.SH
La implementaci�n
.LP
Las siguientes secciones describen c�mo
.CW sam
est� compuesto: primero la parte de host, luego la parte de intercomunicacion entre componentes y luego la parte terminal.
Despu�s de explicar c�mo se ha implementado el lenguaje de comandos, la explicaci�n sigue (aproximadamente) el camino de un car�cter desde el fichero temporal en el disco hasta la pantalla.
La presentaci�n se centra en las estructuras de datos, puesto que as� es como el programa fu� dise�ado y porque los algoritmos son f�ciles de proporcionar, dadas las estructuras de datos correctas.
.SH 2
??????????
An�lisis y ejecuci�n
Parsing and execution
??????????
.LP
El lenguaje de comandos es interpretado analizando cada comando con un parser descendente, e invocando a un ejecutor cuando se ensambla un comando completo.
La mayor�a de editores emplean un scaner l�xico de un solo car�cter a la vez.
El uso de un parser facilita detectar de forma inequ�voca cu�ndo un comando esta completa, lo cual tiene dos ventajas.
Primero, las convenciones de escape, como barras invertidas para acotar comandos de varias lineas son innecesarias; si el comando no ha terminado, el parser continua leyendo. Por ejemplo, un append de varias lineas manejado por un comando
.CW x
es directo:
.P1
x/.*\en/ g/Peter/ a
una linea acerca de Peter
otra linea acerca de Peter
\&.
.P2
Otros editores UNIX requerir�an una barra invertida despu�s de cada linea excepto la �ltima.
.PP
La otra ventaja es espec�fica de la estructura formada por dos procesos de
.CW sam .
El proceso del host debe decidir cu�ndo un comando esta completo para que el int�rprete pueda ejecutarse. Este problema se resuelve f�cilmente teniendo un analizador l�xico que lee un simple stream de eventos desde elterminal, ejecutando directamente todos los comandos de teclado y de rat�n, pero pero pasando al analizador los caracteres tecleados en la ventana de
.CW sam.
Este esquema es ligeramente complicado por la disponibilidad de la edici�n de copy-paste en la ventana de
.CW sam
pero la dificultad se resuelve aplicando las reglas usadas en
.CW mux :
cuando un salto de linea es enviado a la ventana de
.CW sam
todo el texto entre ese y el tecleado anteriormente se pone a disposici�n del parser.
Esto permite la edici�n arbitraria de un comando antes de teclear el salto de linea y solicitar su ejecuci�n.
.PP
El parser es manejado por una tabla debido a que la sintaxis de las direcciones y los comandos es suficientemente regular como para ser codificada de forma compacta. Hay pocos casos especiales, como el texto de reemplazo en una sustituci�n, as� que la sintaxis de casi todos los comandos puede codificarse con unas pocas banderas.
Esto incluye si el comando permite direcciones (por ejemplo,
.CW e
no las permite), si admite expresiones regulares (como en
.CW x
y
.CW s ),
si requiere texto de reemplazo, como en
.CW c
�
.CW i ),
si puede ocupar varias lineas, etc.
La sintaxis interna de las expresiones regulares es manejada pour un parser diferente, una expresi�n regular es una hoja del arbol del comando a analizar.
Las expresiones regulares se explican a fondo en la secci�n siguiente.
.PP
La tabla de an�lisis tiene tambien informaci�n acerca de los valores por defecto, as� que el int�rprete se llama siempre con un �rbol completo. Por ejemplo, el parser rellena el
.CW 0
y el
.CW $
impl�citos en las direcciones abreviadas
.CW ,
(coma),
inserta un
.CW +
??????????
a la izquierda de una expresi�n regular sin adornar en una direcci�n,
to the left of an unadorned regular expression in an address,
??????????
y proporciona la direcci�n por defecto usual
.CW .
(el punto) para comandos que esperaban una direcci�n pero no reciben ninguna.
.PP
Una vez que un comando completo se analiza, la evaluaci�n es f�cil.
La direcci�n es evaluada de izquierda a derecha, empezando por el valor del punto, con un evaluador de expresiones ordinario.
Las direcciones, como muchas de las estructuras de datos en
.CW sam ,
se mantienen en una estructura C y se pasan por valor:
.P1
typedef long Posn; /* Posici�n en un fichero*/
typedef struct Range{
Posn p1, p2;
}Range;
typedef struct Address{
Range r;
File *f;
}Address;
.P2
Una direcci�n se codifica como una subcadena (las posiciones de los caracteres
.CW p1
y
.CW p2 )
en un fichero
.CW f .
(El tipo de datos
.CW File
se describe en detalle mas abajo.)
.PP
El int�rprete de direcciones es una funci�n que devuelve una
.CW Address
que atraviesa el �rbol de an�lisis describiendo una direcci�n (el �rbol de an�lisis para la direccion es del tipo
.CW Addrtree ):
.P1
Address
address(ap, a, sign)
Addrtree *ap;
Address a;
int sign;
{
Address a2;
do
switch(ap->type){
case '.':
a=a.f->dot;
break;
case '$':
a.r.p1=a.r.p2=a.f->nbytes;
break;
case '"':
a=matchfile(a, ap->aregexp)->dot;
break;
case ',':
a2=address(ap->right, a, 0);
a=address(ap->left, a, 0);
if(a.f!=a2.f || a2.r.p2<a.r.p1)
error(Eorder);
a.r.p2=a2.r.p2;
return a;
/* and so on */
}
while((ap=ap->right)!=0);
return a;
}
.P2
.PP
Los errores se manejan mediante un
.CW goto
local (un
.CW setjmp/longjmp
en terminolog�a C)
oculto en una rutina llamada
.CW error
que inmediatamente aborta la ejecuci�n, retrae cualquier cambio parcial (ver la secci�n abajo sobre deshacer), y retorna al nivel superior del parser.
El argumento de
.CW error
es un tipo enumeraci�n que se traduce a un terso pero posiblemente �til mensaje como `?addresses out of order.'
Muchos mensajes comunes se mantienen cortos; por ejemplo, elmensaje para fallos en las expresiones regulares de b�squeda es `?search.'
.PP
Direcciones de car�cter como
.CW #3
son triviales de implementar, dado que la estructura
.CW File
es accesible por n�mero de car�cter.
Sin embargo,
.CW sam
no mantiene informaci�n sobre la posici�n de los saltos de linea \(em ser�a muy costoso de mantener din�micamente \(em as� que las direcciones de linea se computan leyendo el fichero y contando los saltos de linea.
Excepto en ficheros muy largos, esto ha demostrado ser aceptable: el acceso al fichero es suficientemente r�pido como para que resulte pr�ctico, y las lineas no son algo central enla estructura del lenguaje de comandos.
.PP
El int�rprete de comandos, llamado
.CW cmdexec ,
es tambi�n directo. La tabla del analizador incluye una funci�n que se llama para interpretar un comando particular. La funci�n recibe como argumentos la direccion calculada para el comando y el �rbol del comando ( del tipo
.CW Cmdtree ),
que puede contener informaci�n como el sub-�rbol para comandos compuestos.
Aqu�, por ejemplo, est� la funci�n de los comandos
.CW g
y
.CW v
.P1
int
g_cmd(a, cp)
Address a;
Cmdtree *cp;
{
compile(cp->regexp);
if(execute(a.f, a.r.p1, a.r.p2)!=(cp->cmdchar=='v')){
a.f->dot=a;
return cmdexec(a, cp->subcmd);
}
return TRUE; /* hace que contin�e la ejecuci�n*/
}
.P2
.CW Compile "" (
y
.CW execute
son partes del c�digo de expresi�n regular, descrito en la siguiente secci�n.)
Dado que el parser y la estructura de datos
.CW File
hacen casi todo el trabajo, muchos comandos son muy breves.
.SH 2
Expresiones Regulares
.LP
El c�digo de expresi�n regular en
.CW sam
es una implementaci�n, interpretada en lugar de compilada sobre la marcha, del algoritmo de aut�matas finitos no deterministas de Thompson \u\s-4\&12\s+4\d
La sintaxis y sem�ntica de las expresiones es como en el programa UNIX
.CW egrep ,
incluyendo la alternancia, las closures, las clases de caracteres, etc.
Los �nicos cambios en la notaci�n son dos adiciones:
.CW \en
que se traduce por y coincide con un salto de linea y
.CW @
que coincide con cualquier car�cter. En
.CW egrep ,
el car�cter
.CW \&.
coincide con cualquier car�cter excepto el salto de linea, y en
.CW sam
la misma regla parec�o la m�s segura, para evitar idiomas como
.CW \&.*
para abarcar los saltos de linea.
Las expresiones
.CW Egrep
son realmente demasiado complicadas para un editor interactivo \(em ciertamente tendr�an sentido si todos los caracteres especiales fuesen secuencias de dos caracteres, de modo que la mayor�a de los caracteres de puntuaci�n no tendr�a un significado peculiar \(em pero para un lenguaje de comandos interesante, las expresiones regulares completas son necesarias, y
.CW egrep
define la sintaxis completa para las expresiones regulares en programas UNIX.
Tambi�n nos pareci� superfluo definir una nueva sintaxis, dado que varios programas UNIX
.CW ed , (
.CW egrep
y
.CW vi )
definen ya demasiadas.
.PP
Las expresiones son compiladas por una rutina,
.CW compile ,
que genera la descripci�n de una maquina de estados finita no determinista.
Una segunda rutina,
.CW execute ,
interpreta la m�quina para general la coincidencia m�s larga por la izquierda en una subcadena del fichero.
El algoritmo se describe en otra parte.\u\s-4\&12,13\s+4\d
.CW Execute
informa de si se ha encontrado alguna coincidencia, y pone una variable global de tipo
.CW Range ,
a la subcadena encontrada.
.PP
Se requiere un truco para evaluar las expresiones al rev�s, como cuando se busca una expresi�n hacia atr�s.
Por ejemplo,
.P1
-/P.*r/
.P2
busca hacia atr�s a trav�s del fichero una coincidencia de la expresi�n.
La expresi�n, sin embargo, esta definida para una b�squeda hacia adelante. La soluci�n est� en construir una m�quina id�ntica a la maquina para las b�squedas hacia adelante excepto que se invierten todos los operadores de concatenaci�n ( los otros operadores son sim�tricos en la inversi�n), para intercambiar el significado de los operadores.
.CW ^
y
.CW $ ,
y luego, para leer el fichero hacia atr�s, buscando normalmente la coincidencia mas larga.
.PP
.CW Execute
genera solo una coincidencia cada vez que se llamado.
Para interpretar las construcciones de bucle como el comando
.CW x,
.CW sam
debe entonces sincronizarse entre las llamadas a
.CW execute
para evitar problemas con las coincidencias nulas.
Por ejemplo, incluso teniendo en cuenta la regla de la m�s larga por la izquierda, la expresi�n
.CW a*
coincide tres veces en la cadena
.CW ab
(el car�cter
.CW a ,
la cadena vac�a entre
.CW a
y
.CW b ,
y la cadena vac�a final )
Despu�s de devolver una coincidencia para
.CW a ,
.CW sam
no debe considerar coincidente la cadena vac�a antes de
.CW b .
El algoritmo arranca
.CW execute
al final de su coincidencia anterior, y si la coincidencia que devuelve es vac�a y linda con la coincidencia anterior, rechaza la coincidencia y avanza la posici�n inicial un car�cter.
.SH 2
Asignaci�n de memoria
.LP
El lenguaje C no tiene primitivas de asignaci�n de memoria, aunque una rutina estandar
.CW malloc ,
proporciona servicios adecuados para programas simples.
Para usos espec�ficos, sin embargo, puede ser mejor escribir un asignador a medida. El asignador (o mejor, el par de asignadores) descritos aqu�, trabajan tanto en la parte de host como en la del terminal de
.CW sam .
Est�n dise�ados para la manipulaci�n eficiente de cadenes, que son asignadas y liberadas frecuentemente y que var�an en longitud de esencialmente 0 hasta 32 Kbytes (las cadenas muy largas se escriben a disco).
M�s importante, las cadenas pueden ser largas y cambiar de tama�o a menudo, de modo que para minimizar el uso de memoria es de gran ayuda reclamar y fusionar las porciones no usadas de las cadenas que son truncadas.
.PP
Los objetos a los que se asigna memoria en
.CW sam
son de dos clases:
la primera
.CW structs ,
de C, que son peque�as y a menudo accedidas por variables puntero; la segunda es arrays de caracteres o enteros de tama�o variable cuyo puntero base es siempre usado para acceder a ellos.
El asignador de memoria de
.CW sam
tiene entonces dos partes:
la primera, un asignador tradicional tipo firts-fit que proporciona espacio fijo para las
.CW structs ;
y el segundo, un asignador compactador de basura que reduce el sobre-consumo de memori para objetos de tama�o variable, con un peque�o coste de gesti�n.
Los dos tipos de objetos son asignados desde zonas de memoria contiguas, siendo el asignador compactador de basura el que controla la zona m�s alta de ambas.
Separar en dos zonas la memoria simplifica la compactaci�n y previene la fragmentaci�n debida a objetos inamovibles.
Las reglas de acceso para los objetos compactables (explicados en el siguiente p�rrafo) permite que sean reasignados, as� que cuando el asignador first-fit necesita espacio, mueve la zona de memora del compactador a una zona mas alta. El almacenamiento es entonces creado solo en direcciones sucesivamente mas altas, bien cuando se necesita m�s espacio compactable o bien cuando la zona del first-fit empuja a la otra zona.
.PP
Los objetos que pueden ser compactados declaran al asignador una celda que se garantiza que ser� el �nico repositorio para la direcci�n del objeto cuando ocurra una compactaci�n. El compactador puede entonces actualizar esta direcci�n cuando un objeto es movido. Por ejemplo, la implementaci�n del tipo
.CW List
(realmente un array de tama�o variable)
is:
.P1
typedef struct List{
int nused;
long *ptr;
}List;
.P2
La celda
.CW ptr
debe usarse siempre directamente, y nunca copiada. Cuand una
.CW List
va a ser creada, la estructura
.CW List
es asignada en la zona del first-fit y su
.CW ptr
es asignado a la zona del compactador.
Un tipo de dato similar para cadenas, llamado
.CW String ,
almacena arrays de caracteres de tama�o variable hasta 32767 elementos.
.PP
Una cuesti�n relacionada de estilo de programaci�n:
.CW sam
pasa las estructuras normalmente por valor, lo que simplifica el c�digo.
Tradicionalmente, los programas C han pasado estructuras por referencia, pero la asignaci�n impl�cita en la pila es m�s facil de usar.
frequently passes structures by value, which
simplifies the code.
El paso de estructuras es una caracter�stica relativamente nueva de C (no est� en el manual estandar de referencia de C\u\s-4\&14\s+4\d), y est� d�bilmente soportado por la mayor�a de los compiladores comerciales.
Sin embargo, es conveniente y expresivo, y simplifica el manejo de memoria evitando el asignador de memoria y eliminando alias de punteros.
.SH 2
Estructuras de datos para manipular ficheros
.LP
La experiencia con
.CW jim
nos mostr� que los requerimientos de la estructura de datos del fichero eran pocas, pero estrictas.
Primero, los ficheros necesitan ser leidos y escritos r�pidamente; agregar un fichero nuevo debe poder hacerse sin coste alguno. Segundo, la implementaci�n no debe colocar l�mites en la cantidad y tama�o de los ficheros. (Debe ser pr�ctico editar muchos ficheros, y ficheros de megabytes deben manejarse con facilidad.)
Esto implica que los ficheros sean almacenados en disco, no en la memoria. (Los aficionados a la memoria virtual pueden argumentar lo contrario, pero la implementaci�n de memoria virtual en nuestro sistema no es algo que dependa del buen rendimiento.)
Tercero, los cambios en los ficheros necesitan hacerse con solo dos primitivas.
Inserci�n y borrado (Los aficionados a la memoria virtual pueden argumentar lo contrario, pero la implementaci�n de memoria virtual en nuestro sistema no es algo que dependa del buen rendimiento.)
Tercero, los cambios en los ficheros necesitan hacerse con solo dos primitivas:
inserci�n y borrado.
Cada una es la inversa de la otra, lo que simplifica la implementaci�n de la operacion deshacer.
Finalmente, debe ser facil y eficiente acceder al fichero, bien hacia adelante, bien hacia atr�s, un byte a la vez.
.PP
El tipo de datos
.CW File
esta formado por tres estructuras m�s simples que guardan arrays de caracteres. Cada uno de esos tipos tiene un operador de inserci�n y de borrado, y los operadores de inserci�n y borrado del tipo
.CW File
est�n, a su vez, formados por estos.
.PP
El tipo m�s simple es
.CW String,
que se usa para almacenar cadenas en la memoria.
El c�digo que maneja
.CW Strings
garantiza que nunca ser�n mayores a un tama�o moderado, y en la pr�ctica nunca mayores a 8 Kbytes.
Las
.CW Strings
tienen dos prop�sitos: guardar cadenas cortas como nombres de ficheros con poco gasto, y debido a que son deliberadamente peque�as, su modificaci�n es muy eficiente.
Se usan pu�s como estructura de datos para los cach�s en memoria.
.PP
La copia en disco del fichero se maneja con una estructura llamada
.CW Disc ,
que corresponde a un fichero temporal. Un
.CW Disc
no tiene datos en la memoria principal, aparte de informaci�n de gesti�n:
los datos almacenados est�n por completo en el disco.
Para reducir el n�mero de ficheros abiertos necesarios,
.CW sam
abre una docena de ficheros temporales UNIX y multiplexa los
.CW Discs
sobre ellos.
Esto permite que muchos ficheros sean editados; el c�digo fuente completo de
.CW sam
(48 ficheros) puede ser editado confortablemente con una sola instancia de
.CW sam .
Asignar un fichero temporal por
.CW Disc
forzar�a el l�mite del sistema operativo de n�mero de ficheros abiertos.
Tambien, repartiendo el trafico entre varios ficheros temporales mantiene los ficheros peque�os, y los ficheros peque�os se manejan m�s eficientemente por los subsistemas de E/S de UNIX.
.PP
UN
.CW Disc
es un array de bloques de tama�o fijo, cada uno de los cuales contiene entre 1 y 4096 caracteres de datos activos. (El tama�o de bloque de nuestro sistema de ficheros UNIX es de 4096 bytes.)
Las direcciones de los bloques dentro del fichero temporal y la longitud de cada bloque se guarda en una
.CW List .
Cuando se realizan cambios, la parte viva de los bloques puede cambiar de tama�o. Los bloques son creados y consolidados para mantener los tama�os entre 2048 y 4096 bytes.
Una parte muy cambiante de
.CW Disc
tiene sin embargo t�picamente sobre un kilobyte de espacio sobrante que puede ser insertado o borrado sin cambiar m�s de un bloque o afectar al orden de los bloques.
Cuando una inserci�n va a rebosar el bloque, �ste se divide, se asigna uno nuevo para que reciba el sobrante, y la lista de bloques residente en memoria se actualiza para reflejar la inserci�n de un nuevo bloque.
.PP
Obviamente, ir al disco para cada modificaci�n del fichero es prohibitivamente caro.
El tipo de datos
.CW Buffer
consiste en un
.CW Disc
para guardar los datos y una
.CW String
para actuar como cach�.
Este es el primero de una serie de caches a trav�s de las estructuras de datos en
.CW sam.
Los cach�s no solo mejoran el rendimiento, proporcionan una forma de organizar el flujo de datos, particularmente en la comunicaci�n entre el host y la terminal.
Esta idea se desarrolla mas abajo, en la secci�n de comunicaciones.
.PP
Para reducir el tr�fico de disco, los cambios a un
.CW Buffer
se realizan por medio de una cadena de tama�o variable, en memoria, que actua como cach�.
Cuando se inserta o se borra en un
.CW Buffer ,
si el cambio cabe en el cache, se hace ah�.
Si el cach� se hace mas grande que un bloque debido a una inserci�n, una parte de �l es escrita al
.CW Disc
y borrada del cach�.
Si el cach� no interseca el cach�, los datos del cach� son borrados.
El cach� es cargado solamente en una nueva posici�n si el cambio es menor a un bloque;
si no, es enviado directamente al
.CW Disc .
Esto es debido a que los cambios grandes son t�picamente secuenciales, por lo que el siguiente cambio raramente sobre escribir� al actual.
.PP
Un
.CW File
comprende un
.CW String
para guardar el nombre del fichero y algunos datos auxiliares, como el punto y el bit de modificado.
Los componentes m�s importantes, sin embargo, son un par de
.CW Buffers ,
uno llamado transcrip y otro contents.
Su uso es descrito en la siguiente secci�n.
.PP
La estructura general se muestra en la Figura 5.
Aunque puede parecer que los datos se tocan muchas veces de esta forma desde el
.CW Disc ,
se leen (por una llamada del sistema UNIX) directamente en el cach� del
.CW Buffer ;
asociado, no se hace ninguna copia extra.
no extra copy is done.
De forma similar, cuando se borran los datos de un cach�, el texto se escribe directamente desde el cach� al disco.
La mayor�a de operaciones act�an directamente en el texto del cach�.
Un principio aplicado en todo
.CW sam
es que cuanto menos veces se copien los datos, m�s r�pido ir� el programa (ver tambi�n el documento de Waite \u\s-4\&15\s+4\d).
.KF
.PS
copy "fig5.pic"
.PE
.Cs
Figura 5. Estructuras de datos File.
Los ficheros temporales se almacenan en un repositorio estandar para estos ficheros en el sistema host.
.Ce
.KE
.PP
Los contenidos de un
.CW File
se acceden por una rutina que copia a un buffer una subcadena de un fichero comenzando desde un desplazamiento indicado.
Para leer un byte cada vez, se carga un array por
.CW File
comenzando en una posici�n especificada y los bytes pueden entonces leerse desde el array.
La implementaci�n se hace con una macro similar a la macro de E/S estandar de C
.CW getc
\u\s-4\&14\s+4\d
Puesto que la lectura puede hacerse en cualquier direcci�n de memoria, un cambio menor en la macro permite que el fichero sea le�do hacia atr�s.
Este array es de solo lectura; no hay
.CW putc .
.SH 2
Haciendo y deshaciendo
.LP
.CW Sam
como m�todo inusual para manejar cambios en ficheros.
El lenguaje de comandos facilita la especificaci�n de m�ltiples cambios de longitud variable a un fichero de millones de bytes, y estos cambios deben hacerse de forma eficiente si el editor ha de ser pr�ctico.
Las t�cnicas usuales para insertar y borrar cadenas son inadecuadas en estas condiciones.
Las estructuras
.CW Buffer
y
.CW Disc
estan dise�adas para un acceso aleatorio eficiente a cadenas grandes, pero ha de tenerse cuidado para evitar un comportamiento super-lineal cuando se hacen varios cambios simultaneamente.
.PP
.CW Sam
usa un algoritmo de dos pasos para hacer cambios, y trata cada fichero como una base de datos contra la cual se registran transacciones. Los cambios no se hacen directamente en el contenido. En su lugar, cuando se inserta un comando, una 'marca' que contiene un n�mero en secuencia se coloca en el transcript
.CW Buffer ,
y cada cambio hecho al fichero, bien sea una inserci�n, un borrado, o un cambio al nombre del fichero, se agrega al final del transcript.
Cuando un comando se completa, el transcript retrocede hasta la marca y se aplica al contenido.
.PP
Una raz�n para separar evaluaci�n de aplicaci�n de esta manera es que resulte m�s simple llevar cuenta de las direcciones de los cambios realizados en medio de una secuencia larga.
El algoritmo en dos pasos permite que todos los cambios se apliquen al los datos
.I originales
:ning�n cambio puede afectar a otro cambio hecho en el mismo comando.
Esto es particularmente importante cuando se evalua un comando
.CW x
porque previene que las coincidencias de las expresiones regulares se falseen debido a cambios hechos anteriormente en la ejecuci�n.
Tambien, este algoritmo es m�s limpio que el que la manera en que otros editores UNIX permiten que los cambios afecten uno a otro; por ejemplo, los idiomas de
.CW ed
para hacer cosas como borrar cada linea dependen cr�ticamente de la implementaci�n.
En lugar de eso, el sencillo modelo de
.CW sam,
en el que todos los cambios de un comando ocurren, a los efectos, simultaneamente, es f�cil de explicar y de comprender.
.PP
Los registros en el transcript son de la forma "borra la subcadena desde la posici�n 123 a 456" y "inserta 10 caracteres 'hola mundo" en la posici�n 789". (Es un error si los cambios no son en posiciones mon�tonamente mayores del fichero)
Mientras ocurre la actualizaci�n, estos n�meros deben ser desplazados por los cambios anteriores, pero esto es directo y local a la rutina de actualizaci�n; m�s a�n, todos los n�mero habr�n sido computados antes de que el primero sea examinado.
.PP
Tratando el fichero como un sistema de transacciones tiene otra ventaja:
la operaci�n deshacer (undo) es trivial.
Todo lo que se necesita es invertir el transcript despues de que ha sido implementado, convirtiendo las inserciones en borrados y viceversa, y salv�ndolos en un
.CW Buffer
de almacenamiento.
El transcript "hacer" puede ser borrado del
.CW Buffer
de transcripts, y reemplazado por el transcript "deshacer".
Si se solicita un "undo", el transcript se rebobina y se ejecuta el transcript undo.
Debido a que el
.CW Buffer
de transcrips no se trunca despu�s de cada comando, acumula los sucesivos cambios.
Una secuencia de comandos undo puede entonces volver atr�s el estado del fichero de modo arbitrario, lo que es m�s �til que la m�s comunmente implementada forma de undo auto-inverso.
.CW Sam "" (
no proporciona un m�todo de deshacer un undo, pero si se quisiera, podr�a ser facil hacerlo reinterpretando el transcript "hacer")
Cada marca en el transcript contiene un n�mero secuencial y el desplazamiento dentro del transcript desde la marca anterior, para ayudar a revertir el transcript.
Las marcas tambien contienen el valor del punto y el bit de modificaci�n as� que pueden ser restaurados f�cilmente.
Deshacer en m�ltiples ficheros es facil; meramente exige deshacer en todos los ficheros cuyos cambios tengan el mismo n�mero de secuencia que el fichero actual.
.PP
Otro beneficio de tener un transcript es que los errores encontrados en el medio de un comando complicado no necesitan dejar el fichero en un estado intermedio. Revirtiendo el transcript hasta la marca del comienzo del comando, los cambios parciales ser�n trivialmente deshechos.
.PP
Cuando el algoritmo de actualizaci�n fu� implementado al principio, era inaceptablemente lento, as� que se agreg� un cach�, para compactar los cambios cercanos, reemplazando m�ltiples cambios peque�os por un solo cambio m�s grande.
Esto redujo el n�mero de inserciones el
.CW Buffer ,
de transacci�n, y caus� una impactante mejora en el rendimiento, pero hizo imposible manejar cambios en un orden no monot�nico en el fichero; el m�todo de caching solo funciona si los cambios no se solapan.
Antes de que el cach� fuese a�adido, la transacci�n podr�a haber sido ordenada previamente si los cambios estaban desordenados, pero esto nunca lleg� a hacerse.
En el estado actual, sin embargo, el rendimiento es aceptable con una restricci�n menor en los cambios globales, que es, a veces, aunque raramente, una molestia.
.PP
The update algorithm obviously paws the data more than simpler
algorithms, but it is not prohibitively expensive;
the caches help.
(The principle of avoiding copying the data is still honored here,
although not as piously:
the data is moved from contents' cache to
the transcript's all at once and through only one internal buffer.)
Performance figures confirm the efficiency.
To read from a dead start a hundred kilobyte file on a VAX-11/750
takes 1.4 seconds of user time, 2.5 seconds of system time,
and 5 seconds of real time.
Reading the same file in
.CW ed
takes 6.0 seconds of user time, 1.7 seconds of system time,
and 8 seconds of real time.
.CW Sam
uses about half the CPU time.
A more interesting example is the one stated above:
inserting a character between every pair of characters in the file.
The
.CW sam
command is
.P1
,y/@/ a/x/
.P2
and takes 3 CPU seconds per kilobyte of input file, of which
about a third is spent in the regular expression code.
This translates to about 500 changes per second.
.CW Ed
takes 1.5 seconds per kilobyte to make a similar change (ignoring newlines),
but cannot undo it.
The same example in
.CW ex ,\u\s-4\&9\s+4\d
a variant of
.CW ed
done at the University of California at Berkeley,
which allows one level of undoing, again takes 3 seconds.
In summary,
.CW sam 's
performance is comparable to that of other UNIX editors, although it solves
a harder problem.
.SH 2
Communications
.LP
The discussion so far has described the implementation of the host part of
.CW sam ;
the next few sections explain how a machine with mouse and bitmap display
can be engaged to improve interaction.
.CW Sam
is not the first editor to be written as two processes,\u\s-4\&16\s+4\d
but its implementation
has some unusual aspects.
.PP
There are several ways
.CW sam 's
host and terminal parts may be connected.
The first and simplest is to forgo the terminal part and use the host
part's command language to edit text on an ordinary terminal.
This mode is invoked by starting
.CW sam
with the
.CW -d
option.
With no options,
.CW sam
runs separate host and terminal programs,
communicating with a message protocol over the physical
connection that joins them.
Typically, the connection is an RS-232 link between a Blit
(the prototypical display for
.CW sam )
and a host running
the Ninth Edition of the UNIX operating system.\u\s-4\&8\s+4\d
(This is the version of the system used in the Computing Sciences Research
Center at AT&T Bell Laboratories [now Lucent Technologies, Bell Labs], where I work. Its relevant
aspects are discussed in the Blit paper.\u\s-4\&1\s+4\d)
The implementation of
.CW sam
for the SUN computer runs both processes on the same machine and
connects them by a pipe.
.PP
The low bandwidth of an RS-232 link
necessitated the split between
the two programs.
The division is a mixed blessing:
a program in two parts is much harder to write and to debug
than a self-contained one,
but the split makes several unusual configurations possible.
The terminal may be physically separated from the host, allowing the conveniences
of a mouse and bitmap display to be taken home while leaving the files at work.
It is also possible to run the host part on a remote machine:
.P1
sam -r host
.P2
connects to the terminal in the usual way, and then makes a call
across the network to establish the host part of
.CW sam
on the named machine.
Finally, it cross-connects the I/O to join the two parts.
This allows
.CW sam
to be run on machines that do not support bitmap displays;
for example,
.CW sam
is the editor of choice on our Cray X-MP/24.
.CW Sam
.CW -r
involves
.I three
machines: the remote host, the terminal, and the local host.
The local host's job is simple but vital: it passes the data
between the remote host and terminal.
.PP
The host and terminal exchange messages asynchronously
(rather than, say, as remote procedure calls) but there is no
error detection or correction
because, whatever the configuration, the connection is reliable.
Because the terminal handles mundane interaction tasks such as
popping up menus and interpreting the responses, the messages are about
data, not actions.
For example, the host knows nothing about what is displayed on the screen,
and when the user types a character, the message sent to the host says
``insert a one-byte string at location 123 in file 7,'' not ``a character
was typed at the current position in the current file.''
In other words, the messages look very much like the transaction records
in the transcripts.
.PP
Either the host or terminal part of
.CW sam
may initiate a change to a file.
The command language operates on the host, while typing and some
mouse operations are executed directly in the terminal to optimize response.
Changes initiated by the host program must be transmitted to the terminal,
and
vice versa.
(A token is exchanged to determine which end is in control,
which means that characters typed while a time-consuming command runs
must be buffered and do not appear until the command is complete.)
To maintain consistent information,
the host and terminal track changes through a per-file
data structure that records what portions of the file
the terminal has received.
The data structure, called a
.CW Rasp
(a weak pun: it's a file with holes)
is held and updated by both the host and terminal.
A
.CW Rasp
is a list of
.CW Strings
holding those parts of the file known to the terminal,
separated by counts of the number of bytes in the interstices.
Of course, the host doesn't keep a separate copy of the data (it only needs
the lengths of the various pieces),
but the structure is the same on both ends.
.PP
The
.CW Rasp
in the terminal doubles as a cache.
Since the terminal keeps the text for portions of the file it has displayed,
it need not request data from the host when revisiting old parts of the file
or redrawing obscured windows, which speeds things up considerably
over low-speed links.
.PP
It's trivial for the terminal to maintain its
.CW Rasp ,
because all changes made on the terminal apply to parts of the file
already loaded there.
Changes made by the host are compared against the
.CW Rasp
during the update sequence after each command.
Small changes to pieces of the file loaded in the terminal
are sent in their entirety.
Larger changes, and changes that fall entirely in the holes,
are transmitted as messages without literal data:
only the lengths of the deleted and inserted strings are transmitted.
When a command is completed, the terminal examines its visible
windows to see if any holes in their
.CW Rasps
intersect the visible portion of the file.
It then requests the missing data from the host,
along with up to 512 bytes of surrounding data, to minimize
the number of messages when visiting a new portion of the file.
This technique provides a kind of two-level lazy evaluation for the terminal.
The first level sends a minimum of information about
parts of the file not being edited interactively;
the second level waits until a change is displayed before
transmitting the new data.
Of course,
performance is also helped by having the terminal respond immediately to typing
and simple mouse requests.
Except for small changes to active pieces of the file, which are
transmitted to the terminal without negotiation,
the terminal is wholly responsible for deciding what is displayed;
the host uses the
.CW Rasp
only to tell the terminal what might be relevant.
.PP
When a change is initiated by the host,
the messages to the terminal describing the change
are generated by the routine that applies the transcript of the changes
to the contents of the
.CW File .
Since changes are undone by the same update routine,
undoing requires
no extra code in the communications;
the usual messages describing changes to the file are sufficient
to back up the screen image.
.PP
The
.CW Rasp
is a particularly good example of the way caches are used in
.CW sam .
First, it facilitates access to the active portion of the text by placing
the busy text in main memory.
In so doing, it provides efficient access
to a large data structure that does not fit in memory.
Since the form of data is to be imposed by the user, not by the program,
and because characters will frequently be scanned sequentially,
files are stored as flat objects.
Caches help keep performance good and linear when working with such
data.
.PP
Second, the
.CW Rasp
and several of the other caches have some
.I read-ahead;
that is, the cache is loaded with more information than is needed for
the job immediately at hand.
When manipulating linear structures, the accesses are usually sequential,
and read-ahead can significantly reduce the average time to access the
next element of the object.
Sequential access is a common mode for people as well as programs;
consider scrolling through a document while looking for something.
.PP
Finally, like any good data structure,
the cache guides the algorithm, or at least the implementation.
The
.CW Rasp
was actually invented to control the communications between the host and
terminal parts, but I realized very early that it was also a form of
cache. Other caches were more explicitly intended to serve a double
purpose: for example, the caches in
.CW Files
that coalesce updates not only reduce traffic to the
transcript and contents
.CW Buffers ,
they also clump screen updates so that complicated changes to the
screen are achieved in
just a few messages to the terminal.
This saved me considerable work: I did not need to write special
code to optimize the message traffic to the
terminal.
Caches pay off in surprising ways.
Also, they tend to be independent, so their performance improvements
are multiplicative.
.SH 2
Data structures in the terminal
.LP
The terminal's job is to display and to maintain a consistent image of
pieces of the files being edited.
Because the text is always in memory, the data structures are
considerably simpler than those in the host part.
.PP
.CW Sam
typically has far more windows than does
.CW mux ,
the window system within which its Blit implementation runs.
.CW Mux
has a fairly small number of asynchronously updated windows;
.CW sam
needs a large number of synchronously updated windows that are
usually static and often fully obscured.
The different tradeoffs guided
.CW sam
away from the memory-intensive implementation of windows, called
.CW Layers ,\u\s-4\&17\s+4\d
used in
.CW mux.
Rather than depending on a complete bitmap image of the display for each window,
.CW sam
regenerates the image from its in-memory text
(stored in the
.CW Rasp )
when necessary, although it will use such an image if it is available.
Like
.CW Layers ,
though,
.CW sam
uses the screen bitmap as active storage in which to update the image using
.CW bitblt .\u\s-4\&18,19\s+4\d
The resulting organization, pictured in Figure 6,
has a global array of windows, called
.CW Flayers ,
each of which holds an image of a piece of text held in a data structure
called a
.CW Frame ,
which in turn represents
a rectangular window full of text displayed in some
.CW Bitmap .
Each
.CW Flayer
appears in a global list that orders them all front-to-back
on the display, and simultaneously as an element of a per-file array
that holds all the open windows for that file.
The complement in the terminal of the
.CW File
on the host is called a
.CW Text ;
each connects its
.CW Flayers
to the associated
.CW Rasp .
.KF
.PS
copy "fig6.pic"
.PE
.Cs
Figure 6. Data structures in the terminal.
.CW Flayers
are also linked together into a front-to-back list.
.CW Boxes
are discussed in the next section.
.Ce
.KE
.PP
The
.CW Bitmap
for a
.CW Frame
contains the image of the text.
For a fully visible window, the
.CW Bitmap
will be the screen (or at least the
.CW Layer
in which
.CW sam
is being run),
while for partially obscured windows the
.CW Bitmap
will be off-screen.
If the window is fully obscured, the
.CW Bitmap
will be null.
.PP
The
.CW Bitmap
is a kind of cache.
When making changes to the display, most of the original image will
look the same in the final image, and the update algorithms exploit this.
The
.CW Frame
software updates the image in the
.CW Bitmap
incrementally; the
.CW Bitmap
is not just an image, it is a data structure.\u\s-4\&18,19\s+4\d
The job of the software that updates the display is therefore
to use as much as possible of the existing image (converting the
text from ASCII characters to pixels is expensive) in a sort of two-dimensional
string insertion algorithm.
The details of this process are described in the next section.
.PP
The
.CW Frame
software has no code to support overlapping windows;
its job is to keep a single
.CW Bitmap
up to date.
It falls to the
.CW Flayer
software to multiplex the various
.CW Bitmaps
onto the screen.
The problem of maintaining overlapping
.CW Flayers
is easier than for
.CW Layers \u\s-4\&17\s+4\d
because changes are made synchronously and because the contents of the window
can be reconstructed from the data stored in the
.CW Frame ;
the
.CW Layers
software
makes no such assumptions.
In
.CW sam ,
the window being changed is almost always fully visible, because the current
window is always fully visible, by construction.
However, when multi-file changes are being made, or when
more than one window is open on a file,
it may be necessary to update partially obscured windows.
.PP
There are three cases: the window is
fully visible, invisible (fully obscured), or partially visible.
If fully visible, the
.CW Bitmap
is part of the screen, so when the
.CW Flayer
update routine calls the
.CW Frame
update routine, the screen will be updated directly.
If the window is invisible,
there is no associated
.CW Bitmap ,
and all that is necessary is to update the
.CW Frame
data structure, not the image.
If the window is partially visible, the
.CW Frame
routine is called to update the image in the off-screen
.CW Bitmap ,
which may require regenerating it from the text of the window.
The
.CW Flayer
code then clips this
.CW Bitmap
against the
.CW Bitmaps
of all
.CW Frames
in front of the
.CW Frame
being modified, and the remainder is copied to the display.
.PP
This is much faster than recreating the image off-screen
for every change, or clipping all the changes made to the image
during its update.
Unfortunately, these caches can also consume prohibitive amounts of
memory, so they are freed fairly liberally \(em after every change to the
front-to-back order of the
.CW Flayers .
The result is that
the off-screen
.CW Bitmaps
exist only while multi-window changes are occurring,
which is the only time the performance improvement they provide is needed.
Also, the user interface causes fully-obscured windows to be the
easiest to make \(em
creating a canonically sized and placed window requires only a button click
\(em which reduces the need for caching still further.
.PP
.SH 2
Screen update
.LP
Only two low-level primitives are needed for incremental update:
.CW bitblt ,
which copies rectangles of pixels, and
.CW string
(which in turn calls
.CW bitblt ),
which draws a null-terminated character string in a
.CW Bitmap .
A
.CW Frame
contains a list of
.CW Boxes ,
each of which defines a horizontal strip of text in the window
(see Figure 7).
A
.CW Box
has a character string
.CW str ,
and a
.CW Rectangle
.CW rect
that defines the location of the strip in the window.
(The text in
.CW str
is stored in the
.CW Box
separately from the
.CW Rasp
associated with the window's file, so
.CW Boxes
are self-contained.)
The invariant is that
the image of the
.CW Box
can be reproduced by calling
.CW string
with argument
.CW str
to draw the string in
.CW rect ,
and the resulting picture fits perfectly within
.CW rect .
In other words, the
.CW Boxes
define the tiling of the window.
The tiling may be complicated by long lines of text, which
are folded onto the next line.
Some editors use horizontal scrolling to avoid this complication,
but to be comfortable this technique requires that lines not be
.I too
long;
.CW sam
has no such restriction.
Also, and perhaps more importantly, UNIX programs and terminals traditionally fold
long lines to make their contents fully visible.
.PP
Two special kinds of
.CW Boxes
contain a single
character: either a newline or a tab.
Newlines and tabs are white space.
A newline
.CW Box
always extends to the right edge of the window,
forcing the following
.CW Box
to the next line.
The width of a tab depends on where it is located:
it forces the next
.CW Box
to begin at a tab location.
Tabs also
have a minimum width equivalent to a blank (blanks are
drawn by
.CW string
and are not treated specially); newlines have a minimum width of zero.
.KF
.PS
copy "fig7.pic"
.PE
.sp .5
.Cs
Figure 7. A line of text showing its
.CW Boxes .
The first two blank
.CW Boxes
contain tabs; the last contains a newline.
Spaces are handled as ordinary characters.
.Ce
.KE
.PP
The update algorithms always use the
.CW Bitmap
image of the text (either the display or cache
.CW Bitmap );
they never examine the characters within a
.CW Box
except when the
.CW Box
needs to be split in two.
Before a change, the window consists of a tiling of
.CW Boxes ;
after the change the window is tiled differently.
The update algorithms rearrange the tiles in place, without
backup storage.
The algorithms are not strictly optimal \(em for example, they can
clear a pixel that is later going to be written upon \(em
but they never move a tile that doesn't need to be moved,
and they move each tile at most once.
.CW Frinsert
on a Blit can absorb over a thousand characters a second if the strings
being inserted are a few tens of characters long.
.PP
Consider
.CW frdelete .
Its job is to delete a substring from a
.CW Frame
and restore the image of the
.CW Frame .
The image of a substring has a peculiar shape (see Figure 2) comprising
possibly a partial line,
zero or more full lines,
and possibly a final partial line.
For reference, call this the
.I
Z-shape.
.R
.CW Frdelete
begins by splitting, if necessary, the
.CW Boxes
containing the ends of
the substring so the substring begins and ends on
.CW Box
boundaries.
Because the substring is being deleted, its image is not needed,
so the Z-shape is then cleared.
Then, tiles (that is, the images of
.CW Boxes )
are copied, using
.CW bitblt ,
from immediately after the Z-shape to
the beginning of the Z-shape,
resulting in a new Z-shape.
.CW Boxes "" (
whose contents would span two lines in the new position must first be split.)
.PP
Copying the remainder of the
.CW Frame
tile by tile
this way will clearly accomplish the deletion but eventually,
typically when the copying algorithm encounters a tab or newline,
the old and new
.CW x
coordinates of the tile
to be copied are the same.
This correspondence implies
that the Z-shape has its beginning and ending edges aligned
vertically, and a sequence of at most two
.CW bitblts
can be used to copy the remaining tiles.
The last step is to clear out the resulting empty space at the bottom
of the window;
the number of lines to be cleared is the number of complete lines in the
Z-shape closed by the final
.CW bitblts.
The final step is to merge horizontally adjacent
.CW Boxes
of plain text.
The complete source to
.CW frdelete
is less than 100 lines of C.
.PP
.CW frinsert
is more complicated because it must do four passes:
one to construct the
.CW Box
list for the inserted string,
one to reconnoitre,
one to copy (in opposite order to
.CW frdelete )
the
.CW Boxes
to make the hole for the new text,
and finally one to copy the new text into place.
Overall, though,
.CW frinsert
has a similar flavor to
.CW frdelete ,
and needn't be described further.
.CW Frinsert
and its subsidiary routines comprise 211 lines of C.
.PP
The terminal source code is 3024 lines of C,
and the host source is 5797 lines.
.SH
Discussion
.SH 2
History
.LP
The immediate ancestor of
.CW sam
was the original text editor for the Blit, called
.CW jim .
.CW Sam
inherited
.CW jim 's
two-process structure and mouse language almost unchanged, but
.CW jim
suffered from several drawbacks that were addressed in the design of
.CW sam .
The most important of these was the lack of a command language.
Although
.CW jim
was easy to use for simple editing, it provided no direct help with
large or repetitive editing tasks. Instead, it provided a command to pass
selected text through a shell pipeline,
but this was no more satisfactory than could be expected of a stopgap measure.
.PP
.CW Jim
was written primarily as a vehicle for experimenting with a mouse-based
interface to text, and the experiment was successful.
.CW Jim
had some spin-offs:
.CW mux ,
the second window system for the Blit, is essentially a multiplexed
version of the terminal part of
.CW jim ;
and the debugger
.CW pi 's
user interface\u\s-4\&20\s+4\d was closely modeled on
.CW jim 's.
But after a couple of years,
.CW jim
had become difficult to maintain and limiting to use,
and its replacement was overdue.
.PP
I began the design of
.CW sam
by asking
.CW jim
customers what they wanted.
This was probably a mistake; the answers were essentially a list of features
to be found in other editors, which did not provide any of the
guiding principles I was seeking.
For instance, one common request was for a ``global substitute,''
but no one suggested how to provide it within a cut-and-paste editor.
I was looking for a scheme that would
support such specialized features comfortably in the context of some
general command language.
Ideas were not forthcoming, though, particularly given my insistence
on removing all limits on file sizes, line lengths and so on.
Even worse, I recognized that, since the mouse could easily
indicate a region of the screen that was not an integral number of lines,
the command language would best forget about newlines altogether,
and that meant the command language had to treat the file as a single
string, not an array of lines.
.PP
Eventually, I decided that thinking was not getting me very far and it was
time to try building.
I knew that the terminal part could be built easily \(em
that part of
.CW jim
behaved acceptably well \(em and that most of the hard work was going
to be in the host part: the file interface, command interpreter and so on.
Moreover, I had some ideas about how the architecture of
.CW jim
could be improved without destroying its basic structure, which I liked
in principle but which hadn't worked out as well as I had hoped.
So I began by designing the file data structure,
starting with the way
.CW jim
worked \(em comparable to a single structure merging
.CW Disc
and
.CW Buffer ,
which I split to make the cache more general
\(em and thinking about how global substitute could be implemented.
The answer was clearly that it had to be done in two passes,
and the transcript-oriented implementation fell out naturally.
.PP
.CW Sam
was written bottom-up,
starting from the data structures and algorithms for manipulating text,
through the command language and up to the code for maintaining
the display.
In retrospect, it turned out well, but this implementation method is
not recommended in general.
There were several times when I had a large body of interesting code
assembled and no clue how to proceed with it.
The command language, in particular, took almost a year to figure out,
but can be implemented (given what was there at the beginning of that year)
in a day or two. Similarly, inventing the
.CW Rasp
data structure delayed the
connection of the host and terminal pieces by another few months.
.CW Sam
took about two years to write, although only about four months were
spent actually working on it.
.PP
Part of the design process was unusual:
the subset of the protocol that maintains the
.CW Rasp
was simulated, debugged
and verified by an automatic protocol analyzer,\u\s-4\&21\s+4\d and was bug-free
from the start.
The rest of the protocol, concerned mostly
with keeping menus up to date,
was unfortunately too unwieldy for such analysis,
and was debugged by more traditional methods, primarily
by logging in a file all messages in and out of the host.
.SH 2
Reflections
.LP
.CW Sam
is essentially the only interactive editor used by the sixty or so members of
the computing science research center in which I work.
The same could not be said of
.CW jim ;
the lack of a command language kept some people from adopting it.
The union of a user interface as comfortable as
.CW jim 's
with a command language as powerful as
.CW ed 's
|
