CVS log for src/usr.bin/make/lst.c

Up to [cvs.NetBSD.org] / src / usr.bin / make

Request diff between arbitrary revisions

Keyword substitution: kv
Default branch: MAIN

make: simplify freeing of lists

make: unexport list memory management functions

They are only used in a single source file.

No functional change.

make: fix memory leak in Lst_Remove (since 2020-10-23)

The code to free the list node (as opposed to the node data) was
accidentally removed in lst.c 1.83 from 2020-10-23 as part of cleaning
up an unnecessarily complicated function for traversing linked lists.

The memory leak only affected a few lists that actually used Lst_Remove.
Most lists are append-only and are freed using Lst_Done or Lst_Free at
the end, which correctly free the memory.

make: fix documentation of Lst_MoveAll

In CLEANUP mode, was originally meant to track memory allocations but is
useful during debugging as well, initialize the list.  There is no
distinct constant representing an invalid pointer, otherwise that would
have been an even better choice.

make: clean up comments

make: remove unused Lst_Destroy

The code in job.c that seemed to use it is inside an '#if 0' block.

make(1): format multi-line comments

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.

make(1): inline Lst_Enqueue

make(1): inline Vector_Done

make(1): use consistent variable names for list nodes

make(1): reduce memory allocation in suffix handling

The function Lst_MoveAll previously freed the source list.  This
function was only used in a few places, and none of them really needed
the allocation.

make(1): reduce pointer indirection for archives

make(1): remove pointer indirection from GNode.commands

Just to save a few memory allocations.  No noticeable effect on the
performance though.

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.

make(1): indent list functions with tabs instead of spaces

make(1): rename list node to ln

That's the name that is used for list nodes outside lst.c, and there is
no reason to use a different name in the implementation of lists.  Sure,
the "l" of the name "ln" is redundant, but it's still shorter than
"node", and the latter sounds too similar to GNode.

make(1): inline Vector_Get

It is simple enough that it neither bloats the code nor warrants the
extra function call.

make(1): replace PtrVector with Vector, which can contain any type

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.

make(1): inline Lst_Copy in Make_ExpandUse

make(1): remove unused Lst_Find and Lst_FindFrom

make(1): clean up comments in list functions

make(1): clean up code in lst.c

make(1): refactor LstNodeNew

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.

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.

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.

make(1): remove code for circular lists from Lst_Next

Since make does not use circular lists, they have been removed from the
list library a few weeks ago.

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.

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.

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.

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.

make(1): fix indentation

make(1): remove redundant assertions in lst.c

These pointers are dereferenced shortly after the assertion, which
reliably leads to a SIGSEGV.

make(1): normalize whitespace in source code

There is no more space tab.  Either only tabs or only spaces or tabs
followed by spaces, but not spaces followed by tabs.

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.)

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.

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.

make(1): move documentation for MakeAddAllSrc to its correct place

make(1): merge Lst_ForEachFrom into Lst_ForEachUntil

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.

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).

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.

make(1): in debug mode, reset unused stack space to NULL

make(1): clean up RCSID blocks

These blocks mostly consisted of redundant structure, following the same
#ifndef pattern over and over, with only minimal variation.

It's easier to maintain if the common structure is only written once and
encapsulated in a macro.

To avoid "defined but unused" warnings from GCC in the case where
MAKE_NATIVE is not defined, I had to add volatile.  Adding
MAKE_ATTR_UNUSED alone would not preserve the rcsid variable in the
resulting binary.

make(1): fix inconsistent code indentation

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.

make(1): fix unbalanced Lst_Open/Lst_Close in SuffFindCmds

This bug had been there since the initial import of make, on 1993-03-21.
It just never broke the build because of the missing assertion.

https://mail-index.netbsd.org/tech-toolchain/2020/08/30/msg003847.html

The error message "cd: can't cd to include" that I got when I first
applied the fix was unrelated.  It was caused by an extra directory
"include" in src/tools/compat that didn't belong there.  With that
directory removed, running "./build.sh -j8 tools" succeeds as expected.

make(1): fix comment for Lst_Destroy

make(1): rename Lst_Datum to LstNode_Datum

make(1): rename Lst_Memeber to Lst_FindDatum

The new name nicely aligns with Lst_Find and Lst_FindFrom.

make(1): rename LstNode functions to match their type

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.

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.

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.

make(1): inline LstIsValid and LstNodeIsValid

A simple null pointer comparison is easier to understand than the fuzzy
word "valid".

make(1): fix build errors for USER_CPPFLAGS=-DNDEBUG

The functions LstIsValid and LstNodeIsValid are only used in assertions.

