Home | History | Annotate | Download | only in make
History log of /src/usr.bin/make/lst.h
RevisionDateAuthorComments
 1.105  27-Apr-2024  rillig make: simplify freeing of lists
 1.104  29-Dec-2023  rillig make: unexport list memory management functions

They are only used in a single source file.

No functional change.
 1.103  03-Mar-2022  rillig make: improve comments and a parameter name

No binary change.
 1.102  15-Dec-2021  rillig make: use consistent indentation for statements and continuations

No binary change, except for line numbers in assertions in suff.c.
 1.101  15-Dec-2021  rillig make: remove redundant comments for multiple-inclusion guards
 1.100  15-Dec-2021  rillig make: mark several functions whose result must be used

Suggested by sjg, to catch more bugs like the memory leak in cond.c
1.303 from 2021-12-13.

No binary change.
 1.99  05-Dec-2021  rillig make: fix comments
 1.98  03-Apr-2021  rillig make: use C99 bool type instead of defining its own

No functional change.
 1.97  15-Mar-2021  rillig make: indent inline functions for lists

No functional change.
 1.96  01-Feb-2021  rillig make: remove unused Lst_Destroy

The code in job.c that seemed to use it is inside an '#if 0' block.
 1.95  03-Jan-2021  rillig make(1): remove anonymous union from struct ListNode

Anonymous structs and unions have been introduced in C11. The code of
make is supposed to be compatible with C90 though.

The additional members were intended to be used during an interactive
debugging session only and were thus not relevant to running the actual
code.
 1.94  30-Dec-2020  rillig make(1): format multi-line comments
 1.93  13-Dec-2020  rillig make(1): rename Vector.priv_cap to cap

There is no use case for accessing or even modifying the capacity of a
vector, therefore there is no need to hide it using the prefix "priv_".
This way, the member names are aligned between Buffer and Vector.
 1.92  04-Dec-2020  rillig make(1): inline Lst_Enqueue
 1.91  04-Dec-2020  rillig make(1): inline Vector_Done
 1.90  28-Nov-2020  rillig make(1): reduce memory allocation in Arch_ParseArchive
 1.89  28-Nov-2020  rillig make(1): reduce pointer indirection for archives
 1.88  28-Nov-2020  rillig make(1): remove pointer indirection from GNode.commands

Just to save a few memory allocations. No noticeable effect on the
performance though.
 1.87  27-Nov-2020  rillig make(1): inline Lst_ForEachUntil in meta mode

This means no more unnecessary void pointers in function signatures and
no more abstraction level at checking a single element of a list. In
most cases it is more appropriate to define a function that operates on
the list as a whole, thereby hiding implementation details like the
ListNode from the caller.
 1.86  24-Nov-2020  rillig make(1): indent list functions with tabs instead of spaces
 1.85  10-Nov-2020  rillig make(1): use consistent definition for MAKE_INLINE
 1.84  28-Oct-2020  rillig make(1): inline Vector_Get

It is simple enough that it neither bloats the code nor warrants the
extra function call.
 1.83  25-Oct-2020  rillig make(1): remove obsolete comment from lst.h
 1.82  25-Oct-2020  rillig make(1): replace PtrVector with Vector, which can contain any type
 1.81  25-Oct-2020  rillig make(1): rename type Vector to PtrVector

This allows the name Vector to be used for a more generic vector type,
which will be added soon.
 1.80  25-Oct-2020  rillig make(1): inline Lst_Copy in Make_ExpandUse
 1.79  24-Oct-2020  rillig make(1): remove unused Lst_Find and Lst_FindFrom
 1.78  23-Oct-2020  rillig make(1): remove Lst_ForEachUntilConcurrent

The remaining callers of that function don't modify the list
structurally and thus can use the simpler Lst_ForEachUntil instead.
 1.77  22-Oct-2020  rillig make(1): add Lst_ForEachUntilConcurrent

Previously, Lst_ForEachUntil allowed the list to be modified while
iterating. Almost none of the code needs this, and it's also confusing
for human readers.

None of the current unit tests makes use of this concurrent modification
right now, but that's not evidence enough. Only 72% of the code are
covered by unit tests right now, and there are lots of edge cases
(whether intended or not) that are not covered by unit tests.

