1 Find

find       FROM/A,TO/K,PAT/K,N/S

The find command copies the file given by the FROM argument to the file given by the TO argument. In the process it scans the text for occurences of a search pattern. Only lines containing or not containing the search pattern are output; that is, find selects from a file just those lines containing a search pattern or just those lines not containing it.

The search pattern is given by the PAT argument and is formed according to the rules given below. If the pattern is prefixed by a tilde symbol (~), then lines not containing the pattern are output, otherwise lines containing the pattern are output.

If the N switch is given then the lines are numbered on output.

1.1 Patterns

The simplest form of a search pattern is a character string identical to the one sought.

Preceding the pattern with a grave accent (`) specifies that the string must appear at the beginning of a line. The grave accent in any other position has no special meaning.

Terminating a pattern with an apostrophe (') specifies that the string must occur at the end of a line. An apostrophe in any other position has no special meaning.

The following patterns illustrate their use:

pattern meaning
`abcd  the string “abcd” at the beginning of a line
xyz'  the string “xyz” at the end of a line
`xxx'  a line consisting only of “xxx”
ab'cd`e the string “ab’cd‘e” occuring anywhere in a line

A question mark (?) in a pattern matches any character in that position of a string. Thus the pattern f??t matches “foot”, “feet”, “f it”, and so on.

An asterisk (*) causes a match on zero or more occurences of the preceding character. An asterisk at the beginning of a pattern has no special meaning. The following patterns illustrate the use of the asterisk:

pattern matching strings
*abc  “*abc”
a*bc  “bc”, “abc”, “aabc”, “aaabc”, …
aa*bc  “abc”, “aabc”, “aaabc”, “aaaabc”, …
s?*p  “sp”, “sxp”, “sleep”, “s12 xp”, …

1.2 Escape sequences

Sometimes it is necessary to enter nonprintable characters or characters that ordinarily have special meaning. You can enter such characters from the keyboard by using the colon as an escape character. An escape character changes the meaning of the character that follows it.

Together the escape character and the character following it are seen as a single character by the command. The escape sequences are:

:b  backspace
:n  newline
:s  space
:t  tab
<other character> the actual character given

Some special characters known as metacharacters have special meaning when they appear in the pattern. You may use the <other character> escape sequence to force them to be seen as themselves in these contexts.

The colon, having a special use (escape character), must be escaped to be accepted as itself; thus :: is taken for a single colon.

Provision is made for the space character, since if an actual space were included in the pattern it would delimit the pattern.

1.3 Metacharacters

Certain characters assume special meanings when they appearn in the pattern. As a group these characters are designated metacharacters (as opposed to ordinary characters). Since these metacharacters occasionally need to appear as ordinary characters in a search pattern, they may, in such cases, be entered as escape sequences. The metacharacters are given below:

symbol name  use
:  colon  escape character
`  grave accent  matches the beginning of the line
'  apostrophe  matches the end of the line
?  question mark matches any character
* asterisk matches zero or more occurences of the

preceding character

[ left bracket introduces a character class definition
]  right bracket terminates a character class definition
- hyphen indicates a range of characters in a

character class definition

~ tilde complements a character class definition

The metacharacters are defined in Section 2.2. You may change these metacharacter assignments to suit your fancy by changing that section before tangling and compiling.

1.4 Character classes

Since the set of decimal digits, lowercase letters, and uppercase letters are used frequently, and since they are such long lists, a shorthand method of specifying

[012\dots9], [abc\dots z], and [ABC\dots Z] exists. You may place a hy-

phen between the first and last characters. Thus, the pattern a[0-9] matches “a0”, “a1”, and so on.

You need not specify the entire set of decimal digits, nor all of the letters when the shorthand notation is used. You may give [5-7], [a-g], and so on. The only restrictions are that the lower-valued character must be listed in front of of the hyphen. You may use the shorthand notation in a list of characters specifying a character class. Thus, [s12g5-7a-zA-Z$(] is a valid character class.

The hyphen (-) has special meaning only when it falls between characters in a character class definition. If it appears at either end of the definition or outside such a definition, it has no special meaning.

If the first character inside the left bracket is a tilde ~, it causes a match on any character except those listed.

It is important to think of the character class as a single character position. If you need a literal [ or ] in a pattern, then escape it as :[ or :], respec-

tively.

This command won’t replace grep in anyone’s toolbox, but it does have the advantage of working within the BCPL interpreter cinterp.

2 Literate Programs

This document not only describes the implementation of find, it is the implementation. The noweb system for “literate programming” generates both the document and the code from a single source. This source consists of interleaved prose and labelled code fragments. The fragments are written in the order that best suits describing the program, namely the order you see in this document, not the order dictated by the BCPL programming language. The program noweave accepts the source and produces the document’s typescript, which includes all of the code and all of the text. The program notangle extracts all of the code, in the proper order for compilation.

Fragments contain source code and references to other fragments. Fragment definitions are preceded by their labels in angle brackets. For example, the code

4a  ⟨a fragment label 4a⟩≡  4c ▷

  sum := 0

FOR i = 1 TO 10 DO ⟨increment sum 4b⟩

4b  ⟨increment sum 4b⟩≡  (4a)

   sum := sum + x!i

sums the elements of x. Several fragments may have the same name; notangle concatenates their definitions to produce a single fragment. noweave identifies this concatenation by using + ≡ instead of ≡ in continued definitions:

4c  ⟨a fragment label 4a⟩+≡  ◁ 4a

  writef("%i*n", sum)

Fragment definitions are like macro definitions; notangle extracts a program by expanding one fragment. If its definition refers to other fragments, they themselves are expanded, and so on.

Fragment definitions include aids to help readers navigate among them. Each fragment name ends with the number of the page on which the fragment’s definition begins and a letter giving its sequence within that page. If there is only one fragment on a page then there is no letter. This is also shown in the left margin. Each continued definition also shows the previous definition, and the next continued definition, if there is one. ◁ 7b is an example of a previous definition that appears on page 7, and 11 ▷ says the definition is continued on page 11. These annotations form a double linked list of definitions; the left arrow points to the previous definition in the list and the right arrow points to the next one. The previous link on the first definition is omitted, and the next link on the last definition is omitted. These lists are complete: If some of a fragment’s definition appears on the same page with each other, the links refer to the page on which they appear.

Fragments also show a list of pages on which the fragment is used, as illustrated by the (4a) to the right of the definition for ⟨increment sum⟩, above.

2.1 The program

This program is translated from the Small-C program of the same name appearing in the Small-Tools package by J. E. Hendrix.

Translated into BCPL the program has the usual structure. The fragment name consisting of an asterisk indicates to noweb that this is the root fragment, which is expanded to generate the program.

5a ⟨* 5a⟩≡

GET "libhdr"

⟨manifests 5b⟩

⟨statics 6c⟩

⟨debug stuff 20c⟩

⟨procedure start 6a⟩

2.2 The metacharacters

All of the metacharacters are defined here. You may change them to suit your fancy before tangling and compiling. (And don’t forget to change the documentation in Section 1.3.)

5b  ⟨manifests 5b⟩≡  (5a) 10c ▷

MANIFEST {
Char    = 'c'      // identifies a character
BoL     = '`'      // beginning of line
EoL     = '*''     // end of line
Any     = '?'      // any character
CCl     = '['      // begin character class
NCCl    = '^'      // negation of chracter class
CClEnd  = ']'      // end of character class
Closure = '**'     // zero or more occurences
Escape  = ':'      // escape character
NotC    = '^'      // negation character
}

