.c 	Wednesday, December 5, 1984   -*- bolio -*-


.chapter "Strings"
.setq string-chapter-number chapter-number
.setq string-section-page section-page

Strings are vectors of characters which satisfy the predicate
3string-char-p* ((string-char-p-fun)).  Although the generic
sequence and array primitives operate on strings, there are two
reasons for having additional functions for strings.  For one, it is
convenient for atomic symbols to be used in place of strings;  symbols
are not coerced to strings by sequence functions, but they 2are*
for most of the string functions.  Additionally, many of the string
functions which compare characters do so independent of the character
case;  the sequence functions are generally based on the 3eql*
predicate ((eql-fun)), so are case dependent.

Eventually, the string functions will be generalized to handle
arguments which are general character sequences (that is, of type
3(vector character)*, vectors which can hold any characters, not
just those which are 3string-char-p*).  Until then, functions which
can be given character arguments which contain non-zero bits and font
attributes may not behave correctly if that is done.

.section "String Coercion"

.defun string frobozz
This is a lan{common lisp} function for doing coercion to a string.
If 2frobozz* is a string, it is returned;  if it is a symbol, its
name (3symbol-name*, (symbol-name-fun)) is returned.

For backwards compatibility with earlier versions of lan{nil}, and
compatibility with lan{lispm}, 3string* will also coerce
characters and integers to strings.  A character is converted to a
string one character long, having that character as its sole element:
the character must satisfy 3string-char-p* ((string-char-p-fun))
for this to succeed.  An integer is converted to a string like a
character, after first applying 3int-char* ((int-char-fun)),
which of course must succeed in making a character for the string
coercion to succeed.
.end_defun


.section "String Comparison"

When routines deal with boundaries within strings, there are two
different conventions applied.  Many functions take range arguments as
the lower inclusive bound and the upper exclusive bound (generally
named 2start* and 2end*).  These
arguments conveniently default to 0 and the length of the string
(typically).  As a general rule, an upper exclusive bound may be
explicitly specified as 3nil* producing behavior as if it were not
specified;  this is often necessary in order for following optional
arguments to be specified.

The other commonly used substring convention is for a starting index
and a count (generally named 2start* and 2count*) to be
specified.  (This convention is used primarily by subprimitives, and
old lan{nil} functions, not lan{common lisp} functions.)
The substring in question is that
starting at the index, and proceeding for count characters.  Having a
specified count run off the string is an error, and an explicit
specification of a count of 3nil* is not allowed.  Just about all
of the routines which still follow this subsequence convention are
low-level lan{nil} functions, in which the count is a required
argument, so the question of how it defaults if not specified should
not arise any more.  Routines using this convention sometimes
name these arguments 2skip* and 2take* rather than 2start*
and 2count*.

.defun string-equal string1 string2 &key (start1 0) (start2 0) end1 end2
This returns 3t* if the subsequence of 2string1* from
2start1* (inclusive) to 2end1* (exclusive) is equal (using
case-independent character comparison, ala 3char-equal*
((char-equal-fun))) to the subsequence of 2string2* from
2start2* (inclusive) to 2end2* (exclusive).  The subsequences
are guaranteed to be unequal if the subsequence lengths differ.

As a special upwards-compatibility hack, 3string-equal* will
accept optional position arguments instead of keyword arguments.
.end_defun

.defun string-lessp string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string-not-lessp string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string-greaterp string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string-not-greaterp string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string-not-equal string1 string2 &key (start1 0) (start2 0) end1 end2
These functions compare the specified two substrings.  If the substrings
do not satisfy the appropriate predicate, then 3nil* is returned.
Otherwise, the result is the index into 2string1* at which the
substrings were found to satisfy the test.  In other words, the distance
from 2start1* to the result is the length of the prefix of the two
substrings which is the same.  The comparisons made are independent of
case, as if made by 3char-lessp* etc.