Therefore, all calls to Lst_ForEachUntil were changed to
Lst_ForEachUntilConcurrent and those that were obvious were changed
back. The remaining calls probably don't need the concurrent
modification code, but that's not obvious from looking at the code.
 1.76  22-Oct-2020  rillig make(1): remove Lst_Open, Lst_Next, Lst_Close

These functions had made the Lst data type more complicated and hard to
understand than necessary. This additional complexity was not needed in
the vast majority of the cases.
 1.75  21-Oct-2020  rillig make(1): remove unused typedef LstActionProc
 1.74  19-Oct-2020  rillig make(1): inline simple Lst getters

The function call variant takes more screen space than the direct field
access. Having an abstract API is usually a good idea, in this case of
simple read-only member access it makes the code more difficult to read.

LstNode_Set has been kept as a function since it is not a read-only
accessor function.
 1.73  19-Oct-2020  rillig make(1): remove unused Lst_ForEach

All of its uses have been inlined since iterating through a linked list
is trivial. This avoids the cumbersome callback functions with void
pointer parameters, allowing the compiler to perform better type checks.
 1.72  18-Oct-2020  rillig make(1): add tags to enum types

This allows IDEs to offer better type information than "anonymous enum".
 1.71  18-Oct-2020  rillig make(1): rename Lst_Init to Lst_New

For the other types such as HashTable and Buffer, the Init function does
not allocate the memory for the structure itself, it only fills it.
 1.70  18-Oct-2020  rillig make(1): rename Stack to Vector

Both Var_Dump and GetActuallyIncludingFile access more than only the top
item of the stack, therefore it is more honest to rename the data type.
 1.69  26-Sep-2020  rillig make(1): inline and remove LstNode_Prev and LstNode_Next

These functions made the code larger than necessary. The prev and next
fields are published intentionally since navigating in a doubly-linked
list is simple to do and there is no need to wrap this in a layer of
function calls, not even syntactically. (On the execution level, the
function calls had been inlined anyway.)
 1.68  25-Sep-2020  rillig make(1): add tags to some of the unnamed structs

The tags prevent the structs from accidentally becoming compatible
types.

While here, remove a few typedefs for structs that are single-purpose,
since there is no point in abstracting from the actual representation of
these types.
 1.67  25-Sep-2020  rillig make(1): fix build on Debian 9

lst.h:92:5: error: unknown type name 'uint8_t'

It had been broken since the previous commit on 2020-09-24 08:23:29.
 1.66  24-Sep-2020  rillig make(1): make the API of the List partially public

Accessing the fields List.first, List.last, ListNode.prev, ListNode.next
and ListNode.datum in read-only mode should be more efficient than a
whole function call.

All modifications to the lists or their nodes must still happen via
function calls.

This change reduces the code size, makes the code faster to execute and
allows Lst_ForEach to be written inline without the visual overhead of
function calls.
 1.65  24-Sep-2020  rillig make(1): move documentation for MakeAddAllSrc to its correct place
 1.64  24-Sep-2020  rillig make(1): rename Lst_ForEach to Lst_ForEachUntil

Since the callback function returns a terminating condition, this is not
really a foreach loop.

Many of the calls to Lst_ForEachUntil don't make use of the terminating
condition, and several don't modify the list structurally, which means
they don't need this complicated implementation.

In a follow-up commit, Lst_ForEach will be added back with a much
simpler implementation that iterates over the list naively, without a
terminating condition and without taking the iteration state from
Lst_Open/Lst_Next/Lst_Close into account. The migration to this simpler
implementation will be done step by step since each callback function
needs to be examined closely.
 1.63  24-Sep-2020  rillig make(1): refactor add_wait_dep to not use Lst_ForEachFrom anymore

It was the last remaining use of that function outside of lst.c.

While here, clean up the code of add_wait_dep by removing unreachable
code (the GNode lists never contain NULL, only the GNode.commands lists
do that).
 1.62  22-Sep-2020  rillig make(1): use fine-grained type names for lists and their nodes

This is only intended to help the human reader. There is no additional
type safety yet.
 1.61  04-Sep-2020  rillig make(1): use a stack instead of a list for the nested include path