Defines:

Any, used in chunks 13a, 19a, and 20a. BoL, used in chunks 13, 19a, and 20a. CCl, used in chunks 13a, 15a, 19a, and 20a. CClEnd, used in chunk 15. Closure, used in chunks 13, 16a, 18, and 20a. EoL, used in chunks 13, 19a, and 20a. Escape, used in chunks 14b and 15b. NCCl, used in chunks 15a, 19a, and 20a. NotC, used in chunk 15a.

3 The start procedure

By convention execution of a BCPL program begins with a call to start. In this program start processes its command line to get the pattern, compiles the pattern into an internal format, opens the input stream, searches for matching lines and prints them, and finally cleans up.

6a  ⟨procedure start 6a⟩≡  (5a)

LET start() = VALOF {

⟨error procedures 20b⟩ ⟨i/o procedures 11a⟩ ⟨pattern creation procedures 13a⟩ ⟨pattern matching procedures 17b⟩

⟨procedure start’s variables 7b⟩

⟨prepare for bail out 6b⟩ ⟨process command line 7c⟩ ⟨compile pattern 8c⟩ ⟨find input stream 9a⟩ ⟨search for matching lines 9b⟩

fin:

⟨deallocate memory 8e⟩ ⟨close streams 10b⟩

RESULTIS 0
}

Defines:

start, never used.

3.1 Bailing out in case of trouble

We hope we don’t have to, but just in case…

6b  ⟨prepare for bail out 6b⟩≡  (6a)

fin_p, fin_l := level(), fin

Uses fin l 6c and fin p 6c.

6c  ⟨statics 6c⟩≡  (5a) 7e ▷

STATIC {
fin_p; fin_l
}

Defines:

fin l, used in chunks 6b and 7a. fin p, used in chunks 6b and 7a.

Now we can get to the cleanup code from anywhere within the program.

7a  ⟨bail out 7a⟩≡  (20b)

  longjump(fin_p, fin_l)