3string-not-equal* is therefore like 3mismatch*
((mismatch-fun)).  As such, it could have been defined as
.lisp
(defun string-not-equal (string1 string2 &key (start1 0)
			 (start2 0) end1 end2)
  (mismatch (string string1) (string string2)
	    :start1 start1 :start2 start2 :end1 end1 :end2 end2
	    :test #'char-equal))
.end_lisp

As a special upwards-compatibility hack, 3string-lessp* (but
2not* the other functions) will accept its arguments positionally
rather than by-keyword.
.end_defun

.defun string= string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string/= string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string< string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string<= string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string>= string1 string2 &key (start1 0) (start2 0) end1 end2
.defun1 string> string1 string2 &key (start1 0) (start2 0) end1 end2
These functions are similar to those above, but do a case
2dependent* character comparison;  that is, they compare the
characters like 3char=* etc. ((char=-fun)), rather than
3char-equal*.  Thus, 3string=* returns 3t* or 3nil*, and
the others, if the predicate is true, return the index into
2string1* at which the strings differ.
.end_defun


.section "Extracting Characters from Strings"

.defun char string index
Returns the 2index*th character (zero-origined) of the string
2string*, as a character object.  2string* must be a string.

To modify a character within a string, one may use 3setf* on a call
to 3char*.

Because 2string* must be a string, the result of 3char* will
always satisfy 3string-char-p* ((string-char-p-fun)), with all
that that implies.
.end_defun

.defun schar simple-string index
This is like 3char* except that the string must be a simple
string.  This routine can be efficiently coded by the lan{nil}
compiler.

Like 3char*, 3schar* may be used with 3setf* to store into
the string.
.end_defun


.section "String Creation"

.defun make-string length &key :initial-element
Makes a string 2length* long.  Since no complicated array options
may be specified, this will always be a 3simple-string*.
2initial-element* must be a character which satisfies
3string-char-p*;  if it is specified, the returned string contains
that character in every element.

If 2initial-element* is 2not* supplied, the contents of the
returned string is 2undefined* by lan{common lisp}.  lan{nil},
which abhors uninitialized memory, will initialize it to zeros (which
happen to be, but may not always be, the character 3#\Null*).  If
lan{nil} were to be transported to another operating system with
different virtual memory facilities, then this could change
incompatibly.
.end_defun

.defun string-length string
Returns the length of the string 2string*.  2string* must be a
string;  it is not coerced.

For lan{common lisp}, this function is superceded by the generic
3length* function ((length-fun)).  There should be no noticeable
efficiency difference between 3length* and 3string-length*.
Of course, 3string-length* will complain if its argument is not a
string, whereas 3length* will accept any sequence, including
3nil*.
.end_defun

.defun string-upcase string &key (start 0) end
.defun1 string-downcase string &key (start 0) end
.defun1 string-capitalize string &key (start 0) end
These functions a string just like 2string*, with the specified
substring modified accordingly.  For 3string-upcase* and
3string-downcase*, the characters are changed as by
3char-upcase* and 3char-downcase* ((char-upcase-fun)).  For
3string-capitalize*, the first character of every sequence of
alphanumeric characters (see 3alphanumericp*, (alphanumericp-fun))
is capitalized (3char-upcase*), and the remainder of the sequence is
lowercasified (3char-downcase*).  Thus,
.lisp
(string-capitalize "this doesn't do what i want"
		   :start 2 :end 15)
  =>  "thIs Doesn'T Do what i want"
.end_lisp
Note that the "I" in "this" is capitalized because it is the start of
the subsequence, and the "T" in "doesn't" is because it is preceded by a
non-alphanumeric.

If no characters of the string are affected by the conversion, one may
not depend on whether the result is 2string* itself or a copy of
it;  to guarantee a copy, use 3copy-seq* and 3nstring-upcase*,
as in the above example.
chapter.)
.end_defun

.defun string-capitalize-words string &key (start 0) end
This is 2not* a lan{common lisp} function!  However, often it is
found that 3string-capitalize* does not do what is desired because
of its quaint use of 3alphanumericp*.  3string-capitalize-words*
only upper-casifies the first character of the subsequence, and those
characters preceded by whitespace characters, and lower-casifies the
rest.  Whitespace characters are normally Space, Tab, and Page, and
Return and Linefeed (one of which is equivalent to Newline).
.lisp
(string-capitalize-words "this doesn't do what i want"
		   	 :start 2 :end 15)
  =>  "thIs Doesn't Do what i want"
.end_lisp
.end_defun

.defun nstring-upcase string &key (start 0) end
.defun1 nstring-downcase string &key (start 0) end
.defun1 nstring-capitalize string &key (start 0) end
These routines destructively upper-casify, lower-casify, and capitalize
the specified substring of 2string*.
.end_defun

.defun string-trim character-bag string
.defun1 string-left-trim character-bag string
.defun1 string-right-trim character-bag string
These routines return a substring of 2string* resulting from
trimming the characters in the sequence 2character-bag* from one
or both ends of 2string*.  If no characters are trimmed, one may
not depend on whether the result is 2string* itself or a copy.
.lisp
(string-trim '(#\space #\tab) "  This is a test.  ")
  =>  "This is a test."
(string-left-trim '(#\space #\tab) "  This is a test.  ")
  =>  "This is a test.  "
.end_lisp
.end_defun

.section "More String Functions"

The functions in this section are not provided by lan{common lisp},
but are typically inherited from lan{lisp machine lisp}, and are
heavily used in lan{nil}.  That is also why they have not yet been
converted to take keyworded arguments (although some of them may be
in the future).

.defun string-append &rest strings
Returns a string which is the concatenation of all the 2strings*.
The arguments are coerced to strings using fun{string};  in this it
differs from the generic sequence function 3concatenate*
((concatenate-fun)), which will not accept symbols, but 2will*
accept sequences (of characters) other than strings.
.end_defun

.defun substring string start &optional end
Returns the substring of 2string* (coerced to a string using
fun{string}) from the index 2start* up to but not including
2end*, which defaults to the length of 2string* if 3nil* or
not specified.  If the specified subsequence is the entire string, one
may not depend on whether the returned result is 2string* itself,
or a copy;  to guarantee a copy, 3subseq* ((subseq-fun)) may be
used--however, 3subseq* neither restricts its input to strings nor
coerces symbols to strings.
.end_defun

.defun string-reverse string
.defun1 string-nreverse string
These are pretty much superceded by 3reverse* ((reverse-fun))
and 3nreverse* ((nreverse-fun)).  Note that for
3string-nreverse*, 2string* must be a real string because it
is destructively reversed;  3string-reverse* will accept a symbol
and return a string.
.end_defun

.defun string-search-char char string &optional (from 0) to
.defun1 string-reverse-search-char char string &optional from (to 0)
.defun1 string-search-not-char char string &optional (from 0) to
.defun1 string-reverse-search-not-char char string &optional from (to 0)
.end_defun

.defun string-search-set char-set string &optional (from 0) to
.defun1 string-reverse-search-set char-set string &optional from (to 0)
.defun1 string-search-not-set char-set string &optional (from 0) to
.defun1 string-reverse-search-not-set char-set string &optional from (to 0)
2char-set* is coerced into a sequence of characters:  it should be
a string, or a list or vector of objects acceptable to
fun{character} ((character-fun)).
.end_defun

.defun string-search key string &optional (from 0) to
.defun1 string-reverse-search key string &optional from (to 0)
.end_defun


.section "Implementation Subprimitives"

The routines described in this section are very fast routines
primitives which are oriented towards being open-compiled.  As such,
they perform very few niceties like argument defaulting.  The versions
available in the interpreter probably will do some error checking, but
don't count on it.  These are the stuff of which higher-level routines
are made.

.defun %string-cons length &optional fill-character
Creates a primitive string 2length* long, filled with the
character 2fill-character*.  Calls to fun{make-string} will
compile into calls to this, if possible, so one should not go out of
the way to use this.
.end_defun

All of the following routines are specializations for strings of a
larger set of subprimitives for operating on binary data structures (for
instance, 3%string-posq* is a specialization of 3si:%bytes-posq*).
All of the 2string* arguments to them 2must* be simple strings.
Additionally, any 2character* arguments will have their 2bits*
and 2font* ignored, rather than being strictly compared with
(e.g.) 3char=*.

.defun %string-posq character string index count
This searches through 2string* starting at 2index* and
proceeding for 2count* characters for the character
2character*.  If it is found, then the index at which it occurs is
returned;  otherwise 3nil* is returned.  This primitive only looks
at the 2code* attribute of 2character*, ignoring the rest.
.end_defun


.defun %string-eqv string1 string2 index1 index2 count
Returns 3t* if the substrings of 2string1* and 2string2*
defined by 2index1*, 2index2*, and 2count* are
fun{string=}--that is, the same, with case being significant.
.end_defun

.defun %string-replace destination source destination-index source-index count
This transfers 2count* characters from the simple-string
2source* to the simple string 2destination*, starting at the
given indices.
.end_defun

.defun %string-translate destination source translation-table destination-index source-index count
This is a slightly hairier version of fun{%string-replace}.  Instead
of the characters being transferred literally, the 2code* of each
character taken from the string 2source* is used as an index in
the string 2translation-table* to obtain the code to store instead.
For example, fun{string-upcase} could be defined
.lisp
(defun string-upcase (string
		      &aux (len (string-length string)))
  (%string-translate
     (make-string len) string *:character-upcase-table
     0 0 len))
.end_lisp
where var{*:character-upcase-table} has as its value a string
var{char-code-limit} long whose 2i*th character is the uppercase
version of the character with code 2i*.  Note that this definition
of 3string-upcase* is not correct if the input 2string* is not
a simple-string, and note also how this relates to how
3string-char-p* is defined.
.end_defun

String hashing in lan{nil} is ultimately performed by the CRC
instruction.
.cindex CRC instruction
.defun %string-hash string crc-table start count
This performs a hash computation on the substring of 2string*
starting at character 2start* and proceeding for 2count*
characters.  2crc-table* must be a simple bit vector 512 bits (16
lan{vax} longwords) long;  it should contain the hash polynomial for
use by the CRC instruction.  Several hash polynomial tables are
provided (they are listed below).  The hash computation is initially
3-1*;  the result is returned as a signed lan{nil} fixnum--that
is, a 32-bit word with the top two bits shifted off.  Consult the
lan{vax} architecture manual, or some other lan{dec}
documentation, to set up other hash polynomials.

For this to be properly useful for incrementally generating lan{crc}
computations, this primitive will have to be changed to somehow input
and output full 32-bit quantities;  such a primitive should be
available in some future lan{nil}.
.end_defun


.defvar *:autodin-ii-hash-polynomial
.end_defvar

.defvar *:ccitt-hash-polynomial
.end_defvar

.defvar *:crc-16-hash-polynomial
This is the one lan{nil} uses for doing 3intern* and
3sxhash* of strings.
.end_defvar