By using a Stack instead of a Lst, the available API is reduced to the
very few functions that are really needed for a stack. This prevents
accidental misuse (such as confusing Lst_Append with Lst_Prepend) and
clearly communicates what the expected behavior is.

A stack also needs fewer calls to bmake_malloc than an equally-sized
list, and the memory is contiguous. For the nested include path, all
this doesn't matter, but the type is so generic that it may be used in
other places as well.
 1.60  02-Sep-2020  rillig make(1): improve grouping of the Lst functions

Lst_IsEmpty does not belong in the "create and destroy" group, but in
"query information without modifying anything".

The functions named LstNode_* all belong together. They do not provide
much abstraction, but still they restrict the API and hide a few struct
fields that are only used internally by Lst_Open/Lst_Close and
Lst_ForEach.

Use consistent wording in the documentation of the functions (list,
node, datum).
 1.59  30-Aug-2020  rillig make(1): rename Lst_Datum to LstNode_Datum
 1.58  30-Aug-2020  rillig make(1): rename Lst_Memeber to Lst_FindDatum

The new name nicely aligns with Lst_Find and Lst_FindFrom.
 1.57  29-Aug-2020  rillig make(1): rename LstNode functions to match their type
 1.56  29-Aug-2020  rillig make(1): rename Lst_FindB back to Lst_Find

The migration from "comparison function" to "match function" is done,
the "B" in the names is no longer needed.
 1.55  29-Aug-2020  rillig make(1): migrate remaining Lst_Find to Lst_FindB

While here, rename SuffSuffIsSuffix to SuffSuffGetSuffix since a
function named "is" should return a boolean, not a string pointer.
 1.54  29-Aug-2020  rillig make(1): start replacing Lst_Find with Lst_FindB

Lst_Find is called with a "comparison" function that returns the integer
0 if the desired node is found. This leads to confusion since there are
so many different return value conventions for int, such as 0/1 for
mimicking false/true, -1/0 as in close(2), and the sign as in strcmp(3).
This API is much easier to understand if the "comparison" function is
not called a comparison function (since that is too close to strcmp),
but a "match" function that just returns a boolean.

In Lst_FindFromB, the node argument may be null. This deviates from the
other Lst functions, which require Lst and LstNode to generally be
non-null. In this case it is useful though to make the calling code
simpler.

In arch.c, this makes a lot of the previous documentation redundant.

In cond.c, the documentation is reduced a little bit since it had
already been cleaned up before. It also removes the strange negation
from CondFindStrMatch.

In dir.c, the documentation collapses as well.

In main.c, separating the ReadMakefile function from the callbacks for
Lst_FindB allows the former to get back its natural function signature,
with proper types and no unused parameters.

To catch any accidental mistakes during the migration from Lst_Find to
Lst_FindB, the code can be compiled with -DUSE_DOUBLE_BOOLEAN, which
will complain about incompatible function pointer types.
 1.53  28-Aug-2020  rillig make(1): remove trailing 'S' from names of Lst functions

The migration from null-passing Lst functions to argument-checking Lst
functions is completed.

There were 2 surprises: The targets list may be NULL, and in Dir_AddDir,
the path may be NULL. The latter case is especially surprising since
that function turns into an almost-nop in that case. This is another
case where probably 2 independent functions have been squeezed into a
single function. This may be improved in a follow-up commit.

All other lists were fine. They were always defined and thus didn't
need much work.
 1.52  28-Aug-2020  rillig make(1): migrate Lst_Find to Lst_FindS
 1.51  28-Aug-2020  rillig make(1): remove unused reference to Lst_Last
 1.50  28-Aug-2020  rillig make(1): migrate Lst_First to Lst_FirstS
 1.49  27-Aug-2020  rillig make(1): migrate Lst_IsEmpty to Lst_IsEmptyS
 1.48  27-Aug-2020  rillig make(1): migrate Lst_Succ to Lst_SuccS
 1.47  27-Aug-2020  rillig make(1): migrate Lst_ForEach to Lst_ForEachS