Uses fin l 6c and fin p 6c.

3.2 Processing the command line arguments

The first thing we have to do is to extract the arguments from the command line. The input stream and the pattern are required arguments, while an output stream is optional.

7b  ⟨procedure start’s variables 7b⟩≡  (6a)

  LET argv = VEC 10

Defines:

argv, used in chunks 7–9.

We let rdargs process the command line for us.

7c  ⟨process command line 7c⟩≡  (6a) 7d ▷

IF 0 = rdargs("⟨rdargs argument 7f⟩", argv, 10) DO ⟨error: usage 7g⟩

Uses argv 7b.

We’re going to get a little tricky with the line counter. If line numbering is not specified then we initialize the counter to -1. If line numbering is specified then we initialize the counter to the number of lines read so far (which is zero). From this point on, the line count will get incremented upon newline only if the count is nonnegative.

7d  ⟨process command line 7c⟩+≡  (6a) ◁ 7c

  lcount := -1 - argv!3

Uses argv 7b and lcount 7e.

We need to define the line counter.

7e  ⟨statics 6c⟩+≡  (5a) ◁ 6c 8a ▷

  STATIC {
   lcount
  }

Defines:

lcount, used in chunks 7d, 11a, and 12a.

We define the rdargs argument as a separate fragment because it will be passed on to error to tell the user what we expect on the command line.

7f  ⟨rdargs argument 7f⟩≡  (7)

  FROM/A,TO/K,PAT/A/K,N/S

Rather than merely telling the user his arguments are wrong, let’s tell him what we expect.

7g  ⟨error: usage 7g⟩≡  (7c)

  error("Invalid args: FIND ⟨rdargs argument 7f⟩")

Uses error 20b.

3.3 Compiling the pattern

The pattern must have been specified on the command line.

8a  ⟨statics 6c⟩+≡  (5a) ◁ 7e 8b ▷

STATIC {
 pbuf = 0
}

Defines:

pbuf, used in chunks 8, 13–16, and 18–21.

The user may have specified lines not matching the pattern.

8b  ⟨statics 6c⟩+≡  (5a) ◁ 8a 8f ▷

STATIC {
 invert = 0
}

Defines:

invert, used in chunks 8c, 10a, and 13a.

Now it’s a matter of allocating the pattern buffer and compiling the pattern from the string given us on the command line.

8c  ⟨compile pattern 8c⟩≡  (6a)

pbuf := getvec(MaxPat)

UNLESS pbuf DO ⟨error: no memory 8d⟩ ⟨initialize pattern buffer 21a⟩

IF '~' = argv!2%1 DO invert := -1
UNLESS makpat(argv!2) error("Pattern too long")
Uses argv 7b, error 20b, invert 8b, makpat 13a, MaxPat 12b, and pbuf 8a.

In the unlikely event we run out of memory we want to let the user know why we terminated without doing any real work.

8d  ⟨error: no memory 8d⟩≡  (8c 10a)

error("Insufficient memory")

Uses error 20b.

The pattern needs to be deallocated when we’re done.

8e  ⟨deallocate memory 8e⟩≡  (6a) 9f ▷

IF freevec DO freevec(pbuf)

Uses pbuf 8a.

3.4 Opening the input stream

The input stream must have been specified on the command line.

8f  ⟨statics 6c⟩+≡  (5a) ◁ 8b 9c ▷

STATIC {
 instream = 0
}

Defines:

instream, used in chunks 9a and 10b.

We attempt to find the file and if successful, select it for input.

9a  ⟨find input stream 9a⟩≡  (6a)

instream := findinput(argv!0)
UNLESS instream DO error("Can't open input")
selectinput(instream)
Uses argv 7b, error 20b, and instream 8f.

3.5 Searching for matching lines

We open an output stream if one was specified, then print matching lines from the input stream.

9b  ⟨search for matching lines 9b⟩≡  (6a)

⟨open output stream 9d⟩ ⟨print matching lines 10a⟩

The user may have specified an output stream.

9c  ⟨statics 6c⟩+≡  (5a) ◁ 8f 9e ▷

STATIC {
 outstream = 0
}

Defines:

outstream, used in chunks 9d and 10b.

If the user had specified an output stream then we find it and select it for output.

9d  ⟨open output stream 9d⟩≡  (9b)

IF argv!1 DO {
 outstream := findoutput(argv!1)
 UNLESS outstream DO error("Can't open output")
 selectoutput(outstream)
}
Uses argv 7b, error 20b, and outstream 9c.

We need a buffer to hold the input line. This buffer will be allocated when the command executes.

9e  ⟨statics 6c⟩+≡  (5a) ◁ 9c

STATIC {
 lbuf = 0
}

Defines:

lbuf, used in chunks 9–12, 17–19, and 21c.