Without the always-false assertion, Enum_ValueToString could have
returned undefined behavior.

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.

make(1): migrate Lst_Find to Lst_FindS

make(1): migrate Lst_First to Lst_FirstS

make(1): migrate Lst_IsEmpty to Lst_IsEmptyS

make(1): migrate Lst_Last to Lst_LastS

make(1): migrate Lst_Succ to Lst_SuccS

make(1): migrate Lst_ForEach to Lst_ForEachS

Most lists are always valid.  Only the "targets" variable may be null in
some cases, probably.

make(1): migrate remaining code from Lst_Open to Lst_OpenS

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.

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.

make(1): define aliases for function types in list processing

This makes the prototypes of the functions clearer.

make(1): make navigating lists in debugging mode easier

Lst is an untyped list of pointers.  During debugging, it is often
necessary to inspect the content of the list.  To do this without manual
typecasting, add a few aliases for the LstNode.datum pointer, for
inspecting GNodes and strings.

make(1): remove another piece of code for circular lists

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.

make(1): migrate Lst_AtFront to Lst_PrependS

This makes Lst_AtFront unused, as well as LstInsertBefore.

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.

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.

make(1): make Lst_Prev stricter regarding null pointers

make(1): clean up headers

Remove redundant headers that are already included by "make.h".
Make <assert.h> available to all compilation units that use "make.h".

make(1): fix indentation

#include <stdint.h> for uint8_t

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.

make(1): replace Lst_Datum with non-null guaranteeing Lst_DatumS

make(1): unexport Lst_InsertBefore and Lst_InsertAfter

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.

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.

make(1): allow the inconsistency with Lst_OpenS to be discovered

The -dL option is intended to find bugs in Makefiles and in make itself,
therefore enabling the consistency check is ok there.  Having this check
available by default increases the chances of the bug being found and
finally fixed.

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.

make(1): make Make_HandleUse simpler

Since the function names now contain the text from the comments, the
comments can be shortened a bit.

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.

make(1): rename local list functions

Since the name of LstIsValid and LstNodeIsValid now matches exactly the
comment, the comment is not needed anymore.

make(1): document the recently failed assertion in Lst_OpenS

In make, a list has a single iterator that can be used with Lst_Open,
Lst_Next and Lst_Close.  Because this is a single iterator, it doesn't
make sense to call Lst_Open twice in a row without the corresponding
Lst_Close.  Exactly this happens in jobs mode though.

make(1): revert invalid assertion

When iterating over a list, it is currently not guaranteed that the list
is marked as "!isOpen", which I had wrongly and naively assumed.

This probably means that there is some hidden bug in make, but even if
there is, this bug would be quite old already and was too small to be
detected.

Therefore, remove the assertion again, until the situation is clear and
reproduced.

make(1): clean up list handling

Lst_Init never returns NULL.  Casting postfix increment to void is
unnecessary since that is quite common.  Found a last instance of a
local variable named 'nlnode'.

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'.

make(1): use shorter field names in Lst and LstNode

In a doubly linked list, it is commonly known that the 'prev' and 'next'
fields of the nodes are pointers to other nodes, therefore this does not
need to be repeated in the variable name.

make(1): condense the API comments in the list library

Most mentioned "side effects" were either implementation details or
rather "main effects".  The wording of similar functions has been
aligned.

make(1): remove unnecessary type duplication in list implementation

Having both the interface types Lst/LstNode and the implementation types
List/ListNode does not make the code clearer, it is an unnecessary
abstraction.  Eliminating the implementation type means that some of the
local variables can be merged, which will make the code simpler than
before.

make(1): extract creation of a list node into a separate function

make(1): remove unnecessary macro PAlloc

The ptype parameter was never used, which made it redundant.  The
remaining text is so simple that it's not worth having a macro for this
purpose.  This makes it easier to read the code since the previously
implicit variable assignment is now clearly visible.

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.

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.

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.

make(1): don't use bitfields in list processing

There is no need to squeeze unrelated fields of the struct into a single
object.  A bitset with a single flag is the same as a simple boolean
variable.

make(1): properly clean up the remaining code mentioning circular lists

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.

make(1): fix inconsistent formatting in lst.c

make(1): use consistent indentation in source code

Tabs for multiples of 8, then spaces.

The usage string has been kept as-is since the spaces there are
indentional and do influence the output.

make(1): replace macros with functions

make(1): condense the list library into a single file

The list library is only used in make(1). Having it spread out over 28
files made it look more complex than it really is. In fact, it's just a
versatile generic data type like in hash.c.

Having all the list functions in a single file reduces the code size,
both by omitting the many RCS Ids and by inlining commonly used code.