Most lists are always valid. Only the "targets" variable may be null in
some cases, probably.
 1.46  27-Aug-2020  rillig make(1): migrate remaining code from Lst_Open to Lst_OpenS
 1.45  26-Aug-2020  rillig make(1): remove header sprite.h

Make is independent of the Sprite operating system.
 1.44  26-Aug-2020  rillig make(1): add stricter variants for remaining Lst functions

In most cases the Lst functions are only called when the arguments are
indeed valid. It's not guaranteed though, therefore each function call
needs to be analyzed and converted individually.

While here, remove a few statements that were only useful when the Lst
functions handled circular lists.
 1.43  23-Aug-2020  rillig make(1): remove unused declarations from header files
 1.42  23-Aug-2020  rillig make(1): remove parameter names from function prototypes

Thanks kre for noticing.
 1.41  23-Aug-2020  rillig make(1): reverse order of the Lst_Find parameters

The other callbacks all have (function, param), only the Lst_Find had
(param, function), which was inconsistent.
 1.40  23-Aug-2020  rillig make(1): define aliases for function types in list processing

This makes the prototypes of the functions clearer.
 1.39  23-Aug-2020  rillig make(1): handle special case of a list containing null pointers

GNode.commands is the only place in make where a list can contain null
pointers. That's unexpected, and memory management in CompatRunCommand
looks suspicous enough to warrant extensive documentation.
 1.38  22-Aug-2020  rillig make(1): replace Lst_Duplicate with Lst_CopyS

Lst_Duplicate would have passed through any null pointer, which was not
needed for make. It was the last function that used Lst_AtEnd, which in
turn was the last function that used LstInsertAfter. As a result, these
two functions have been removed.
 1.37  22-Aug-2020  rillig make(1): make moving and copying lists simpler

Instead of the two-in-one Lst_Concat, having two separate functions is
easier to understand. There is no need for a long API comment anymore
since the new functions have a single purpose that is accurately
described by their name.

The long comment inside Lst_Concat has been removed since it only
repeated the exact code, only in more words.

The comments in make.c about appending the cohorts had been wrong. They
were not appended but prepended. Once more, the function name expresses
everything that the comment said, making the comment redundant. There
is no need to test whether the cohorts list is empty, doing nothing is
implied by the word All in Lst_PrependAllS.
 1.36  22-Aug-2020  rillig make(1): make Lst_Prev stricter regarding null pointers
 1.35  22-Aug-2020  rillig make(1): require argument of Lst_Member to be non-null

Since the lists don't contain null pointers, it doesn't make sense to
search for a null pointer. All calls but one already had obviously
non-null arguments. The one remaining call using targ->suff has been
guarded for now.

The code for Lst_Member became much simpler than before. Partly because
the old code had an extra condition for circular lists, which are not
used by make.
 1.34  22-Aug-2020  rillig make(1): replace Lst_Datum with non-null guaranteeing Lst_DatumS
 1.33  22-Aug-2020  rillig make(1): unexport Lst_InsertBefore and Lst_InsertAfter
 1.32  22-Aug-2020  rillig make(1): add strict argument checks for Lst_InsertBefore

As with the other modifying operations on lists, the callers already
made sure that the arguments are valid.
 1.31  22-Aug-2020  rillig make(1): convert Lst_Enqueue and Lst_Dequeue to nonnull variants

Except for once instance in parse.c, the usage pattern for Lst_Dequeue
was to first test whether the list is empty. This pattern allowed the
implementation of Lst_Dequeue to become simpler since the null check is
not needed anymore.

The calls to Lst_Enqueue never pass an invalid list or a null pointer,
therefore making them strict was trivial.
 1.30  22-Aug-2020  rillig make(1): convert remaining Lst_AtEnd to the stricter Lst_Append

The general-purpose list library that is included in make allows to call
Lst_AtEnd for invalid lists, silently ignoring this programming error.
This is a flexibility that make doesn't need.

Another unneeded "feature" is that list items can theoretically be null
pointers. This doesn't make sense as well and is therefore not needed
by make.

These programming errors are now caught early by assertions.
 1.29  22-Aug-2020  rillig make(1): make Make_HandleUse simpler

Since the function names now contain the text from the comments, the
comments can be shortened a bit.
 1.28  22-Aug-2020  rillig make(1): add Lst_Append to add an item at the end of the list