And we must not forget to deallocate it when we’re done with it.

9f  ⟨deallocate memory 8e⟩+≡  (6a) ◁ 8e

IF lbuf DO freevec(lbuf)

Uses lbuf 9e.

Now we allocate the line buffer then read each line of input and see whether it matches.

10a  ⟨print matching lines 10a⟩≡  (9b)

  lbuf := getvec(MaxLine + 1)

UNLESS lbuf DO ⟨error: no memory 8d⟩

  WHILE 0 <= readline() DO
   IF match() NEQV invert DO writeline()
Uses invert 8b, lbuf 9e, match 17b, MaxLine 10c, readline 11a, and writeline 12a.

3.6 Closing the streams

We close both the input stream and the output stream before terminating.

10b  ⟨close streams 10b⟩≡  (6a)

  IF instream  DO endread()
  IF outstream DO endwrite()
Uses instream 8f and outstream 9c.

4 Input/Output

This command would be rather useless if it couldn’t perform any input or output.

This command works with individual lines. Even though patterns spanning multiple lines could be given on the command line, such patterns will not work.

The input line is stored unpacked (one character per word) in the variable lbuf. There is no length word; the line is terminated with a zero word. This means that the standard library routines such as writes cannot be used to write it out. It does mean that lines longer than 255 characters can be handled… as long as they’re less than MaxLine characters.

4.1 Input

We will fold input lines longer than MaxLine characters.

10c  ⟨manifests 5b⟩+≡  (5a) ◁ 5b 12b ▷

  MANIFEST {
   MaxLine = 1024
  }

Defines:

MaxLine, used in chunks 10–12.

Since we’re dealing with lines, we need a function to read a line from the input stream. The characters are placed unpacked into lbuf. A line is terminated by a newline or an end of stream, or if we reach MaxLine characters. Carriage returns are ignored, thus making the command virtually worthless for Mac-formatted files. But then, this is already rather worthless for true binary files.

This function returns the number of characters read, or -1 if end of stream.

11a  ⟨i/o procedures 11a⟩≡  (6a) 12a ▷

LET readline() = VALOF {
 LET i, ch = 0, ?
 UNLESS lcount < 0 DO lcount := lcount + 1
 lbuf!2 := 0
 WHILE i < MaxLine DO {

⟨read and store character 11b⟩

⟨handle possible line termination 11c⟩

 }

⟨store terminator 11d⟩

 RESULTIS i - 1
}

Defines:

readline, used in chunk 10a.

Uses lbuf 9e, lcount 7e, and MaxLine 10c.

This should be pretty obvious.

11b  ⟨read and store character 11b⟩≡  (11a)

ch := rdch()
i := i + 1
lbuf!i := ch

Uses lbuf 9e.

The character just read may terminate the line.

11c  ⟨handle possible line termination 11c⟩≡  (11a)

SWITCHON ch INTO {
CASE endstreamch:   IF 1 = i    RESULTIS -1
CASE '*n':                      i := i - 1; BREAK
CASE '*c':                      i := i - 1
default:                        ENDCASE
}

We want to make sure the line buffer is terminated properly.

11d  ⟨store terminator 11d⟩≡  (11a)

i := i + 1
lbuf!i := 0

Uses lbuf 9e.

4.2 Output

Since we’re dealing with unpacked lines, we need a procedure to print one out. This is a lot easier than reading one since the only interpretation we have to apply to the line is searching for its end. And, since we stripped off the newline when we read it in, we have to tack one on at the end after writing it out.

12a  ⟨i/o procedures 11a⟩+≡  (6a) ◁ 11a

  AND writeline() BE {
   IF 0 <= lcount DO writef("%i5: ", lcount)
   FOR i = 1 TO MaxLine DO {
    UNLESS lbuf!i BREAK
    wrch(lbuf!i)
   }
   newline()
  }

Defines:

writeline, used in chunk 10a.

Uses lbuf 9e, lcount 7e, and MaxLine 10c.

5 Pattern creation

We want to compile the pattern into an internal format to make the matching easier. The compiled pattern is placed unpacked into the vector pbuf.

We have to put an upper limit on the size of the pattern.

12b  ⟨manifests 5b⟩+≡  (5a) ◁ 10c 12c ▷

  MANIFEST {
   MaxPat = 257
  }

Defines:

MaxPat, used in chunks 8c, 14a, and 21.

Some symbolic names to help us deal with patterns.

12c  ⟨manifests 5b⟩+≡  (5a) ◁ 12b

  MANIFEST {
   Count = 1; PrevCl; StartCl; CloSize
  }

Defines:

CloSize, used in chunks 16a, 18, and 20a.

Count, used in chunk 18.

PrevCl, used in chunk 18.

StartCl, used in chunk 18.

Compile pattern specified by arg into pattern buffer pbuf.

