Copyright (c) 2000 Rich Miller. This material may be distributed only subject to the terms and conditions set forth in the Software Carpentry Open Publication License, which is available at: http://www.software-carpentry.com/openpub-license.html

Contents

Introduction and Overview

Dependency Graph

Node Processing

Dependency Scanning

Component Building

Determining What Was Done

Miscellaneous

Introduction and Overview

Introduction

Make is a powerful, much-used program for performing full and incremental builds in systems of files connected by dependency relationships. It has been (re)implemented numerous times, and is available on most platforms. Unfortunately, it has a well-deserved reputation for being arcane, and inadequate in environments with complex build requirements. Make processes makefiles containing a description of a system's components, dependency relationships, and the commands used to build those components. These are described declaratively (unordered), which was a great innovation; but the makefile language is itself declarative rather than procedural, which directly contributes to the difficulty of using make. Most make implementations support the same language, partly to maintain compatibility with existing makefiles. While some have extended the language to increase its power, all implementations known to this author are quite limited in language power and expressiveness when compared with a modern scripting language like Perl or Python.

PyMake is designed to be a strong marriage of make functionality with a powerful and modern scripting language, Python. This "strong marriage" designates the fact that PyMake offers all the declarative processing features of a powerful make engine (more generally, a dependency graph evaluation system) coupled with all the processing power of a rich, modern procedural (and object-oriented) language. These two aspects of PyMake are fully available, with neither handicapped to support the other.

Background

Much of the design described here has been implemented in Perl in a predecessor of PyMake.  This program, PerlMake, has been in production use at IDX Systems Corp. for the past year, where it is used under the Tandem Guardian operating system to build a large (20,000 to 30,000 nodes and nearly 100,000 dependency relationships), highly complex software system. PerlMake was designed to facilitate solving essential problems encountered in this environment, in many cases going well beyond the capabilities of traditional make. More than half the nodes in the dependency graph represent non-file objects (usually, timestamped records in a DBMS). For development purposes, full simulations of Tandem builds are performed under Linux, since the latter provides a much richer and faster development environment than the Tandem.

Terminology

The make engine works on a dependency graph. Each node in the graph represents a component (for example, a file, database object, or process). Each node has a unique name. A node can have zero or more ancestors and/or descendents; for example, a source file is the descendent of any header files it includes, and is the ancestor of the object file compiled from it. If a node has any ancestor that has changed since the node (or its component) was last built, we say that this change triggers a new build of that component, and that the node must be executed. The ancestor tree of a node is the tree consisting of all direct and indirect ancestors of that node. If a node is in its own ancestor tree, we have a cycle. The dependency graph is transitive, with triggering information "flowing down" through the graph. A node is marked static if its component isn't changed by builds; typical examples are source code and header files.

We evaluate a node in the dependency graph to determine what work, if any, is required to make that node (and the component which it represents) up to date. All the information needed to make that decision can be obtained by examining that node and its ancestors, completely disregarding all other parts of the dependency graph. We execute a node when its evaluation indicates that its component must be (re)built.  For example, if a node represents an object file, and this is older than the source file from which it is built, then that source file must be recompiled.

Nodes are processed by backward chaining from desired targets through their ancestors. All ancestors of a node are guaranteed to have been fully evaluated by the time that node is evaluated; for example, if a node creates an executable program file from several library files, then these library files will be up to date (or the attempt to make them so will have failed) by the time they are needed for incorporation into the program file.

Overview

PyMake can perform full and incremental sequential or fully-parallelized, distributed builds of all or selected parts of an entire project. The dependency graph is both transitive and dynamic. Dependency scanning of files is automatic, integrated, and lazy (done just in time, and only if needed), as is extension of the dependency graph itself based on such information. Information obtained by scanning files, etc. is remembered from one run of PyMake to the next, for purposes of efficiency. A log file and audit trail are produced, showing what was done, why, and what happened. Output from the commands used to build components is logged, after optional filtering to reduce "fluff" and extract information affecting later parts of the build. A manifest is generated, listing all files used in the build.

A rich set of relationships in the dependency graph are provided to give clean, elegant solutions to various build problems. For example, it is possible to have an ancestor (e.g., a node representing an FTP connection to a data source) which is needed to build its descendants, but which doesn't trigger their builds.