The previous variant of using a special case of Lst_InsertAfter was
unnecessarily complicated. Linked lists are a very basic data
structure, and there is no need to overcomplicate things by introducing
unnecessary conditions and branches.
 1.27  21-Aug-2020  rillig make(1): remove type information from local variables in list library

Every node in this file is of type LstNode, which makes the 'l' in the
name 'ln' redundant. The name 'ln' is quite close to the name 'l',
which in turn can easily be confused with the digit '1'. Therefore,
rename 'l' to 'list' and 'ln' to 'node'.
 1.26  21-Aug-2020  rillig make(1): use stricter list API for sequential access

In several places, it just doesn't make sense to have a null pointer
when a list is expected.

In the existing unit tests, the list passed to Lst_Open is always valid,
but that's not a guarantee for real-world usage. Therefore, Lst_Open
has been left for now, and Lst_OpenS is only the preferred alternative
to it.
 1.25  21-Aug-2020  rillig make(1): assert correct usage of the Lst_Open API

All calls to Lst_Next are properly protected by Lst_Open, so there is no
possible assertion failure here.
 1.24  21-Aug-2020  rillig make(1): make list library code stricter

Up to now, the list library didn't distinguish between programming
mistakes (violations of invariants, illegal parameter values) and
actually interesting situations like "element not found in list".

The current code contains many branches for conditions that are neither
exercised by the unit tests nor by real-world usage. There is no point
in keeping this unnecessary code.

The list functions will be migrated from their lenient variants to the
stricter variants in small parts, each function getting the S suffix
when it is made strict, to avoid any confusion about how strict a
particular function is. When all functions have been migrated, they
will be renamed back to their original names.

While here, the comments of the functions are cleaned up since they
mention irrelevant implementation details in the API comments, as well
as "side effects" that are really main effects.
 1.23  21-Aug-2020  rillig make(1): properly clean up the remaining code mentioning circular lists
 1.22  21-Aug-2020  rillig make(1): remove unused code for circular lists

The list library had probably been imported from a general-purpose
library that also supported circular lists. These are not used by make
though.

After replacing Lst_Init(FALSE) with Lst_Init(), only a single call to
Lst_Init remained with a non-constant argument, and that was in
Lst_Concat, which was to be expected.
 1.21  13-Aug-2020  rillig make(1): follow naming conventions for multiple-inclusion guards

This avoids undefined behavior.
 1.20  07-Sep-2014  joerg Revert all make changes except the unit tests to the state of three
weeks ago. Individual changes can be reapplied after review.
 1.19  23-Aug-2014  christos PR/46096: Jarmo Jaakkola: fix many problems with dependencies (PR 49086)

Quite extensive rewrite of the Suff module. Some ripple effects into
Parse and Targ modules too.

Dependency searches in general were made to honor explicit rules so
implicit and explicit sources are no longer applied on targets that
do not invoke a transformation rule.

Archive member dependency search was rewritten. Explicit rules now
work properly and $(.TARGET) is set correctly. POSIX semantics for
lib(member.o) and .s1.a rules are supported.

.SUFFIXES list maintenance was rewritten so that scanning of existing
rules works when suffixes are added and that clearing the suffix list
removes single suffix rules too. Transformation rule nodes are now
mixed with regular nodes so they are available as regular targets too
if needed (especially after the known suffixes are cleared).

The .NULL target was documented in the manual page, especially to
warn against using it when a single suffix rule would work.
A deprecation warning was also added to the manual and make also
warns the user if it encounters .NULL.

Search for suffix rules no longer allows the explicit dependencies
to override the selected transformation rule. A check is made in
the search that the transformation that would be tried does not
already exist in the chain. This prevents getting stuck in an infinite
loop under specific circumstances. Local variables are now set
before node's children are expanded so dynamic sources work in
multi-stage transformations. Make_HandleUse() no longer expands
the added children for transformation nodes, preventing triple
expansion and allowing the Suff module to properly postpone their
expansion until proper values are set for the local variables.

Directory prefix is no longer removed from $(.PREFIX) if the target
is found via directory search.