13a  ⟨pattern creation procedures 13a⟩≡  (6a)

LET makpat(arg) = VALOF {

⟨add set 14a⟩ ⟨map escape character 14b⟩ ⟨get character class 15a⟩ ⟨insert closure 16a⟩

LET i, j, lastcl, lastj, lj, from = ?, 1, -1, 1, ?, ?
i := 1 - invert
from := i
WHILE i <= arg%0 DO {
 lj := j
 TEST      Any     = arg%i                 THEN addset(Any, @j)
 ELSE TEST BoL     = arg%i & i = from      THEN addset(BoL, @j)
 ELSE TEST EoL     = arg%i & 0 = arg%(i+1) THEN addset(EoL, @j)
 ELSE TEST CCl     = arg%i                 THEN
  UNLESS getccl(arg, @i, @j)                    BREAK
 ELSE TEST Closure = arg%i & from < i      THEN {

⟨add closure 13c⟩

 } ELSE {

⟨add literal character 13b⟩

 }
 lastj := lj
 i := i + 1
}
IF FALSE = addset(0, @j) | i < arg%0 RESULTIS FALSE
RESULTIS TRUE
}

Defines:

makpat, used in chunk 8c.

Uses addset 14a, Any 5b, BoL 5b, CCl 5b, Closure 5b, EoL 5b, getccl 15a, and invert 8b.

A literal character is added to the pattern by flagging it as such and then adding the character. Remember that the character could be an escaped character.

13b  ⟨add literal character 13b⟩≡  (13a)

addset(Char, @j)
addset(esc(arg, @i), @j)

Uses addset 14a and esc 14b.

13c  ⟨add closure 13c⟩≡  (13a)

lj := lastj
IF BoL = pbuf!lj | EoL = pbuf!lj | Closure = pbuf!lj BREAK
lastcl := stclos(@j, @lastj, lastcl)
Uses BoL 5b, Closure 5b, EoL 5b, pbuf 8a, and stclos 16a.

Put character c into pattern buffer pbuf and increment index !j. Returns FALSE if the pattern buffer is full.

14a  ⟨add set 14a⟩≡  (13a)

LET addset(c, j) = VALOF {
IF MaxPat <= !j RESULTIS FALSE
pbuf!!j := c
!j := !j + 1
RESULTIS TRUE
}

Defines:

addset, used in chunks 13, 15, and 16. Uses MaxPat 12b and pbuf 8a.

Map array%i into escaped character if appropriate.

14b  ⟨map escape character 14b⟩≡  (13a)

AND esc(array, i) = VALOF {
TEST Escape ~= array%!i     RESULTIS array%!i
ELSE TEST 0 =  array%(!i+1) RESULTIS Escape
ELSE {
 !i := !i + 1
 SWITCHON array%!i INTO {
 CASE 't':                  RESULTIS '*t'
 CASE 'b':                  RESULTIS '*b'
 CASE 's':                  RESULTIS ' '
 DEFAULT:                   RESULTIS array%!i
 }
}
}

Defines:

esc, used in chunks 13b, 15b, and 16b. Uses Escape 5b.

Expand character class at arg%i into pbuf!j.

15a  ⟨get character class 15a⟩≡  (13a)

AND getccl(arg, i, j) = VALOF {

⟨expand hyphen 16b⟩

LET jstart = ?
LET digit  = "0123456789"
LET loalf  = "abcdefghijklmnopqrstuvwxyz"
LET upalf  = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
!i := !i + 1
TEST NotC = arg%!i THEN {
 addset(NCCl, j)
 !i := !i + 1
} ELSE addset(CCl, j)

⟨expand class 15b⟩

RESULTIS CClEnd = arg%!i
}

Defines:

getccl, used in chunk 13a.

Uses addset 14a, CCl 5b, CClEnd 5b, NCCl 5b, and NotC 5b.

Expand character class in arg into pbuf.

15b  ⟨expand class 15b⟩≡  (15a)

jstart := !j
addset(0, j)
WHILE arg%!i & CClEnd ~= arg%!i DO {
TEST      Escape = arg%!i           THEN addset(esc(arg, i), j)
ELSE TEST '-'    ~= arg%!i          THEN addset(arg%!i, j)
ELSE TEST j <= 1 | 0 = arg%!i       THEN addset('-', j)
ELSE TEST '0' <= pbuf!(!j-1) <= '9' THEN dodash(digit, arg, i, j)
ELSE TEST 'a' <= pbuf!(!j-1) <= 'z' THEN dodash(loalf, arg, i, j)
ELSE TEST 'A' <= pbuf!(!j-1) <= 'Z' THEN dodash(upalf, arg, i, j)
ELSE                                addset('-', j)
!i := !i + 1
}
pbuf!jstart := !j - jstart - 1
Uses addset 14a, CClEnd 5b, dodash 16b, esc 14b, Escape 5b, and pbuf 8a.

