This manual documents version 4.6 of the ID utilities.
An ID database is a binary file containing a list of file names, a list of tokens, and a sparse matrix indicating which tokens appear in which files.
With this database and some tools to query it (described in this
manual), many text-searching tasks become simpler and faster. For
example, you can list all files that reference a particular
#include file throughout a huge source hierarchy, search for all
the memos containing references to a project, or automatically invoke an
editor on all files containing references to some function or variable.
Anyone with a large software project to maintain, or a large set of text
files to organize, can benefit from the ID utilities.
Although the name `ID' is short for `identifier', the ID utilities handle more than just identifiers; they also treat other kinds of tokens, most notably numeric constants, and the contents of certain character strings. Thus, this manual will use the word token as a term that is inclusive of identifiers, numbers and strings.
There are several programs in the ID utilities family:
In addition, the ID utilities have historically provided several query programs which are specializations of lid:
Please report bugs to ‘bug-idutils@gnu.org’. Remember to include the version number, machine architecture, input files, and any other information needed to reproduce the bug: your input, what you expected, what you got, and why it is wrong. Diffs are welcome, but please include a description of the problem as well, since this is sometimes difficult to infer. See Bugs.
Type ./configure
Type ‘make’
Type ‘make install’ as a user with the appropriate privileges (e.g., ‘bin’ or perhaps even ‘root’).
Type ‘cd /usr/include; mkid’ to build an ID database covering all of the system header files.
Type ‘lid FILE’, then ‘gid strtok’, then ‘aid stdout’.
You have just built, installed and used the most common commands of the GNU ID utilities. If you ever need help remembering which system header files contain a particular declaration, or reference a particular symbol, you'll want to keep the ID file you built in /usr/include for later use. If your working directory is elsewhere at the time, simply provide the ‘-f /usr/include’ option to lid (see Reading options).
Certain options, and regular expression syntax, are shared by various groupings of the ID utilities. We describe these in the sections below, rather than repeating them for each program.
If no ID databases are specified either on the command line or via the ‘IDPATH’ environment variable, then the ID utilities search for a file named ID in the current working directory, and then in successive parent directories.
The programs mkid and xtokid accept the names of files and directories on the command line. Files are scanned if there is a scanner available and enabled for the file's source language. Directories are recursively descended, searching for files whose names match the rules listed in the language map file (see Language map).
The following option controls the file tree walker:
The programs lid and fnid can print lists of file names as the result of queries. The following option controls how these lists are formatted:
The style of ‘braces’ means that file names with common directory prefix and common suffix are printed using the shell's brace notation in order to compress the output. For example, ../src/foo.c ../src/bar.c can be printed in brace notation as ../src/{foo,bar}.c.
The styles of ‘space’ and ‘newline’ mean that file names are separated spaces or by newlines, respectively.
If the list of files is being printed on a terminal, brace notation is the default. If not, file names are separated by spaces if the key is included in the output, and by newlines the key style is ‘none’ (see lid invocation).
mkid and xtokid walk file trees, select source files by name, and extract tokens from source files. They accept the following options:
$ mkid -l swizzle:"-x foo" -l swizzle:--coke-bottle
$ mkid --lang-option=swizzle:"-x foo" --lang-option=swizzle:--coke-bottle
Note the use of quotes when passing an option with arguments. Quoting is optional for options without arguments.
Use the ‘--help’ option to see the command-line option summary for each language.
To determine which tokens to extract from a file and store in the database, mkid calls a scanner; we say a scanner recognizes a particular language. Scanners for several languages are built-in to mkid; you can add your own scanners as well, as explained in Defining scanners.
The ID utilities determine which scanner to use for a particular file by consulting the language-map file. Scanners for several are already built-in to the ID utilities. You can see which languages have built-in scanners, and examine their language-specific options by invoking ‘mkid --help’ or ‘xtokid --help’.
The file id-lang.map, installed by default in $(prefix)/share/id-lang.map, contains rules for mapping file names to source languages. Each rule comprises three parts: a shell glob pattern, a language name, and language-specific scanner options.
The special pattern ‘**’ denotes the default source language. This is the language that's assigned to file names that don't match any other pattern.
The special pattern ‘***’ should be followed by a file name. The named file should contain more language-map rules and is included at this point.
The order in which rules are presented in a language-map file is significant. This order influences the order in which files are displayed as the result of queries. For example, the distributed language-map file places all rules for C .h files ahead of .c files, so that in general, declarations will precede definitions in query output. The same thing is done for C++ and its many different source file name extensions.
Here is a pared-down version of the id-lang.map file distributed with the ID utilities:
# Default language
** IGNORE # Although this is listed first,
# the default language pattern is
# logically matched last.
# Backup files
*~ IGNORE
*.bak IGNORE
*.bk[0-9] IGNORE
# SCCS files
[sp].* IGNORE
# list header files before code files
*.h C
*.h.in C
*.H C++
*.hh C++
*.hpp C++
*.hxx C++
# list C `meta' files next
*.l C
*.lex C
*.y C
*.yacc C
# list C code files after header files
*.c C
*.C C++
*.cc C++
*.cpp C++
*.cxx C++
# list assembly language after C
*.[sS] asm --comment=;
*.asm asm --comment=;
# [nt]roff
*.[0-9] roff
*.ms roff
*.me roff
*.mm roff
# TeX and friends
*.tex TeX
*.ltx TeX
*.texi texinfo
*.texinfo texinfo
The C scanner is the most commonly used. Files that match the glob pattern *.h, *.c, as well as yacc files that match *.y or *.yacc, and lex files that match *.l or *.lex, are processed with this scanner.
Scanner-specific options (Note, these options are presented without the required ‘-l’ or ‘--lang-option=’ prefix):
Assembly languages use a variety of commenting conventions, and allow a variety of special characters to dirty up local symbols, preventing name space conflicts with symbols defined by higher-level languages. Also, some compilation systems prepend an underscore to external symbols. The options listed below are designed to address these differences.
The plain text scanner is intended for human-language documents, or as the scanner of last resort for files that have no scanner that is more specific. It is customizable to the extent that character classes can be designated as token constituents or as token delimiters. The default token constituents are the alpha-numerics; all other characters are considered token delimiters.
The perl scanner is intended for perl-language documents. Tokens are all words, Perl Keywords are included. Comments & string declarations are ignored, as well as the documentation. It is customizable to the extent that character classes can be designated as token constituents or as token delimiters. The default token constituents are the alpha-numerics; all other characters are considered token delimiters.
Perl support has been originally written by Madhu Gogulapati. This scanner is considered experimental; please report any problems you should encounter to ‘bug-idutils@gnu.org’ .
The lisp scanner has been originally written by Edouard G. Parmelan, and after many years it was posthumously integrated with the main idutils code. It is intended for Lisp and Emacs Lisp files (.lisp, .el, .elc, .scm). No options are currently available for this scanner.
This scanner is considered experimental; please report any problems you should encounter to ‘bug-idutils@gnu.org’ .
To add a new scanner in source code, you should add a new section to the
file scanners.c. It might be easiest to clone one of the
existing scanners and modify it as necessary. For the hypothetical
language foo, you must define the functions get_token_foo,
parse_args_foo, help_me_foo, as well as the tables
long_options_foo and args_foo. If your scanner is
modeled after one of the existing scanners, you'll also need a
character-attribute table ctype_foo.
This is not a terribly difficult programming task, but it requires recompiling and installing the new version of mkid and xtokid. You should use xtokid to test the operation of the new scanner.
Once these functions and tables are ready, add function prototypes and
an entry to the languages_0 table near the beginning of the file.
Be warned that the existing scanners are built for speed, not elegance or readability. You might wish to create a new scanner that's easier to read and understand if you don't feel that speed is so important.
mkid builds an ID database. It accepts the names of files and/or directories on the command line, selects files that have an enabled scanner, then extracts and stores tokens from those files. The resulting ID database is architecture- and byte-order-independent so it can be shared among all systems.
The primary virtues of mkid are speed and high capacity. The size of the source trees it can index is limited only by available system memory. mkid's indexing algorithm is very space-efficient and exhibits excellent locality-of-reference, and so is capable of operating with a working-set size that is only half the size of its virtual address space. A typical unix-like operating system with 16 megabytes of system memory should be able to build an ID database covering approximately 12,000-14,000 source files totaling approximately 50–100 Megabytes. A 66 MHz 486 computer can build such a large ID database in approximately 10-15 minutes.
In a future release, mkid will be able to incrementally update an ID database much faster than it can build one from scratch. Until this feature becomes available, it might be a good idea to schedule a cron job to regularly update large ID databases during off-hours.
mkid writes the ID file, therefore it accepts the ‘--output’ (and ‘--file’) options as described in Writing options. mkid extracts tokens from source files, therefore it accepts the ‘--lang-map’, ‘--include’, ‘--exclude’, and ‘--lang-option’ options, as well as the language-specific scanner options, all of which are described in Extraction options. mkid walks file trees, therefore it handles file and directory names on its command line and the ‘--prune’ option as described in Walker options.
In addition, mkid accepts the following command-line options:
lid: Querying an ID Database by TokenThe lid program accepts patterns on the command line which it matches against the tokens stored in an ID database. The interpretation of a pattern is determined by the makeup of the pattern string itself, or can be overridden by command-line options. If a pattern contains regular expression meta-characters, it is used to perform a regular-expression substring search. If no such meta-characters are present, pattern is used to perform a literal word search. (By default, all searches are sensitive to alphabetic case.) If no pattern is supplied on the command line, lid lists every entry in the ID database.
lid reads the ID database, therefore it accepts the ‘--file’ option, and consults the ‘IDPATH’ environment variable, as described in Reading options. lid lists file names, therefore it accepts the ‘--separator’ option, as described in File listing options.
In addition, lid accepts the following command-line options:
$ lid --key=token '^dest.'
destaddr libsys/memcpy.c
destination libsys/regex.c
destlst libsys/rx.c
destpos libsys/rx.c
destset libsys/rx.h libsys/rx.c
$ lid --key=pattern '^dest.'
^dest. libsys/rx.h libsys/{memcpy,regex,rx}.c
$ lid --key=none '^dest.'
libsys/rx.h libsys/{memcpy,regex,rx}.c
When ‘--key’ is either ‘token’ or ‘pattern’, the first
column of output is a token or pattern, respectively. When
‘--key’ is ‘none’, neither of these is printed, and the file
name list begins immediately. The default is ‘token’.
..m. Either limit of the range may be omitted (e.g.,
..m, or n....). If the lower limit n is
omitted, it defaults to 1. If the upper limit is omitted, it
defaults in the present implementation to 65535, the maximum
value of an unsigned 16-bit integer.
Particularly useful queries are ‘lid -F1’, which helps locate
identifiers that are defined but never used, or are used but never
defined. Similarly, lid -F2 can help find functions that possess
a prototype declaration and a definition, but are never called.
Historically, the ID utilities have provided several query interfaces
which are specializations of lid (see lid invocation).
The idutils source distribution comes with a file idutils.el,
which defines a GNU Emacs interface to gid. To install it, put
idutils.el somewhere that Emacs will find it (i.e., in your
load-path) and put
(autoload 'gid "idutils" nil t)
in one of Emacs' initialization files, e.g., ~/.emacs. You will then be able to use M-x gid to run the command.
The gid function prompts you with the word around point. If you
want to search for something else, simply delete the line and type the
pattern of interest.
The function then runs the gid program in a ‘*compilation*’
buffer, so the normal next-error function can be used to visit
all the places the identifier is found (see Compilation).
eid: Invoking an Editor on Query Results
‘lid -R edit’ is an editing interface for the ID utilities that is
most commonly used with vi. Emacs users should use the interface
defined in idutils.el (see Emacs gid interface). The ID
utilities include an alias called eid, and for the sake of
brevity, we'll use this alias for the remainder of this section.
eid performs a lid-style, then asks if you wish to edit
the files. If your query yields more than one line of output, you will
be prompted after each line. This is the prompt you'll see:
Edit? [y1-9^S/nq]
You may respond with:
Here is an example:
prompt$ eid FILE \^print
FILE {ansi2knr,fid,filenames,idfile,idx,lid,misc,...}.c
Edit? [y1-9^S/nq] n
^print {ansi2knr,fid,getopt,getopt1,lid,mkid,regex,scanners}.c
Edit? [y1-9^S/nq] 2
This will start editing at getopt.c.
eid invokes the editor defined by the environment variable
‘VISUAL’. If ‘VISUAL’ is undefined, it uses the environment
variable ‘EDITOR’ instead. If ‘EDITOR’ is undefined, it
defaults to vi. It is possible for eid to pass the editor
an initial search pattern so that your cursor will immediately alight on
the token of interest. This feature is controlled by the following
environment variables:
vi, this should be ‘+/%s/’.
eid inserts this in
front of the matching token when a word-search is desired. For
vi, this should be ‘\<’.
eid inserts this in
end of the matching token when a word-search is desired. For
vi, this should be ‘\>’.
fid: Listing a file's tokensfid prints the tokens found in a given file. If two file names are passed on the command line, fid prints the tokens that are common to both files (i.e., the set intersection of the two token sets).
fid reads the ID database, therefore it accepts the ‘--file’ option, and consults the ‘IDPATH’ environment variable, as described in Reading options.
If the standard output is attached to a terminal, the printed tokens are separated by spaces. Otherwise, the tokens are printed one per line.
fnid: Looking up filenamesfnid queries the list of file names stored in the ID database. It accepts shell wildcard patterns on the command line. If no pattern is supplied, * is implied. fnid prints the file names that match the given patterns.
fnid prints file names, and as such accepts the ‘--separator’ option as described in File listing options.
For example, the command:
fnid \*.c
lists all the .c files in the database. (The ‘\’ here protects the ‘*’ from being expanded by the shell.)
gid: Token-based grepgid lists each line containing one of the specified tokens.
Running gid is equivalent to ‘lid -R grep’)
For example, the command:
gid important_variable
lists each line of each file in the database that contains that token.
xtokid accepts the names of files and/or directories on the command line, then extracts and prints a stream of tokens from those files for which it has a valid, enabled scanner. This is useful primarily for debugging new mkid scanners (see Defining scanners).
xtokid extracts tokens from source files, therefore it accepts the ‘--lang-map’, ‘--include’, ‘--exclude’, and ‘--lang-option’ options, as well as the language-specific scanner options, all of which are described in Extraction options. xtokid walks file trees, therefore it handles file and directory names on its command line and the ‘--prune’ option as described in Walker options.
The name ‘xtokid’ indicates that it is the “eXtract TOKens ID utility”.
Greg McGary conceived of the ideas behind the ID utilities when he
began working on the Unix kernel in 1984. He needed a navigation tool
to help him find his way around the expansive, unfamiliar landscape.
The first idutils-like tools were shell scripts, and produced an
ASCII database that looks much like the output of ‘lid ".*"’. It
took over an hour on a vax 11/750 to build a database for a
4.1bsd derived kernel. The first version of lid used the
unix system utility look, modified to handle very long
lines.
In 1986, Greg rewrote the shell scripts in C to improve performance.
Build times for the ID file were shortened by an order of magnitude.
The ID utilities were first posted to ‘comp.sources.unix’ in
September 1987 under the name id.
Over the next few years, several versions diverged from the original source. Tom Horsley at Harris Computer Systems Division stepped forward to take over maintenance and integrated some of the fixes from divergent versions. A first release of the renamed mkid version 2 was posted to alt.sources near the end of 1990. At that time, Tom wrote a Texinfo manual with the encouragement of the net community. (Tom especially thanks Doug Scofield and Bill Leonard whom he dragooned into helping proofread and edit—they found several problems in the initial version.) Karl Berry revamped the manual for Texinfo style, indexing, and organization in 1995.
In January 1995, Greg McGary reemerged as the primary maintainer and launched development of mkid version 3, whose primary new feature is an efficient algorithm for building databases that is linear in both time and space over the size of the input text. (The old algorithm was quadratic in space so it was incapable of handling very large source trees.) For the first time, the code was released under the GNU Public License.
In June 1996, the package was renamed again to id-utils and was
released for the first time under FSF copyright as part of the GNU
system. All programs had their command-line arguments completely
revised. The mkid and xtokid programs also gained a
file-tree walker, so that directory names can be passed on the command
line instead of the names of every individual file. Greg reorganized
and rewrote most of the Texinfo manual to reflect these changes.
In 2006, Claudio Fontana modernized the build system and the code itself,
and analyzed and integrated various pending patches. Package name had a
minor change from id-utils to idutils, to be more consistent
with the other GNU package names.
Future releases of idutils might include:
grep, so that grep can use
an ID database for hints
a cscope work-alike query interface
incremental update of the ID database.
*compilation* Emacs buffer: Emacs gid interface--ambiguous: lid invocation--comment: Assembler scanner--dtags: Perl scanner--exclude: Perl scanner--exclude: Text scanner--exclude: Extraction options--file: Writing options--file: Reading options--files0-from=FILE: Walker options--frequency: lid invocation--help: Universal options--ignore: Assembler scanner--ignore: C Cpp Java scanner--ignore-case: lid invocation--include: Perl scanner--include: Text scanner--include: Extraction options--keep: Assembler scanner--keep: C Cpp Java scanner--lang-map: Extraction options--lang-option: Extraction options--lang-option=asm:--comment: Assembler scanner--lang-option=asm:--ignore: Assembler scanner--lang-option=asm:--keep: Assembler scanner--lang-option=asm:--no-cpp: Assembler scanner--lang-option=asm:--strip-underscore: Assembler scanner--lang-option=asm:-c: Assembler scanner--lang-option=asm:-i: Assembler scanner--lang-option=asm:-k: Assembler scanner--lang-option=asm:-n: Assembler scanner--lang-option=asm:-u: Assembler scanner--lang-option=C:--ignore: C Cpp Java scanner--lang-option=C:--keep: C Cpp Java scanner--lang-option=C:--strip-underscore: C Cpp Java scanner--lang-option=C:-i: C Cpp Java scanner--lang-option=C:-k: C Cpp Java scanner--lang-option=C:-u: C Cpp Java scanner--lang-option=perl:--dtags: Perl scanner--lang-option=perl:--exclude: Perl scanner--lang-option=perl:--include: Perl scanner--lang-option=perl:-d: Perl scanner--lang-option=perl:-i: Perl scanner--lang-option=perl:-x: Perl scanner--lang-option=text:--exclude: Text scanner--lang-option=text:--include: Text scanner--lang-option=text:-i: Text scanner--lang-option=text:-x: Text scanner--literal: lid invocation--no-cpp: Assembler scanner--output: Writing options--prune: Walker options--regexp: lid invocation--result: lid invocation--separator: File listing options--statistics: mkid invocation--strip-underscore: Assembler scanner--strip-underscore: C Cpp Java scanner--substring: lid invocation--verbose: mkid invocation--version: Universal options--word: lid invocation-a: lid invocation-c: Assembler scanner-d: lid invocation-d: Perl scanner-F: lid invocation-f: Writing options-f: Reading options-i: lid invocation-i: Perl scanner-i: Text scanner-i: Assembler scanner-i: C Cpp Java scanner-i: Extraction options-k: lid invocation-k: Assembler scanner-k: C Cpp Java scanner-l: lid invocation-l: Extraction options-l asm:--comment: Assembler scanner-l asm:--dtags: Perl scanner-l asm:--ignore: Assembler scanner-l asm:--keep: Assembler scanner-l asm:--no-cpp: Assembler scanner-l asm:--strip-underscore: Assembler scanner-l asm:-c: Assembler scanner-l asm:-d: Perl scanner-l asm:-i: Assembler scanner-l asm:-k: Assembler scanner-l asm:-n: Assembler scanner-l asm:-u: Assembler scanner-l C:--ignore: C Cpp Java scanner-l C:--keep: C Cpp Java scanner-l C:--strip-underscore: C Cpp Java scanner-l C:-i: C Cpp Java scanner-l C:-k: C Cpp Java scanner-l C:-u: C Cpp Java scanner-l perl:--exclude: Perl scanner-l perl:--include: Perl scanner-l perl:-i: Perl scanner-l perl:-x: Perl scanner-l text:--exclude: Text scanner-l text:--include: Text scanner-l text:-i: Text scanner-l text:-x: Text scanner-m: Extraction options-n: Assembler scanner-o: lid invocation-o: Writing options-p: Walker options-R: lid invocation-r: lid invocation-s: lid invocation-s: mkid invocation-S: File listing options-u: Assembler scanner-u: C Cpp Java scanner-v: mkid invocation-w: lid invocation-x: lid invocation-x: Perl scanner-x: Text scanner-x: Extraction optionscron: mkid invocationcscope: Past and Futureeid: eid invocationEIDARG: eid invocationEIDLDEL: eid invocationEIDRDEL: eid invocationgid: Emacs gid interfacefid: fid invocationfnid: fnid invocationgid: gid invocationgid Emacs function: Emacs gid interfacegrep: Past and Futureidutils.el interface to Emacs: Emacs gid interfacelanguages_0: Defining scannersload-path: Emacs gid interfacelook and mkid 1: Past and Futurescanners.c: Defining scannerslid: Querying an ID Database by Token
fid: Listing a file's tokens
fnid: Looking up filenames
gid: Token-based grep