This document describes the formats of the files used by the TDF linker and the linker's required behaviour. There are two file formats: the capsule format and the library format. It also describes the format of the linker information units within capsules. The capsule format is described in more detail in the TDF specification.
The structure of a TDF capsule is defined properly in the TDF specification. This section describes the basic components of the TDF format that the linker uses, and the remaining sections describe the format of a TDF capsule, a TDF library and a linker information unit in terms of these components. The basic components are:
ALIGN
TDFINT
BYTEBYTEs
are always aligned on an eight bit boundary.
TDFIDENTTDFIDENT is a sequence
of characters. It is possible to change the size of the characters,
although the current implementation will produce an error for TDFIDENT
s with character sizes other than eight bits. A TDFIDENT
is represented by two TDFINTs (the size of the characters
in bits and the number of characters in the TDFIDENT),
and a sequence of BYTEs.
UNIQUEUNIQUE is a list of TDFIDENT
s. It is represented as a
TDFINT specifying the number of TDFIDENTs
in the UNIQUE, followed by that many TDFIDENTs.
EXTERNALEXTERNAL is a mechanism
for identifying external identifiers. It is represented as a discriminating
tag, followed by a byte alignment, followed by either a TDFIDENT
or a UNIQUE. The tag is a two bit number, where one
represents a TDFIDENT, two represents a
UNIQUE, and zero and three are currently illegal. UNIQUE
s are only used as part of an EXTERNAL; TDFIDENT
s are used as entities in their own right, as well as in EXTERNAL
s.
In the following descriptions, the syntax name: type is used to specify an object in the structure. The name is used to describe the purpose of the object; the type is used to describe what the object is. A type is one of the following:
TDFINT
object.
A TDF capsule has the following structure:
magic BYTE * 4 = "TDFC"
major_version TDFINT
minor_version TDFINT
ALIGN
num_prop_names: TDFINT
prop_names: TDFIDENT * num_prop_names
num_linkable_entities: TDFINT
linkable_entities: {
name: TDFIDENT
num_capsule_scope_identifiers: TDFINT
} * num_linkable_entities
num_external_linkages: TDFINT = num_linkable_entities
external_linkages: {
num_entries: TDFINT
entries: {
capsule_scope_id: TDFINT
external_name: EXTERNAL
} * num_entries
} * num_external_linkages
num_unit_groups: TDFINT = num_prop_names
unit_groups: {
num_units: TDFINT
units: {
num_counts: TDFINT = (num_linkable_entities | 0)
counts: TDFINT * num_counts
num_link_sets: TDFINT = num_counts
link_sets: {
num_links: TDFINT
links: {
internal: TDFINT
external: TDFINT
} * num_links
} * num_link_sets
num_bytes_tdf: TDFINT
tdf: BYTE * num_bytes_tdf
} * num_units
} * num_unit_groups
The rest of this section describes the format of a capsule.
The capsule begins with a header that contains a four byte magic number (magic: "TDFC"), followed by the major (major_version) and minor (minor_version) version numbers of the TDF in the capsule. This is then followed by a byte alignment and then the the capsule body.
The first part of a capsule tells the linker how many types of unit groups there are in the capsule (num_prop_names), and what the names of these unit group types are (prop_names). There can be many unit group types, but the linker must know what they are called, and the order in which they should occur. At present the linker knows about tld, tld2, versions, tokdec, tokdef, aldef, diagtype, tagdec, diagdef, tagdef and linkinfo (this can be changed from the command line). There is nothing special about any unit group type except for the tld unit group type, which contains information that the linker uses (and the tld2 unit group type, which is obsolete, but is treated as a special case of the tld unit group type). The format of the tld unit group type is described in a later section.
The second part of the capsule tells the linker how many linkable entities it should be linking on (num_linkable_entities), the name of each linkable entity (name), and the number of identifiers of each linkable entity at capsule scope (num_capsule_scope_identifiers). Identifiers at capsule scope should be numbers from zero to one less than num_capsule_scope_identifiers. The identifier allocation may be sparse, but the linker is optimized for continuous identifier allocation.
The third part of the capsule tells the linker which external names the capsule contains for each linkable entity. For each linkable entity listed in the second part, the number of external names of that linkable entity are listed in this part (num_entries), along with each of the external names (external_name) and the corresponding capsule scope identifiers (capsule_scope_id). The ordering of the linkable entities in part three must be identical to the ordering of linkable entities in part two.
The fourth and final part of the capsule contains the unit groups
themselves. The unit groups occur in the same order as the unit group
types were listed in part one. For each unit group, there is a TDFINT
specifying the number of units in that unit group (num_units),
followed by that many units.
Each unit contains a list of counts (counts) and the number of counts in that list (num_counts), which must be either zero or the same as the number of linkable entities in the capsule (num_linkable_entities ). Each count contains the number of unit scope identifiers of the given linkable entity in the unit. If the number of counts is non-zero, then the counts must be in the same order as the linkable entity names.
After the counts come the unit scope identifier to capsule scope identifier
mapping tables. The number of these tables is specified by
num_link_sets and must be the same as the number of counts
(num_counts), which is either zero or the same as the number
of linkable entities in the capsule. There is one table for each
linkable entity (if
num_link_sets is non-zero), and each table contains num_links
pairs of TDFINTs. The internal TDFINT
is the unit scope identifier; the
external TDFINT is the capsule scope identifier.
After the mapping tables there is a length (num_bytes_tdf), and that many bytes of TDF data (tdf).
The tld unit group (if it exists in the capsule) should contain one unit only. This unit should begin with two zeroes (i.e. no counts, and no identifier mapping tables), a length (which must be correct), and a sequence of bytes.
The bytes encode information useful to the linker. The first thing
in the byte sequence of a tld unit is a TDFINT
that is the type of the unit. What follows depends upon the type.
There are currently two types that are supported: zero and one. Type
zero units contain the same information as the old tld2 units
(if a tld2 unit is read, it is treated as if it were a tld
unit that began with a type of zero; it is illegal for a capsule to
contain both a tld unit group and a tld2 unit group).
Type one units contain more information (described below), and are
what the linker writes out in the generated capsule.
A version one unit contains a sequence of TDFINTs. There
is one TDFINT for each external name in part two of the
capsule. These TDFINTs should be in the same order as
the external names were. The TDFINTs are treated as
a sequence of bits, with the following meanings:
0 = The name is used within this capsule.
1 = The name is declared within this capsule.
2 = The name is uniquely defined within this capsule. If this bit is set for a tag, then the declared bit must also be set (i.e. a declaration must exist).
3 = The name is defined in this capsule, but may have other definitions provided by other capsules. This bit may not be set for tokens. If a tag has this bit set, then the declared bit must also be set (i.e. a declaration must exist).
All of the other bits in the TDFINT are reserved. The
linker uses the information provided by this unit to check that names
do not have multiple unique definitions, and to decide whether libraries
should be consulted to provide a definition for an external name.
If a capsule contains no linker information unit group, then the external
names in that capsule will have no information, and hence these checks
will not be made. A similar situation arises when the information
for a name has no bits set.
A version zero unit contains a sequence of TDFINTs.
There is one TDFINT
for each external token name, and one TDFINT for each
external tag name. These TDFINTs should be in the same
order as the external names were (but the tokens always come before
the tags). The TDFINTs are treated as a sequence of
bits, with the same meanings as above.
A TDF library begins with a header, followed by a TDFINT,
that is the type of the library. At present only type zero libraries
are supported. The format of a type zero library is as follows:
magic: BYTE * 4 = "TDFL"
major_version: TDFINT
minor_version: TDFINT
ALIGN
type: TDFINT = 0
num_capsules: TDFINT
capsules: {
capsule_name: TDFIDENT
capsule_length: TDFINT
capsule_body: BYTE * capsule_length
} * num_capsules
num_linkable_entities: TDFINT
linkable_entities: {
linkable_entity_name: TDFIDENT
num_this_linkable_entity: TDFINT
this_linkable_entity_names: {
name: EXTERNAL
info: TDFINT
capsule: TDFINT
} * num_this_linkable_entity
} * num_linkable_entities
The library begins with a four byte magic number (magic: "TDFL"),
followed by the major (major_version) and minor (minor_version)
versions of the TDF in the library (the major version must be the
same for each capsule in the library; the minor version is the highest
of the minor version numbers of all of the the capsules contained
in the library). This is followed by a byte alignment, the type of
the library (type: 0), and the number of capsules in the library
(num_capsules), followed by that many capsules.
Each of the capsules has a name (capsule_name), and the capsule content, which consists of the length of the capsule (capsule_length ) and that many bytes (capsule_body). The capsule name is the name of the file from which the capsule was obtained when the library was built. The names of capsules within a library must all be different.
The library is terminated by the index. This contains information about where to find definitions for external names. The index begins with the number of linkable entities whose external names the library will provide definitions for (num_linkable_entities).
For each of these linkable entities, the linkable entity index begins with the name of the linkable entity (linkable_entity_name), followed by the number of external names of the linkable entity that have entries in the index (num_this_linkable_entity). This is followed by the index information for each of the names.
For each name, the index contains the name (name); a TDFINT
that provides information about the name (info) with the same
meaning as the
TDFINTs in the linker information units; and the index
of the capsule that contains the definition for the name (capsule).
The index of the first capsule is zero.
The TDF linker has four uses:
This section describes the requirements of linking capsules together. The first sub-section describes the basic linking requirements. Subsequent sub-sections detail the requirements of some more advanced features.
Before the linking process is described in detail, here is an outline of the stages of the link process:
The linker is invoked with the following inputs: a set of input capsules, a set of libraries, a set of hiding rules, a set of keeping rules, a set of renaming rules, and a set of link suppression rules.
The first thing that the linker does is to enter the renaming rules into the name hash table. The name entry lookup routines will automatically pick up the new name when a renamed name is looked up in a name table.
The next stage is to load the input capsules, and to bind them together. As part of this binding process, the capsule scope identifiers for all input capsules are mapped into a single capsule scope (to be output to the final capsule). The rules for this mapping are described below.
After binding the input capsules together, the linker tries to provide definitions for undefined names using the specified libraries. When a definition is found in a library (and it hasn't been suppressed by the link suppression rules), the capsule that contains it is loaded and bound to the input capsules as if it had been one itself.
After the library capsules have been bound in, external names are hidden according to the hiding rules, and kept according to the keeping rules. Hiding means removing an entry from the external name list of the output capsule. Keeping means forcing an entry into the list, if it would otherwise be hidden. It is illegal to hide names that have no definition.
Finally the output capsule is written to a file.
This sub-section describes the process of binding capsules together in greater detail.
The first thing that the linker does when reading a capsule is to read in the magic number, and the major and minor version numbers. Capsules with an incorrect magic number are rejected. The major version number of each capsule read in must be at least four. In addition, the major version numbers of all capsules that are read in must be the same.
After this, the linker reads the unit group type names (also called `prop names'), and checks that the they are known and that they are in the correct order. There is a default list of names built into the linker (the list specified in the TDF specification) and that should be sufficient for most uses of the linker, but it is possible to provide a new list by specifying a file containing the new list on the command line.
The next thing the linker does is to read in the linkable entity names and the capsule scope identifier limit for each linkable entity. It checks that there are no duplicate names, and creates a mapping vector for each linkable entity, to contain the mapping from the capsule scope identifiers in the capsule being read in to the capsule scope identifiers in the capsule that will be written out.
After reading the linkable entity names, the linker reads the external names for each linkable entity. For each name, it checks that its capsule scope identifier is in range, and maps that to the next available capsule scope identifier (for the same linkable entity) in the output capsule, unless a name with the same linkable entity and the same name (subject to the renaming rules) has already been read (in which case it is mapped to the same capsule scope identifier as the identical name). The linker also checks to ensure that each capsule scope identifier has no more than one external name bound to it.
The final phase of reading a capsule is to read the unit groups. For normal (i.e. not tld or tld2) unit groups, the following occurs for each unit in the unit group:
The unit scope identifier limits for each linkable entity are read and saved in the unit data structure (which is appended to the list of units in that unit group for all input capsules). When the unit is written out in the output capsule, it may be necessary to add extra unit scope identifier limits (and extra mapping tables) as other capsules may have different linkable entities, which will also need entries (they will just be zero length).
The capsule scope to unit scope identifier mapping tables are read, and the old capsule scope identifier (which is first checked to see if it is in range) is replaced by a new capsule scope identifier. This information is also saved in the unit data structure. The new capsule scope identifiers are either the ones that were allocated when reading in the external names (if the old identifier is bound to an external name), or the next free capsule scope identifier of the required linkable entity.
Finally, the unit body is read, and saved with the unit.
For tld and tld2 unit groups, the unit group count is checked to ensure that it is one, and the number of unit scope identifier limits and identifier mapping tables are checked to ensure that they are both zero. The size of the body is read (and it must be correct as this is checked after reading the unit), and then the body is read. If the unit is a tld unit, then the type is read, and the body is read depending upon the type; if the unit is a tld2 unit, then the body is read as if it where a type zero tld unit.
A type zero tld unit consists of a number of integers: one for each external token name, followed by one for each external tag name (in the same order as the external name tables, but tokens always precede tags). A type one tld unit consists of a number of integers: one for each external name (of all linkable entities), in the same order as the external name tables.
Each of the integers is interpreted as a series of bits, with the bits having the following meanings:
0 = The name is used within this capsule.All of the other bits in the integer are reserved. The linker uses the information provided by this unit to check that names do not have multiple unique definitions, and to decide whether libraries should be consulted to provide a definition for a name. If a capsule contains no linker information unit group, then the names in that capsule will have no information, and hence will not receive the extra checking or library definition.1 = The name is declared within this capsule.
2 = The name is uniquely defined within this capsule. If this bit is set for a tag, then the declared bit must also be set. It is illegal to have a name uniquely defined in more than one capsule. If this occurs, the linker will report an error.
3 = The name is defined in this capsule, but may have other definitions provided by other capsules. This bit may not be set for tokens. If a tag has this bit set, the declared bit must also be set. It is possible for a name to provide a unique definition, but still allow other non-unique definitions to be linked in from other capsules.
Renaming just requires that any occurrence of the name being renamed is treated as though it were an occurrence of the name it is being renamed to. This includes names read from library indices.
After reading in all of the specified capsules, the linker loads the libraries. The library indices are read, and checked to ensure that there is no more than one definition for any external name. If there is no unique definition, but there is a single multiple definition, then this is considered to be a definition (although this can be turned off with a command line option).
Once the libraries have been loaded, each of the external names in the bound capsules that are used, but not defined are looked up in the library index. If a definition is found (and it hasn't been suppressed) then the defining capsule is loaded from the library. This process is repeated until definitions have been found for all external names that need them (and that definitions exist for), including those that are undefined in the capsules read in from the libraries.
Hiding and keeping just require that all names which should be hidden, and are not required to be kept, are not written to the external name table of the output capsule.
The magic number is written out, followed by the major and minor version numbers. The major version number is the same as that in each of the loaded capsules. The minor version number is the largest of the minor version numbers in the loaded capsules.
The unit group type names are written out first. Only those unit groups that are non-empty are actually written out. They are written out in the order specified by the current unit group name list.
The linkable entity names are written out next, followed by their capsule scope identifier limit. Again, only those linkable entity names that are non empty (i.e. have some unit scope or capsule scope identifiers) are written out.
After the linkable entity names have been written out, the external names are written out. These are written out in an arbitrary order within their linkable entities, with the linkable entities being written out in the same order as in the linkable entity name section (which is itself arbitrary, but must be repeatable). The names are written out with their new capsule scope identifiers. External names that have been hidden must not be written out.
Finally the unit groups are written out in the same order as the unit group type names in the first section. For normal units, the old counts (plus some zero counts that may be necessary if there are new linkable entities that weren't in the unit's original capsule) are written out in the same order as the linkable entity names in section two. The counts are followed by the new capsule scope to unit scope identifier mapping tables, in the same order as the counts. Finally the old unit content is written out.
For tld unit groups, a single version one tld unit is written out containing the use information for each of the external names, in the same order that the external names were written out in.
This section describes the requirements of building TDF libraries. Here is an outline of the stages of the construction process:
The linker is invoked with the following inputs: a set of input capsules, a set of libraries, and a set of link suppression rules.
The first thing that the linker does is to load the input capsules (including all capsules that are included in any of the specified libraries), and to extract their external name information into a central index. The index is checked to ensure that there is only one definition for any given name. The capsules are read in in the same way as for linking them (this checks them for validity).
The suppression rules are applied, to ensure that no suppressed external name will end up in the index in the output library.
The library is written out. The library consists of a magic number, and the major and minor version numbers of the TDF in the library (calculated in the same way as for capsules), the type zero, followed by the number of capsules. This is followed by that many capsule name and capsule content pairs. Finally, the index is appended to the library.
The index only contains entries for linkable entities that have external names defined by the library. Only external names for which there is a definition are written into the index, although this is not a requirement (when linking, the linker will ignore index entries that don't provide a definition). Either a unique definition or a single multiple definition are considered to be definitions (although the latter can be disabled using a command line option).
Part of the TenDRA Web.
Crown
Copyright © 1998.