PyMake "makefiles" are simply Python scripts, and can be developed and debugged using all the usual Python tools. PyMake is fully database, web, and internet enabled, since it has full access to Python modules supporting access to these. PyMake is highly extensible, simply by writing Python code; and writing such extensions feels like programming in a comfortable, modern language.

PyMake is backwards compatibility with existing makefiles, using a Python module to add them to the dependency graph.
 

Dependency Graph

Construction of the Dependency Graph

PyMake makefiles are ordinary Python scripts, which call Python subroutines to build the dependency graph. Typically some or all of the following routines will be defined for each component of type X (e.g., a Cobol source file):
 

addX()	add one or more components of type X , and (typically) the object file compiled from each of them, to the dependency graph and to the all-X pseudotarget
scanX()	scan an object of type X for dependency information
compX()	construct a compilation command for an object of type X
filterX()	filter the output of the build command for a node of type X

 
A prominent omission from user-level makefiles is any information that will be derived from source files via scanning, as PyMake collects this automatically.

Example PyMake File

Here's a reasonable translation of the MickeyMake example makefile into PyMake, assuming that appropriate routines have been defined, with extensive in-line comments:

  load pymake                         # get PyMake modules
  addGlobalAttr ('DIR', 'debug')      # put generated code into 'debug' tree
  addTypeAttr ('C', 'FLAGS', '-g')    # set '-g' option for C compilation
  addLink ('cereal', \                # add executable to the dependency graph
      addC ('bran', 'raisin', 'sugar'))  # ... derived from these C sources
  doMake()                            # run the build
                                      # Note:  to remove objects, make 'kill-obj'

Dependency Graph Transitivity, Encapsulation, and Triggering

PyMake uses a transitive dependency graph, in which triggering information "flows down" from nodes to their descendents. This meshes well with the idea of encapsulation of information. Dependency scanning looks only for directly-referenced files. For example, if a program source file includes a header file, the programmer needed by concerned about whether this header file may in turn include other header files.

Triggering information, including timestamps, digital signatures, and the various node statuses, is used to determine if a node should be built. If any ancestor fail, the current node will not be built, regardless of any other triggering information. If any ancestor was successfully built, its status is set to DO, which triggers building of the current node. For timestamp-based triggering, a node's timestamp is compared to the effective timestamp of each of its direct ancestors; it is rebuilt if it is older than any of them. For digital signature-based triggering, the node is rebuilt if the cumulative digital signature of it and its direct ancestors is different from what it was the last time the node was built. Both timestamp and digital signature triggering can be used for one node, presumably for different ancestors; the node is rebuilt if either method triggers it. Finally, selected nodes may be pre-marked as "triggered", thus enabling "what-if" analyses.

Cycle Detection and Resolution

Cycles may arise in the dependency graph during its initial construction or subsequent evaluation. They are detected on the fly, and are ignored unless they exist in a part of the dependency graph that is evaluated for a desired build target. Cycles containing only static nodes (e.g. header files) are handled as if they were acyclic, with each node considered to have the others as its ancestors. Otherwise the nodes in the cycle are given status BAD.
 

Node Processing

Node Status

When evaluation of a node in the dependency graph starts, the node's status is set to "EVAL..."; when evaluation of the node completes, it is set to one of the four options below:
 

OK	node was already up to date; node's (effective) timestamp is set to the most recent timestamp of itself and its ancestor tree; node signature, if any, is set to the signature of its direct ancestors plus the node's component (file or object)
DO	node was successfully built; the node's effective timestamp and signature are set the same way as for status OK
BAD	node wasn't built, because an ancestor failed or was absent (think "bad environment, so no build attempted)
FAILED	node build was attempted, but failed

Node Type

Each node has a type attribute describing the generic class to which it belongs. This type controls how a node's name is bound, how the node's component is scanned for dependency and other information, the default method for building the component, etc. Example values might include "C", "OBJ", "EXE".

Node Evaluation

Each node in the dependency graph is completely evaluated exactly one time, if at all. The evaluation passes through several stages. Processing may be paused after a stage and resumed later, if it is blocked pending the complete evaluation of required ancestor nodes. Note that a node's full set of direct ancestor nodes can't even be identified until a node's processing starts, because the ancestor nodes may be discovered through scanning an object created by the node.