Insert closure entry at pbuf!j.

16a  ⟨insert closure 16a⟩≡  (13a)

AND stclos(j, lastj, lastcl) = VALOF {
LET jp, jt = ?, ?
jp := !j - 1
WHILE !lastj <= jp DO {
 jt := jp + CloSize
 addset(pbuf!jp, @jt)
 jp := jp - 1
}
!j := !j + CloSize
jp := !lastj
addset(Closure, lastj)
addset(0,       lastj)
addset(lastcl,  lastj)
addset(0,       lastj)
RESULTIS jp
}

Defines:

stclos, used in chunk 13c.

Uses addset 14a, CloSize 12c, Closure 5b, and pbuf 8a.
Expand arg%(i-1) - arg%(i+1) into pbuf!j . . .

16b  ⟨expand hyphen 16b⟩≡  (15a)

LET dodash(set, arg, i, j) BE {

⟨find character 17a⟩

LET lower, upper = ?, ?
!i := !i + 1
!j := !j - 1
upper := index(set, esc(arg, i))
lower := index(set, pbuf!!j)
WHILE lower <= upper DO {
 addset(set%lower, j)
 lower := lower + 1
}
}

Defines:

dodash, used in chunk 15b. Uses addset 14a, esc 14b, index 17a, and pbuf 8a.

Find character c in string s.

17a  ⟨find character 17a⟩≡  (16b)

LET index(s, c) = VALOF {
LET i = 1
WHILE s%i DO {
 IF s%i = c RESULTIS i
 i := i + 1
}
RESULTIS -1
}

Defines:

index, used in chunk 16b.

6 Pattern matching

These procedures try to match the compiled pattern in pbuf against the input line in lbuf.

This function tries to match a pattern anywhere in lbuf.

17b  ⟨pattern matching procedures 17b⟩≡  (6a)

LET match() = VALOF {

⟨look for match 18⟩

LET i = 1
WHILE TRUE DO {
 IF 0 <= amatch(i) RESULTIS TRUE
 i := i + 1
 UNLESS lbuf!i RESULTIS FALSE
}
}

Defines:

match, used in chunk 10a. Uses amatch 18 and lbuf 9e.

This function looks for a match starting at lbuf!from.

18  ⟨look for match 18⟩≡  (17b)

LET amatch(from) = VALOF {

⟨match single pattern 19a⟩

LET i, j, offset, stack = ?, 1, ?, -1
offset := from
WHILE pbuf!j DO {
TEST Closure = pbuf!j THEN {
stack := j
j := j + CloSize
i := offset
WHILE lbuf!i UNLESS omatch(@i, j) BREAK
pbuf!(stack+Count) := i - offset
pbuf!(stack+StartCl) := offset
offset := i
} ELSE UNLESS omatch(@offset, j) DO {
WHILE 0 <= stack DO {
 IF 0 < pbuf!(stack+Count) BREAK
 stack := pbuf!(stack+PrevCl)
}
IF stack < 0 RESULTIS -1
pbuf!(stack+Count) := pbuf!(stack+Count) - 1
j := stack + CloSize
offset := pbuf!(stack+StartCl) + pbuf!(stack+Count)
}

⟨increment by pattern size 20a⟩

}
RESULTIS offset
}

Defines:

amatch, used in chunks 17b and 20a.

Uses CloSize 12c, Closure 5b, Count 12c, lbuf 9e, omatch 19a, pbuf 8a, PrevCl 12c,
and StartCl 12c.

Try to match a single pattern at pbuf!j.

19a  ⟨match single pattern 19a⟩≡  (18)

LET omatch(i, j) = VALOF {

⟨locate character in class 19b⟩

LET bump = -1
TEST      BoL  = pbuf!j  IF     1 = !i     bump := 0
ELSE TEST EoL  = pbuf!j  UNLESS lbuf!!i    bump := 0
ELSE TEST 0    = lbuf!!i                   RESULTIS FALSE
ELSE TEST Char = pbuf!j  IF     lbuf!!i = pbuf!(j+1)
                                           bump := 1
ELSE TEST Any  = pbuf!j                    bump := 1
ELSE TEST CCl  = pbuf!j  IF     locate(lbuf!!i, j + 1)
                                           bump := 1
ELSE TEST NCCl = pbuf!j  UNLESS locate(lbuf!!i, j + 1)
                                           bump := 1
ELSE error("In omatch: can't happen")
IF 0 <= bump THEN {
 !i := !i + bump
 RESULTIS TRUE
}
RESULTIS FALSE
}

Defines:

omatch, used in chunk 18. Uses Any 5b, BoL 5b, CCl 5b, EoL 5b, error 20b, lbuf 9e, locate 19b, NCCl 5b, and pbuf 8a.