The last rule defined is now used instead of the first one (POSIX
requirement) in case a rule is defined multiple times. Everything
defined in the first instance is undone, but things added "globally"
are honored. To implement this, each node tracks attribute bits
which have been set by special targets (global) instead of special
sources (local). They also track dependencies that were added by
a rule with commands (local) instead of rule with no commands (global).

New attribute, OP_FROM_SYS_MK is introduced. It is set on all targets
found in system makefiles so that they are not eligible to become
the main target. We cannot just set OP_NOTMAIN because it is one of
the attributes inherited from transformation and .USE rules and would
make any eligible target that uses a built-in inference rule ineligible.

The $(.IMPSRC) local variable now works like in gmake: it is set to
the first prerequisite for explicit rules. For implicit rules it
is still the implied source.

The manual page is improved regarding the fixed features. Test cases
for the fixed problems are added.

Other improvements in the Suff module include:
- better debug messages for transformation rule search (length of
the chain is now visualized by indentation)
- Suff structures are created, destroyed and moved around by a set
of maintenance functions so their reference counts are easier
to track (this also gets rid of a lot of code duplication)
- some unreasonably long functions were split into smaller ones
- many local variables had their names changed to describe their
purpose instead of their type
 1.18  23-Jan-2009  dsl Sprinkle some const.
In particular for Lst_Find() and Lst_FindFrom().
Remove some unneeded casts and some now-undeeded UNCONST().
 1.17  23-Jan-2009  dsl Change 'ClientData' to 'void *' so that relevant parameters can
be made 'const void *'.
 1.16  13-Dec-2008  dsl Use NULL instead of -1 cast to the relavant type (usually via NIL).
This was a suggestion from christos - so blame him if there is a deep
reason for using -1 :-)
 1.15  11-Nov-2006  dsl Return the non-zero value that caused the Lst_ForEach[From] call to
terminate early to the caller.
 1.14  27-Oct-2006  dsl Rename 'struct Lst' to 'struct List' and 'struct LstNode' to 'struct 'ListNode'
in lst.d remove a small barrowload of casts from the lst.lib bloatset.
 1.13  25-Oct-2006  dsl Rename Lst_Append() to Lst_InsertAfter() and Lst_Insert() to Lst_InsertBefore()
to better explain their actions.
 1.12  25-Oct-2006  dsl Fix previous - need to add a lstPrev()
 1.11  09-Aug-2005  christos Add typedefs for DuplicateProc and FreeProc from Max Okumoto.
 1.10  07-Aug-2003  agc Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22365, verified by myself.
 1.9  15-Jun-2002  wiz Remove !__STDC__ stuff, de-__P(), ANSIfy, and de-register.
 1.8  29-Jul-1999  hubertf sprite.h is private to make, so #include it with "sprite.h",
not <sprite.h>.

Problem reported in PR 4381 bye Soren S. Jorvang <soren@t.dk>
 1.7  06-Nov-1996  christos - Merge in FreeBSD and Lite2 changes.
- Fix bug where a non-archive target with a .a suffix would always
be considered to be out of date, since it does not have a TOC.
 1.6  04-Feb-1996  christos branches: 1.6.4;
fix pr/1421 and pr/1997
 1.5  14-Jun-1995  christos - $NetBSD$ rcsids
- Fixed so that .[A-Z]* targets that do not match keywords are ignored as
Posix mandates
- Added .PHONY target keyword
 1.4  06-Jun-1994  jtc Fixes from Christos Zoulas, who used purify, objectcenter and testcenter
to find memory leaks and illegal memory accesses.
 1.3  05-Mar-1994  cgd fixes/improvements from Christos Zoulas <christos@deshaw.com>.
 1.2  01-Aug-1993  mycroft Add RCS identifiers.
 1.1  21-Mar-1993  cgd branches: 1.1.1;
Initial revision
 1.1.1.2  28-Dec-1996  tls Import 4.4BSD-Lite2 sources onto CSRG branch (already merged at head)
 1.1.1.1  21-Mar-1993  cgd initial import of 386bsd-0.1 sources
 1.6.4.1  26-Jan-1997  rat Update make(1) from trunk, by request from Christos Zoulas. Fixes many bugs.

RSS XML Feed