First, the node's direct ancestors are evaluated (as are their direct ancestors in turn, etc.); when this is complete, triggering information is used to determine whether the node should be built; if needed, the build is attempted; and the nodes' status and other appropriate attributes are updated as per the table above.

Node Names, Boundnames, Search Paths, and Layered Views

While the name of a node may be identical to the name of a file in the filesystem, there is no requirement that this be the case. Early in the evaluation of a node, a subroutine derives a "fully bound" filename from the "unbound" node name. This permits mapping filenames into different filesystem namespaces (e.g., for Unix, VMS, and Windows). It is also used to map filenames as found by file scanning into fully-qualified filenames (e.g., to map the unbound "stdio.h" into the bound "/usr/include/stdio.h"). Layered views can be used to support per-developer "sandboxes" built on top of a standard product build.
 

Dependency Scanning

Dependency Scanning

After a node's filename is bound, the file is scanned for dependency information, provided that a scanner exists for this node's type. Scanners are context-free where possible; for example, the C/C++ scanner captures all included header files, ignoring any preprocessor directives. This facilitates reuse of scanned information, since its the same regardless of, e.g., preprocessor definitions. In normal evaluation of the dependency graph, the node for the file is evaluated just once (if at all), inheriting attributes such as the effective timestamp of itself plus its ancestor tree, regardless of what compiler directives might be in effect in the various nodes for which it is an ancestor. Scanned information is saved from run to run of PyMake along with information used to detect whether information about a file obtained during an earlier run is still valid (e.g., whether the file's timestamp exactly matches what it was when the file was last scanned). PyMake rescans needed files unless it already knows what's in them.

Scanned dependency information is stored in a file as simple, human-readable text, to make scanners easier to validate, to make scanned information easy to absorb, and to ease integration into other tools. If this file is deleted, the next PyMake run will automatically re-scan all files whose nodes are evaluated, but this scanning will not trigger any builds. Deleting this file is the natural and appropriate way to handle changes in the dependency scanner, or corruption of the file.

Non-Existent Files

If a needed file doesn't exist, a check is done to determine whether this is ignorable; if so, the node's status is set to OK. This can arise because the brute-force scanning normally done by PyMake treats conditional includes of header files as unconditional includes, which can easily include files existing only on other platforms. Otherwise an error is reported, and the absent file's node's status is set to BAD. If the header file is actually required for compilation, the compilation will fail.
 

Component Building

Node Execution

When the decision has been made that a node needs to be built, the build command(s) are constructed. Commands specific to the node are used if defined; otherwise the type-specific routine is used (e.g., compX() for files of type X). All newly-completed jobs are read from the Job Dispatcher (see below); appropriate log file entries are made; the success or failure of the command is determined (this may be complex - for example, certain old warnings in compiler output may be allowed, but all new or different warnings rejected); and nodes blocked on this node and the Run Queue are adjusted accordingly. Finally, the newly-generated commands are handed to the Job Dispatcher for execution.

Job Dispatcher

The commands required to build a node are handed to a job dispatcher, along with the node's name. The job dispatcher can safely assume that the jobs which are under its control at any given time can be executed in any order. It is responsible for running them on some available machine or processor, then returning any generated output, the process completion code, and the time between issuing the command and its completion, and the node name. Since the job dispatcher processes and returns text, it is perfectly feasible to implement cross-machine or cross-operating system builds.

Parallel Builds

PyMake is single-threaded throughout, so it avoids all locking and debugging issues associated with threaded code. Node "scheduling" is similar to process scheduling in an operating system. The "Run Queue" is a list of non-blocked nodes whose evaluation is desired but not yet complete. When a node is evaluated, its declared direct ancestors are examined, and those which have not yet started evaluation are placed on the Run Queue, with the BLOCKNUM field of the node set to the count of (ancestor) nodes on which it is blocked. A list is maintained for each node of the nodes that are blocked until its evaluation is completed, at which time the BLOCKNUM field of each of these nodes is decremented, and if it becomes zero the affected node is returned to the Run Queue.  All required contextual information required for a node is associated with the node when its processing is paused, and restored when its processing is resumed.
 

Determining What Was Done

Log File

PyMake creates a log file showing what was done, why it was done, and any errors or warnings that occurred during processing. This is particularly important for testing, and for seeing that extensions to PyMake are working as they should. A command line option to PyMake controls the level of verbosity in the log. The log contains three kinds of entries, with each line starting with a specific log-id character to identify what follows:
 

"	comments from PyMake (e.g., why it thinks a node needs to be built)
!	commands issued to the job dispatcher
:	output from commands sent to the job dispatcher

 
Each logged comment or command has an incremental time value immediately following the initial log-id character, showing how much time has passed since the last such incremental time was reported. This allows quick determination of how much time each command consumed, thus provided detailed profiling information about the time taken by various build commands.

Commands are written to the log as they are posted to the job dispatcher. In verbose mode, all command output is added directly and unconditionally to the log. In normal (non-verbose) mode, output from commands is first filtered (by default, using a filter corresponding to a node's type). This filtering may override the job dispatcher's report of whether the command succeeded (e.g., to turn unexpected or disallowed compiler warnings into failures); extract information which can be used in later steps in the build; and to suppress "fluff" from the output. After filtering, no output is shown for successful commands, even if the actual command output contains warnings, provided all the warnings are classed by the filter as "acceptable and non-visible"; otherwise (for unsuccessful commands, and those whose output contains "unacceptable" or "acceptable but visible" warnings) the filtered output is added to the log.

The log file can be post-processed to give useful views of what happened in a build. A particularly useful post-processor eliminates all information about successful commands, thus highlighting any build problems. Other tools can show, e.g., which files were compiled and the commands use to do this.

Manifest of Components

The fully qualified name of every file used in a build becomes known as each node's filename is bound. This information is written to a "manifest" file, which by definition lists all of the component files in a build.

Build Statistics

Summary statistics are written to the log at the end of a PyMake run. The count of each node type is shown (for example, the number of C files), as well as the total number of nodes, giving data about the full dependency graph. The count of nodes with each status (OK, DO, BAD, and FAILED) is given, as a summary of results. Commands issued during the run are categorized, using (by default) the first word of the command line; for each category, the number of invocations is shown, and the total time consumed by these commands (as collected by the Job Dispatcher).
 

Miscellaneous

Issues and Limitations

PyMake follows Peter Miller's recommendation in "Recursive Make Considered Harmful" to treat a full project as a single, integrated build. This avoids a class of problems related to the order in which recursive makes are invoked, as well as unnecessary repetition of work. However, in a large build environment it would be useful to automatically partition a project into core routines needed for cross-directory builds, plus a collection of single-directory makefiles, so that if the core build is up to date, then single-directory builds could be done without the overhead of processing non-core makefiles from any other directory.

Only one PyMake build can be running on a project at a time. This avoids interesting problems related to synchronizing multiple simultaneous builds (or, from the perspective of any one of those builds, running in an unstable environment). This (and the whole-project nature of PyMake) have the potential to limit PyMake's ability to scale to very large projects. Traditionally, developers work around this limitation of make programs by recompiling specific files, e.g. for short-term testing, without regard to whether they incorporate obsolete ancestor files, relying on an occasional (preferably nightly) full build to fix such problems.

Some  would argue that dependency information obtained by scanning files, as well as any other information that PyMake retains from run to run, should be put into a database management system rather than PyMake's flat, human readable text files. This has not been explored in the present design, since flat text files have great advantages in understandability, ease of incorporation into other tools, ease of porting, speed when most of the file needs to be read, etc., and it is unclear what advantages would actually derive from using a DBMS.

Acknowledgments

• Kevin Thomas (Ovid Technologies, Inc.), for years of mentoring and numerous fruitful design discussions, and for kmake, an early and reasonably powerful extension of make.
• Carl Adler (IDX Systems Corp.) for serving as a sounding board as I worked through many PerlMake design issues.
• Steve Summit (independent consultant, and author and maintainer of the comp.lang.c FAQ list), for help with some of the hardest PerlMake design issues.
• IDX Systems Corp., for the opportunity to develop PerlMake.

Appendix - Responses to the Ideas

1. How are dependencies represented and detected? How easy is it for novices to use this tool on simple projects? In particular, how much effort is required to configure the tool for a "hello, world" program, or to extract specially-formatted comments from source code to create HTML documentation?

Dependencies are detected automatically where possible, e.g., by scanning source files, or by an addX() routine automatically adding a dependency of the compiled object on the source code from which it is derived. Additional dependencies can be registered by calling a routine such as addDep(). The MickeyMake rewrite in this document illustrates how little effort is required for end-users to implement simple makefiles (it's easier than with traditional make, in that dependencies which can be discovered automatically don't need to be specified by hand). Creating HTML documentation from specially-formatted comments in source code is isomorphic to compiling code (the source code is digested, and an object produced); therefore, you would write an addHtml() routine to add one or more source files to the build; a scanHtml() routine to scan such files for "include" files; and a compHtml() routine to "compile" the code (extracting the specially-formatted comments, and generating HTML documentation from them).

Compilation options can be handled in a variety of ways; for example, the compX() routine can contain conditional code, reference global variables, and reference generic attributes set for nodes of type X.

The dependency graph is constructed from scratch for each build, so makefile changes take effect automatically.

The getBoundName() routine provides a single point of control for mapping node names (and types) onto bound (fully-qualified) filenames. A single makefile can handle an entire project, spread across multiple directories. Files of any type (e.g., header files) can be located by searching an (ordered) list of locations. Object files can be mapped to arbitrary locations, e.g., subdirectories of the source directories, or completely separate build trees, either to a fixed location, or a location which depends on compilation options (e.g., "DEBUG" vs. non-debug, or "16-bit" vs. "32-bit").

To change PyMake's behavior, change the code (e.g., in compX()), or supply values to change its behavior based on pre-defined options. Several "hooks" are available to modify normal node evaluation and execution, at least one of which could be used to cause a node to be built only if and only if an arbitrary user-defined function returns TRUE (e.g., if the machine's load is sufficiently low, or it's "late enough" at night).

Yes. Timestamps are a cheap and efficient proxy for comparing before and after versions of a file to see whether it has changed since something was built from it. PyMake supports the use of both digital signatures and timestamps for determining whether a node has to be rebuilt.

Since PyMake is designed to be pure Python code (for now, at least), there is no bootstrapping problem specific to PyMake until such time as Python is modified to require PyMake in the construction of Python - arguably a questionable idea.

There is a clean partitioning of work between PyMake determining what commands need to be executed, and the job dispatcher which is responsible for issuing these commands. The job dispatcher is designed to be able to work cross-machine (even to foreign operating systems) where that is appropriate. Environments with clock synchronization problems make timestamp-based triggering unreliable and unacceptable. PyMake's digital signature dependencies can be used reliably in such environments.

Yes, by building it into the compX() routine.

The log file is highly useful for debugging the build process, including user-defined extensions to PyMake. Timing data is collected and shown for both individual commands, and for each category of command. There is no way at this time to see how much work remains to be done.

The log file shows not just what PyMake is doing, but why it's doing so.  E.g., A (with timestamp X) is being built because it is older than its ancestor B (with timestamp Y). There is no support at this time for graphical displays of any kind. A GUI front end could be added to PyMake, but this is not planned at this time.

By default, PyMake builds everything possible in the ancestor tree of the requested target(s). A runtime option ("-stop") is available to stop processing if an error occurs.

This is very easy to build in for specific classes of files. For example, we create a node called "all-obj" with type "group", and add a reference to each object node added to the dependency graph to the ancestor list of the all-obj node. This is usable as a build target, and is referenced by the corresponding "kill-obj" group node.

Yes. Global and type-specific options can be written into files associated with the build.

Yes. The simplest way to do this is to remove the file containing stored dependency information if there is reason to believe that it is out of date; this can be done as part of the build process itself. This causes PyMake to rescan source files as necessary, but will not trigger any nodes to be built.

This design doesn't consider whether these should be done. The answer to whether these can be done is "Yes". Each node type can have "initial" and "final" nodes defined. The "initial" node is evaluated the first time an object of type X must be built, and is responsible for making sure that this can be done. This might include compiling a tool,  updating it from the web, or starting a process which will be used to compile objects of type X. The "final" node cleans up for type X at the end of the build.

Zope management by SPVI

Last modified 2000/05/15 19:21:6.60516 US/Mountain