Locate character c in character class beginning at offset

19b  ⟨locate character in class 19b⟩≡  (19a)

LET locate(c, offset) = VALOF {
LET i = offset + pbuf!offset
WHILE offset < i DO {
 IF c = pbuf!i RESULTIS TRUE
 i := i - 1
}
RESULTIS FALSE
}

Defines:

locate, used in chunk 19a. Uses pbuf 8a.

Determine the size of the entry at pbuf!j and increment j accordingly.

20a  ⟨increment by pattern size 20a⟩≡  (18)

  TEST      Char    = pbuf!j   THEN j := j + 2
  ELSE TEST BoL     = pbuf!j | EoL = pbuf!j | Any = pbuf!j
                               THEN j := j + 1
  ELSE TEST CCl     = pbuf!j | NCCl = pbuf!j
                               THEN j := j + 2 + pbuf!(j+1)
  ELSE TEST Closure = pbuf!j   THEN j := j + CloSize
  ELSE error("In amatch: can't happen")
Uses amatch 18, Any 5b, BoL 5b, CCl 5b, CloSize 12c, Closure 5b, EoL 5b, error 20b,

NCCl 5b, and pbuf 8a.

7 Error reporting

Before we can print the error message we have to ensure that we’re writing to the console where it can be seen by the user. Then we can print the message and tack on a newline. Rather than terminating the program here, we bail out to the cleanup code at the end of start.

20b  ⟨error procedures 20b⟩≡  (6a)

  LET error(msg) BE {
   selectoutput(findoutput("**"))
   writes(msg)
   newline()

⟨bail out 7a⟩

  }

Defines:

error, used in chunks 7–9, 19a, and 20a.

8 Debugging

The program is functional enough for the author’s purposes. However some debugging code is still left in the program. Once written, this code looked too good to just throw away. Conditional compilation keeps the code from being compiled into the final command but still available if needed in the future. To activate, remove the two slashes at the beginning of the first line of this code fragment.

20c  ⟨debug stuff 20c⟩≡  (5a)

  //$$Debug
  $<Debug

⟨debug procedures 21b⟩

  $>Debug

8.1 The pattern buffer

When debugging it’s useful to have the pattern buffer initialized to a known state. In this case the known state is all zeros, which is also the terminator.

21a  ⟨initialize pattern buffer 21a⟩≡  (8c)

  $<Debug
   FOR c = 0 TO MaxPat DO pbuf!c := 0
  $>Debug

Uses MaxPat 12b and pbuf 8a.

This function dumps out the entire pattern buffer in hexadecimal. The buffer shouldn’t come close to being filled up in normal use, and it should be properly terminated (we initialized it to be filled with zeros). However if some errant code should plant a zero into it we want to be able to see it.

21b  ⟨debug procedures 21b⟩≡  (20c) 21c ▷

  LET DbgDumpPattBuf() BE {
   FOR i = 1 TO MaxPat DO {
    writef(" %x3", pbuf!i)
    UNLESS i REM 16 DO newline()
   }
   newline()
  }

Defines:

DbgDumpPattBuf, used in chunk 22a. Uses MaxPat 12b and pbuf 8a.

8.2 The input line

Just in case you ever suspect the weirdness is happening in the input, this procedure dumps out the input buffer in hexadecimal. This one does terminate on hitting a zero.

21c  ⟨debug procedures 21b⟩+≡  (20c) ◁ 21b

  LET DbgDumpLineBuf() BE {
   LET i = 0
   {
    i := i + 1
    writef(" %x3", lbuf!i)
    UNLESS i REM 16 DO newline()
   } REPEATWHILE lbuf!i
   newline()
  }

Defines:

DbgDumpLineBuf, used in chunk 22b. Uses lbuf 9e.

8.3 Calling the debug procedures

And we’ll provide conditional calls to these dump procedures. These fragments may be sprinkled in wherever needed.

22a ⟨dump pattern buffer 22a⟩≡

$<Debug
DbgDumpPattBuf()
$>Debug
Uses DbgDumpPattBuf 21b.

22b ⟨dump line buffer 22b⟩≡

$<Debug
DbgDumpLineBuf()
$>Debug
Uses DbgDumpLineBuf 21c.

A Index of Fragments

References are to the first definition of each fragment.

