A
string datatype is a datatype modeled on the idea of a formal string. Strings are such an important and useful datatype that they are implemented in nearly every
programming language. In some languages they are available as
primitive types and in others as
composite types. The
syntax of most high-level programming languages allows for a string, usually quoted in some way, to represent an instance of a string datatype; such a meta-string is called a
literal or
string literal.
String length Although formal strings can have an arbitrary finite length, the length of strings in real languages is often constrained to an artificial maximum. In general, there are two types of string datatypes:
fixed-length strings, which have a fixed maximum length to be determined at
compile time and which use the same amount of memory whether this maximum is needed or not, and
variable-length strings, whose length is not arbitrarily fixed and which can use varying amounts of memory depending on the actual requirements at run time (see
Memory management). Most strings in modern
programming languages are variable-length strings. Of course, even variable-length strings are limited in length by the amount of available memory. The string length can be stored as a separate integer (which may put another artificial limit on the length) or implicitly through a termination character, usually a character value with all bits zero such as in C programming language. See also "
Null-terminated" below.
Character encoding String datatypes have historically allocated one byte per character, and, although the exact character set varied by region, character encodings were similar enough that programmers could often get away with ignoring this, since characters a program treated specially (such as period and space and comma) were in the same place in all the encodings a program would encounter. These character sets were typically based on
ASCII or
EBCDIC. If text in one encoding was displayed on a system using a different encoding, text was often
mangled, though often somewhat readable and some computer users learned to read the mangled text.
Logographic languages such as
Chinese,
Japanese, and
Korean (known collectively as
CJK) need far more than 256 characters (the limit of a one 8-bit byte per-character encoding) for reasonable representation. The normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK
ideographs. Use of these with existing code led to problems with matching and cutting of strings, the severity of which depended on how the character encoding was designed. Some encodings such as the
EUC family guarantee that a byte value in the ASCII range will represent only that ASCII character, making the encoding safe for systems that use those characters as field separators. Other encodings such as
ISO-2022 and
Shift-JIS do not make such guarantees, making matching on byte codes unsafe. These encodings also were not "self-synchronizing", so that locating character boundaries required backing up to the start of a string, and pasting two strings together could result in corruption of the second string.
Unicode has simplified the picture somewhat. Most programming languages now have a datatype for Unicode strings. Unicode's preferred byte stream format
UTF-8 is designed not to have the problems described above for older multibyte encodings. UTF-8, UTF-16 and
UTF-32 require the programmer to know that the fixed-size code units are different from the "characters", the main difficulty currently is incorrectly designed APIs that attempt to hide this difference (UTF-32 does make
code points fixed-sized, but these are not "characters" due to composing codes).
Implementations Some languages, such as
C++,
Perl and
Ruby, normally allow the contents of a string to be changed after it has been created; these are termed
mutable strings. In other languages, such as
Java,
JavaScript,
Lua,
Python, and
Go, the value is fixed and a new string must be created if any alteration is to be made; these are termed
immutable strings. Some of these languages with immutable strings also provide another type that is mutable, such as Java and
.NET's , the thread-safe Java , and the
Cocoa NSMutableString. Immutability brings advantages and disadvantages: while immutable strings may require inefficiently creating many copies, they are simpler and fully
thread-safe. Strings are typically implemented as
arrays of bytes, characters, or code units, to allow fast access to individual units or substrings, including characters when they have a fixed length. A few languages such as
Haskell implement them as
linked lists instead. Many high-level languages provide strings as a primitive data type, such as
JavaScript and
PHP, while most others provide them as a composite data type, some with special language support in writing literals, for example,
Java and
C#. Some languages, such as
C,
Prolog and
Erlang, avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes. Even in programming languages having a dedicated string type, strings can usually be iterated as a sequence of character codes, like lists of integers or other values.
Representations Representations of strings depend heavily on the choice of character repertoire and the method of character encoding. Older string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the
ISO 8859 series. Modern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16. The term
byte string usually indicates a general-purpose string of bytes, rather than strings of only (readable) characters, strings of bits, or such. Byte strings often imply that bytes can take any value and any data can be stored as-is, meaning that there should be no value interpreted as a termination value. Most string implementations are very similar to variable-length
arrays with the entries storing the
character codes of corresponding characters. The principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array. This happens, for example, with UTF-8, where single codes (
UCS code points) can take anywhere from one to four bytes, and single characters can take an arbitrary number of codes. In these cases, the logical length of the string (number of characters) differs from the physical length of the array (number of bytes in use).
UTF-32 avoids the first part of the problem.
Dope vectors The length of a string can be stored in a
dope vector, separate from the storage holding the actual characters. The IBM PL/I (F) compiler used a
string dope vector (SDV) for variable-length strings and for passing string parameters. The SDV contains a current length and a maximum length, and is not adjacent to the string proper. After PL/I (F), IBM dropped the SDV in favor of length-prefixed strings.
Null-terminated The length of a string can be stored implicitly by using a special terminating character; often this is the
null character (NUL), which has all bits zero, a convention used and perpetuated by the popular
C programming language. Hence, this representation is commonly referred to as a
C string. This representation of an
n-character string takes
n + 1 space (1 for the terminator), and is thus an
implicit data structure. In terminated strings, the terminating code is not an allowable character in any string. Strings with
length field do not have this limitation and can also store arbitrary
binary data. An example of a
null-terminated string stored in a 10-byte
buffer, along with its
ASCII (or more modern
UTF-8) representation as 8-bit
hexadecimal numbers is: The length of the string in the above example, "FRANK", is 5 characters, but it occupies 6 bytes. Characters after the terminator do not form part of the representation; they may be either part of other data or just garbage. (Strings of this form are sometimes called
ASCIZ strings, after the original
assembly language directive used to declare them.)
Byte- and bit-terminated Using a special byte other than null for terminating strings has historically appeared in both hardware and software, though sometimes with a value that was also a printing character. $ was used by many assembler systems, : used by
CDC systems (this character had a value of zero), and the
ZX80 used " since this was the string delimiter in its BASIC language. Somewhat similar, "data processing" machines like the
IBM 1401 used a special
word mark bit to delimit strings at the left, where the operation would start at the right. This bit had to be clear in all other parts of the string. This meant that, while the IBM 1401 had a seven-bit word, almost no-one ever thought to use this as a feature, and override the assignment of the seventh bit to (for example) handle ASCII codes. Early microcomputer software relied upon the fact that ASCII codes do not use the high-order bit, and set it to indicate the end of a string. It must be reset to 0 prior to output.
Length-prefixed The length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value. This convention is used in many
Pascal dialects; as a consequence, some people call such a string a
Pascal string or
P-string. Storing the string length as byte limits the maximum string length to 255. To avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit
words to store the string length. When the
length field covers the
address space, strings are limited only by the
available memory. If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an
implicit data structure, taking
n +
k space, where
k is the number of characters in a word (8 for 8-bit ASCII on a 64-bit machine, 1 for 32-bit UTF-32/UCS-4 on a 32-bit machine, etc.). If the length is not bounded, encoding a length
n takes log(
n) space (see
fixed-length code), so length-prefixed strings are a
succinct data structure, encoding a string of length
n in log(
n) +
n space. In the latter case, the length-prefix field itself does not have fixed length, therefore the actual string data needs to be moved when the string grows such that the length field needs to be increased. Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:
Strings as records Many languages, including object-oriented ones, implement strings as
records with an internal structure like: public final class String { private unsigned long length; // string length private UniquePointer text; // explicit ownership // public methods... } However, since the implementation is usually
hidden, the string must be accessed and modified through member functions. text is a pointer to a dynamically allocated memory area, which might be expanded as needed. See also
string (C++).
Other representations Both character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly by
C string library functions: Strings using a length code are limited to the maximum value of the length code. Both of these limitations can be overcome by clever programming. It is possible to create data structures and functions that manipulate them that do not have the problems associated with character termination and can in principle overcome length code bounds. It is also possible to optimize the string represented using techniques from
run length encoding (replacing repeated characters by the character value and a length) and
Hamming encoding. While these representations are common, others are possible. Using
ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient. The core data structure in a
text editor is the one that manages the string (sequence of characters) that represents the current state of the file being edited. While that state could be stored in a single long consecutive array of characters, a typical text editor instead uses an alternative representation as its sequence data structure—a
gap buffer, a
linked list of lines, a
piece table, or a
rope—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.
Security concerns The differing memory layout and storage requirements of strings can affect the security of the program accessing the string data. String representations requiring a terminating character are commonly susceptible to
buffer overflow problems if the terminating character is not present, caused by a coding error or an
attacker deliberately altering the data. String representations adopting a separate length field are also susceptible if the length can be manipulated. In such cases, program code accessing the string data requires
bounds checking to ensure that it does not inadvertently access or change data outside of the string memory limits. String data is frequently obtained from user input to a program. As such, it is the responsibility of the program to validate the string to ensure that it represents the expected format. Performing
limited or no validation of user input can cause a program to be vulnerable to
code injection attacks. == Literal strings ==