TOUR revision 218306
11556Srgrimes# @(#)TOUR 8.1 (Berkeley) 5/31/93 250471Speter# $FreeBSD: head/bin/sh/TOUR 218306 2011-02-04 22:47:55Z jilles $ 31556Srgrimes 41556SrgrimesNOTE -- This is the original TOUR paper distributed with ash and 51556Srgrimesdoes not represent the current state of the shell. It is provided anyway 61556Srgrimessince it provides helpful information for how the shell is structured, 71556Srgrimesbut be warned that things have changed -- the current shell is 81556Srgrimesstill under development. 91556Srgrimes 101556Srgrimes================================================================ 111556Srgrimes 121556Srgrimes A Tour through Ash 131556Srgrimes 141556Srgrimes Copyright 1989 by Kenneth Almquist. 151556Srgrimes 161556Srgrimes 171556SrgrimesDIRECTORIES: The subdirectory bltin contains commands which can 181556Srgrimesbe compiled stand-alone. The rest of the source is in the main 191556Srgrimesash directory. 201556Srgrimes 211556SrgrimesSOURCE CODE GENERATORS: Files whose names begin with "mk" are 221556Srgrimesprograms that generate source code. A complete list of these 231556Srgrimesprograms is: 241556Srgrimes 25157789Sschweikh program input files generates 26157789Sschweikh ------- ----------- --------- 271556Srgrimes mkbuiltins builtins builtins.h builtins.c 281556Srgrimes mkinit *.c init.c 291556Srgrimes mknodes nodetypes nodes.h nodes.c 301556Srgrimes mksignames - signames.h signames.c 311556Srgrimes mksyntax - syntax.h syntax.c 3217987Speter mktokens - token.h 331556Srgrimes bltin/mkexpr unary_op binary_op operators.h operators.c 341556Srgrimes 351556SrgrimesThere are undoubtedly too many of these. Mkinit searches all the 361556SrgrimesC source files for entries looking like: 371556Srgrimes 381556Srgrimes INIT { 391556Srgrimes x = 1; /* executed during initialization */ 401556Srgrimes } 411556Srgrimes 421556Srgrimes RESET { 431556Srgrimes x = 2; /* executed when the shell does a longjmp 441556Srgrimes back to the main command loop */ 451556Srgrimes } 461556Srgrimes 471556SrgrimesIt pulls this code out into routines which are when particular 481556Srgrimesevents occur. The intent is to improve modularity by isolating 491556Srgrimesthe information about which modules need to be explicitly 501556Srgrimesinitialized/reset within the modules themselves. 511556Srgrimes 521556SrgrimesMkinit recognizes several constructs for placing declarations in 531556Srgrimesthe init.c file. 541556Srgrimes INCLUDE "file.h" 551556Srgrimesincludes a file. The storage class MKINIT makes a declaration 561556Srgrimesavailable in the init.c file, for example: 571556Srgrimes MKINIT int funcnest; /* depth of function calls */ 581556SrgrimesMKINIT alone on a line introduces a structure or union declara- 591556Srgrimestion: 601556Srgrimes MKINIT 611556Srgrimes struct redirtab { 621556Srgrimes short renamed[10]; 631556Srgrimes }; 641556SrgrimesPreprocessor #define statements are copied to init.c without any 651556Srgrimesspecial action to request this. 661556Srgrimes 671556SrgrimesINDENTATION: The ash source is indented in multiples of six 681556Srgrimesspaces. The only study that I have heard of on the subject con- 691556Srgrimescluded that the optimal amount to indent is in the range of four 701556Srgrimesto six spaces. I use six spaces since it is not too big a jump 711556Srgrimesfrom the widely used eight spaces. If you really hate six space 721556Srgrimesindentation, use the adjind (source included) program to change 731556Srgrimesit to something else. 741556Srgrimes 751556SrgrimesEXCEPTIONS: Code for dealing with exceptions appears in 761556Srgrimesexceptions.c. The C language doesn't include exception handling, 771556Srgrimesso I implement it using setjmp and longjmp. The global variable 781556Srgrimesexception contains the type of exception. EXERROR is raised by 79218306Sjillescalling error. EXINT is an interrupt. 801556Srgrimes 811556SrgrimesINTERRUPTS: In an interactive shell, an interrupt will cause an 821556SrgrimesEXINT exception to return to the main command loop. (Exception: 831556SrgrimesEXINT is not raised if the user traps interrupts using the trap 841556Srgrimescommand.) The INTOFF and INTON macros (defined in exception.h) 85157789Sschweikhprovide uninterruptible critical sections. Between the execution 861556Srgrimesof INTOFF and the execution of INTON, interrupt signals will be 871556Srgrimesheld for later delivery. INTOFF and INTON can be nested. 881556Srgrimes 891556SrgrimesMEMALLOC.C: Memalloc.c defines versions of malloc and realloc 901556Srgrimeswhich call error when there is no memory left. It also defines a 911556Srgrimesstack oriented memory allocation scheme. Allocating off a stack 921556Srgrimesis probably more efficient than allocation using malloc, but the 931556Srgrimesbig advantage is that when an exception occurs all we have to do 941556Srgrimesto free up the memory in use at the time of the exception is to 951556Srgrimesrestore the stack pointer. The stack is implemented using a 961556Srgrimeslinked list of blocks. 971556Srgrimes 981556SrgrimesSTPUTC: If the stack were contiguous, it would be easy to store 991556Srgrimesstrings on the stack without knowing in advance how long the 1001556Srgrimesstring was going to be: 1011556Srgrimes p = stackptr; 1021556Srgrimes *p++ = c; /* repeated as many times as needed */ 1031556Srgrimes stackptr = p; 104157789SschweikhThe following three macros (defined in memalloc.h) perform these 1051556Srgrimesoperations, but grow the stack if you run off the end: 1061556Srgrimes STARTSTACKSTR(p); 1071556Srgrimes STPUTC(c, p); /* repeated as many times as needed */ 1081556Srgrimes grabstackstr(p); 1091556Srgrimes 1101556SrgrimesWe now start a top-down look at the code: 1111556Srgrimes 1121556SrgrimesMAIN.C: The main routine performs some initialization, executes 113157789Sschweikhthe user's profile if necessary, and calls cmdloop. Cmdloop 1141556Srgrimesrepeatedly parses and executes commands. 1151556Srgrimes 1161556SrgrimesOPTIONS.C: This file contains the option processing code. It is 1171556Srgrimescalled from main to parse the shell arguments when the shell is 1181556Srgrimesinvoked, and it also contains the set builtin. The -i and -j op- 1191556Srgrimestions (the latter turns on job control) require changes in signal 1201556Srgrimeshandling. The routines setjobctl (in jobs.c) and setinteractive 1211556Srgrimes(in trap.c) are called to handle changes to these options. 1221556Srgrimes 1231556SrgrimesPARSING: The parser code is all in parser.c. A recursive des- 1241556Srgrimescent parser is used. Syntax tables (generated by mksyntax) are 1251556Srgrimesused to classify characters during lexical analysis. There are 1261556Srgrimesthree tables: one for normal use, one for use when inside single 1271556Srgrimesquotes, and one for use when inside double quotes. The tables 1281556Srgrimesare machine dependent because they are indexed by character vari- 1291556Srgrimesables and the range of a char varies from machine to machine. 1301556Srgrimes 1311556SrgrimesPARSE OUTPUT: The output of the parser consists of a tree of 1321556Srgrimesnodes. The various types of nodes are defined in the file node- 1331556Srgrimestypes. 1341556Srgrimes 1351556SrgrimesNodes of type NARG are used to represent both words and the con- 1361556Srgrimestents of here documents. An early version of ash kept the con- 1371556Srgrimestents of here documents in temporary files, but keeping here do- 1381556Srgrimescuments in memory typically results in significantly better per- 1391556Srgrimesformance. It would have been nice to make it an option to use 1401556Srgrimestemporary files for here documents, for the benefit of small 1411556Srgrimesmachines, but the code to keep track of when to delete the tem- 1421556Srgrimesporary files was complex and I never fixed all the bugs in it. 1431556Srgrimes(AT&T has been maintaining the Bourne shell for more than ten 1441556Srgrimesyears, and to the best of my knowledge they still haven't gotten 1451556Srgrimesit to handle temporary files correctly in obscure cases.) 1461556Srgrimes 1471556SrgrimesThe text field of a NARG structure points to the text of the 1481556Srgrimesword. The text consists of ordinary characters and a number of 1491556Srgrimesspecial codes defined in parser.h. The special codes are: 1501556Srgrimes 1511556Srgrimes CTLVAR Variable substitution 1521556Srgrimes CTLENDVAR End of variable substitution 1531556Srgrimes CTLBACKQ Command substitution 1541556Srgrimes CTLBACKQ|CTLQUOTE Command substitution inside double quotes 1551556Srgrimes CTLESC Escape next character 1561556Srgrimes 1571556SrgrimesA variable substitution contains the following elements: 1581556Srgrimes 1591556Srgrimes CTLVAR type name '=' [ alternative-text CTLENDVAR ] 1601556Srgrimes 1611556SrgrimesThe type field is a single character specifying the type of sub- 1621556Srgrimesstitution. The possible types are: 1631556Srgrimes 1641556Srgrimes VSNORMAL $var 1651556Srgrimes VSMINUS ${var-text} 1661556Srgrimes VSMINUS|VSNUL ${var:-text} 1671556Srgrimes VSPLUS ${var+text} 1681556Srgrimes VSPLUS|VSNUL ${var:+text} 1691556Srgrimes VSQUESTION ${var?text} 1701556Srgrimes VSQUESTION|VSNUL ${var:?text} 1711556Srgrimes VSASSIGN ${var=text} 172157789Sschweikh VSASSIGN|VSNUL ${var:=text} 1731556Srgrimes 1741556SrgrimesIn addition, the type field will have the VSQUOTE flag set if the 1751556Srgrimesvariable is enclosed in double quotes. The name of the variable 1761556Srgrimescomes next, terminated by an equals sign. If the type is not 1771556SrgrimesVSNORMAL, then the text field in the substitution follows, ter- 1781556Srgrimesminated by a CTLENDVAR byte. 1791556Srgrimes 1801556SrgrimesCommands in back quotes are parsed and stored in a linked list. 1811556SrgrimesThe locations of these commands in the string are indicated by 1821556SrgrimesCTLBACKQ and CTLBACKQ+CTLQUOTE characters, depending upon whether 1831556Srgrimesthe back quotes were enclosed in double quotes. 1841556Srgrimes 1851556SrgrimesThe character CTLESC escapes the next character, so that in case 1861556Srgrimesany of the CTL characters mentioned above appear in the input, 1871556Srgrimesthey can be passed through transparently. CTLESC is also used to 1881556Srgrimesescape '*', '?', '[', and '!' characters which were quoted by the 1891556Srgrimesuser and thus should not be used for file name generation. 1901556Srgrimes 1911556SrgrimesCTLESC characters have proved to be particularly tricky to get 1921556Srgrimesright. In the case of here documents which are not subject to 1931556Srgrimesvariable and command substitution, the parser doesn't insert any 1941556SrgrimesCTLESC characters to begin with (so the contents of the text 1951556Srgrimesfield can be written without any processing). Other here docu- 1961556Srgrimesments, and words which are not subject to splitting and file name 1971556Srgrimesgeneration, have the CTLESC characters removed during the vari- 198157789Sschweikhable and command substitution phase. Words which are subject to 1991556Srgrimessplitting and file name generation have the CTLESC characters re- 2001556Srgrimesmoved as part of the file name phase. 2011556Srgrimes 2021556SrgrimesEXECUTION: Command execution is handled by the following files: 2031556Srgrimes eval.c The top level routines. 2041556Srgrimes redir.c Code to handle redirection of input and output. 2051556Srgrimes jobs.c Code to handle forking, waiting, and job control. 206157789Sschweikh exec.c Code to do path searches and the actual exec sys call. 2071556Srgrimes expand.c Code to evaluate arguments. 2081556Srgrimes var.c Maintains the variable symbol table. Called from expand.c. 2091556Srgrimes 2101556SrgrimesEVAL.C: Evaltree recursively executes a parse tree. The exit 2111556Srgrimesstatus is returned in the global variable exitstatus. The alter- 2121556Srgrimesnative entry evalbackcmd is called to evaluate commands in back 2131556Srgrimesquotes. It saves the result in memory if the command is a buil- 2141556Srgrimestin; otherwise it forks off a child to execute the command and 2151556Srgrimesconnects the standard output of the child to a pipe. 2161556Srgrimes 2171556SrgrimesJOBS.C: To create a process, you call makejob to return a job 2181556Srgrimesstructure, and then call forkshell (passing the job structure as 2191556Srgrimesan argument) to create the process. Waitforjob waits for a job 2201556Srgrimesto complete. These routines take care of process groups if job 2211556Srgrimescontrol is defined. 2221556Srgrimes 2231556SrgrimesREDIR.C: Ash allows file descriptors to be redirected and then 2241556Srgrimesrestored without forking off a child process. This is accom- 2251556Srgrimesplished by duplicating the original file descriptors. The redir- 226157789Sschweikhtab structure records where the file descriptors have been dupli- 2271556Srgrimescated to. 2281556Srgrimes 2291556SrgrimesEXEC.C: The routine find_command locates a command, and enters 2301556Srgrimesthe command in the hash table if it is not already there. The 2311556Srgrimesthird argument specifies whether it is to print an error message 2321556Srgrimesif the command is not found. (When a pipeline is set up, 2331556Srgrimesfind_command is called for all the commands in the pipeline be- 2341556Srgrimesfore any forking is done, so to get the commands into the hash 2351556Srgrimestable of the parent process. But to make command hashing as 2361556Srgrimestransparent as possible, we silently ignore errors at that point 2371556Srgrimesand only print error messages if the command cannot be found 2381556Srgrimeslater.) 2391556Srgrimes 2401556SrgrimesThe routine shellexec is the interface to the exec system call. 2411556Srgrimes 2421556SrgrimesEXPAND.C: Arguments are processed in three passes. The first 2431556Srgrimes(performed by the routine argstr) performs variable and command 2441556Srgrimessubstitution. The second (ifsbreakup) performs word splitting 2451556Srgrimesand the third (expandmeta) performs file name generation. If the 2461556Srgrimes"/u" directory is simulated, then when "/u/username" is replaced 2471556Srgrimesby the user's home directory, the flag "didudir" is set. This 2481556Srgrimestells the cd command that it should print out the directory name, 2491556Srgrimesjust as it would if the "/u" directory were implemented using 2501556Srgrimessymbolic links. 2511556Srgrimes 2521556SrgrimesVAR.C: Variables are stored in a hash table. Probably we should 2531556Srgrimesswitch to extensible hashing. The variable name is stored in the 2541556Srgrimessame string as the value (using the format "name=value") so that 2551556Srgrimesno string copying is needed to create the environment of a com- 2561556Srgrimesmand. Variables which the shell references internally are preal- 2571556Srgrimeslocated so that the shell can reference the values of these vari- 2581556Srgrimesables without doing a lookup. 2591556Srgrimes 2601556SrgrimesWhen a program is run, the code in eval.c sticks any environment 2611556Srgrimesvariables which precede the command (as in "PATH=xxx command") in 2621556Srgrimesthe variable table as the simplest way to strip duplicates, and 2631556Srgrimesthen calls "environment" to get the value of the environment. 2641556Srgrimes 2651556SrgrimesBUILTIN COMMANDS: The procedures for handling these are scat- 2661556Srgrimestered throughout the code, depending on which location appears 2671556Srgrimesmost appropriate. They can be recognized because their names al- 2681556Srgrimesways end in "cmd". The mapping from names to procedures is 269157789Sschweikhspecified in the file builtins, which is processed by the mkbuilt- 270157789Sschweikhins command. 2711556Srgrimes 2721556SrgrimesA builtin command is invoked with argc and argv set up like a 2731556Srgrimesnormal program. A builtin command is allowed to overwrite its 2741556Srgrimesarguments. Builtin routines can call nextopt to do option pars- 2751556Srgrimesing. This is kind of like getopt, but you don't pass argc and 2761556Srgrimesargv to it. Builtin routines can also call error. This routine 2771556Srgrimesnormally terminates the shell (or returns to the main command 2781556Srgrimesloop if the shell is interactive), but when called from a builtin 2791556Srgrimescommand it causes the builtin command to terminate with an exit 2801556Srgrimesstatus of 2. 2811556Srgrimes 2821556SrgrimesThe directory bltins contains commands which can be compiled in- 2831556Srgrimesdependently but can also be built into the shell for efficiency 2841556Srgrimesreasons. The makefile in this directory compiles these programs 2851556Srgrimesin the normal fashion (so that they can be run regardless of 2861556Srgrimeswhether the invoker is ash), but also creates a library named 2871556Srgrimesbltinlib.a which can be linked with ash. The header file bltin.h 2881556Srgrimestakes care of most of the differences between the ash and the 2891556Srgrimesstand-alone environment. The user should call the main routine 2901556Srgrimes"main", and #define main to be the name of the routine to use 2911556Srgrimeswhen the program is linked into ash. This #define should appear 2921556Srgrimesbefore bltin.h is included; bltin.h will #undef main if the pro- 2931556Srgrimesgram is to be compiled stand-alone. 2941556Srgrimes 2951556SrgrimesCD.C: This file defines the cd and pwd builtins. The pwd com- 2961556Srgrimesmand runs /bin/pwd the first time it is invoked (unless the user 2971556Srgrimeshas already done a cd to an absolute pathname), but then 2981556Srgrimesremembers the current directory and updates it when the cd com- 2991556Srgrimesmand is run, so subsequent pwd commands run very fast. The main 3001556Srgrimescomplication in the cd command is in the docd command, which 3011556Srgrimesresolves symbolic links into actual names and informs the user 3021556Srgrimeswhere the user ended up if he crossed a symbolic link. 3031556Srgrimes 3041556SrgrimesSIGNALS: Trap.c implements the trap command. The routine set- 3051556Srgrimessignal figures out what action should be taken when a signal is 3061556Srgrimesreceived and invokes the signal system call to set the signal ac- 3071556Srgrimestion appropriately. When a signal that a user has set a trap for 3081556Srgrimesis caught, the routine "onsig" sets a flag. The routine dotrap 3091556Srgrimesis called at appropriate points to actually handle the signal. 3101556SrgrimesWhen an interrupt is caught and no trap has been set for that 3111556Srgrimessignal, the routine "onint" in error.c is called. 3121556Srgrimes 3131556SrgrimesOUTPUT: Ash uses it's own output routines. There are three out- 3141556Srgrimesput structures allocated. "Output" represents the standard out- 3151556Srgrimesput, "errout" the standard error, and "memout" contains output 3161556Srgrimeswhich is to be stored in memory. This last is used when a buil- 3171556Srgrimestin command appears in backquotes, to allow its output to be col- 3181556Srgrimeslected without doing any I/O through the UNIX operating system. 3191556SrgrimesThe variables out1 and out2 normally point to output and errout, 3201556Srgrimesrespectively, but they are set to point to memout when appropri- 3211556Srgrimesate inside backquotes. 3221556Srgrimes 3231556SrgrimesINPUT: The basic input routine is pgetc, which reads from the 3241556Srgrimescurrent input file. There is a stack of input files; the current 3251556Srgrimesinput file is the top file on this stack. The code allows the 3261556Srgrimesinput to come from a string rather than a file. (This is for the 3271556Srgrimes-c option and the "." and eval builtin commands.) The global 3281556Srgrimesvariable plinno is saved and restored when files are pushed and 3291556Srgrimespopped from the stack. The parser routines store the number of 3301556Srgrimesthe current line in this variable. 3311556Srgrimes 3321556SrgrimesDEBUGGING: If DEBUG is defined in shell.h, then the shell will 3331556Srgrimeswrite debugging information to the file $HOME/trace. Most of 3341556Srgrimesthis is done using the TRACE macro, which takes a set of printf 3351556Srgrimesarguments inside two sets of parenthesis. Example: 3361556Srgrimes"TRACE(("n=%d0, n))". The double parenthesis are necessary be- 3371556Srgrimescause the preprocessor can't handle functions with a variable 3381556Srgrimesnumber of arguments. Defining DEBUG also causes the shell to 3391556Srgrimesgenerate a core dump if it is sent a quit signal. The tracing 3401556Srgrimescode is in show.c. 341