⟨* 5a⟩ ⟨a fragment label 4a⟩ ⟨add closure 13c⟩ ⟨add literal character 13b⟩ ⟨add set 14a⟩ ⟨bail out 7a⟩ ⟨close streams 10b⟩ ⟨compile pattern 8c⟩ ⟨deallocate memory 8e⟩ ⟨debug procedures 21b⟩ ⟨debug stuff 20c⟩ ⟨dump line buffer 22b⟩ ⟨dump pattern buffer 22a⟩ ⟨error procedures 20b⟩ ⟨error: no memory 8d⟩ ⟨error: usage 7g⟩ ⟨expand class 15b⟩ ⟨expand hyphen 16b⟩ ⟨find character 17a⟩ ⟨find input stream 9a⟩ ⟨get character class 15a⟩ ⟨handle possible line termination 11c⟩ ⟨i/o procedures 11a⟩ ⟨increment by pattern size 20a⟩ ⟨increment sum 4b⟩ ⟨initialize pattern buffer 21a⟩ ⟨insert closure 16a⟩ ⟨locate character in class 19b⟩ ⟨look for match 18⟩ ⟨manifests 5b⟩ ⟨map escape character 14b⟩ ⟨match single pattern 19a⟩ ⟨open output stream 9d⟩ ⟨pattern creation procedures 13a⟩ ⟨pattern matching procedures 17b⟩ ⟨prepare for bail out 6b⟩ ⟨print matching lines 10a⟩ ⟨procedure start 6a⟩ ⟨procedure start’s variables 7b⟩ ⟨process command line 7c⟩ ⟨rdargs argument 7f⟩ ⟨read and store character 11b⟩ ⟨search for matching lines 9b⟩ ⟨statics 6c⟩ ⟨store terminator 11d⟩

B Index of Identifiers

Underlined entries are their definitions. Standard library definitions are not listed here. Nor are FOR control variables and most other variables local to a procedure.

addset: 13a, 13b, \underline{14a}, 15a, 15b, 16a,

16b amatch: 17b, \underline{18}, 20a Any: \underline{5b}, 13a, 19a, 20a argv: \underline{7b}, 7c, 7d, 8c, 9a, 9d BoL: \underline{5b}, 13a, 13c, 19a, 20a CCl: \underline{5b}, 13a, 15a, 19a, 20a CClEnd: \underline{5b}, 15a, 15b CloSize: \underline{12c}, 16a, 18, 20a Closure: \underline{5b}, 13a, 13c, 16a, 18, 20a Count: \underline{12c}, 18

DbgDumpLineBuf: \underline{21c}, 22b
DbgDumpPattBuf: \underline{21b}, 22a

dodash: 15b, \underline{16b} EoL: \underline{5b}, 13a, 13c, 19a, 20a error: 7g, 8c, 8d, 9a, 9d, 19a, 20a,

\underline{20b} esc: 13b, \underline{14b}, 15b, 16b Escape: \underline{5b}, 14b, 15b fin l: 6b, \underline{6c}, 7a fin p: 6b, \underline{6c}, 7a getccl: 13a, \underline{15a} index: 16b, \underline{17a} instream: \underline{8f}, 9a, 10b invert: \underline{8b}, 8c, 10a, 13a lbuf: \underline{9e}, 9f, 10a, 11a, 11b, 11d, 12a,

17b, 18, 19a, 21c lcount: 7d, \underline{7e}, 11a, 12a locate: 19a, \underline{19b} makpat: 8c, \underline{13a} match: 10a, \underline{17b} MaxLine: 10a, \underline{10c}, 11a, 12a MaxPat: 8c, \underline{12b}, 14a, 21a, 21b NCCl: \underline{5b}, 15a, 19a, 20a NotC: \underline{5b}, 15a omatch: 18, \underline{19a} outstream: \underline{9c}, 9d, 10b pbuf: \underline{8a}, 8c, 8e, 13c, 14a, 15b, 16a, 16b, 18, 19a, 19b, 20a, 21a, 21b

PrevCl: \underline{12c}, 18

                                  readline: 10a, \underline{11a}
                                  start: \underline{6a}
                                  StartCl: \underline{12c}, 18

stclos: 13c, \underline{16a}

                                  writeline: 10a, \underline{12a}

Contents

1 Find 1 1.1 Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Escape sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Metacharacters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Character classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Literate Programs 4 2.1 The program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 The metacharacters . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 The start procedure 6 3.1 Bailing out in case of trouble . . . . . . . . . . . . . . . . . . . . 6 3.2 Processing the command line arguments . . . . . . . . . . . . . . 7 3.3 Compiling the pattern . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Opening the input stream . . . . . . . . . . . . . . . . . . . . . . 8 3.5 Searching for matching lines . . . . . . . . . . . . . . . . . . . . . 9 3.6 Closing the streams . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Input/Output 10 4.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

5 Pattern creation 12

6 Pattern matching 17

7 Error reporting 20

8 Debugging 20 8.1 The pattern buffer . . . . . . . . . . . . . . . . . . . . . . . . . . 21 8.2 The input line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 8.3 Calling the debug procedures . . . . . . . . . . . . . . . . . . . . 22

A Index of Fragments 23

B Index of Identifiers 24