Q:

How to ensure `make` rebuilds all objects after deletion of a file

Consider the following Makefile skeleton:
HEADERS := $(shell find . -name "*.h" | sort)
SOURCES := $(shell find . -name "*.c" | sort)
OBJECTS := $(patsubst %.c, %.o, $(SOURCES))

executable: $(OBJECTS)
    $(CC) $(CFLAGS) -o $@ $(OBJECTS)

%.o: %.c
    rm -f $@
    $(CC) $(CFLAGS) -c -o $@ $< || { rm -f $@; exit 1; }

$(OBJECTS): Makefile $(HEADERS)

These rules ensure that OBJECTS and executable are recompiled if any of the following files is modified:

Declaration files (*.h)
Implementation files (*.c)
The Makefile itself

This works very nicely. It also covers the case of adding a new source code file to a directory of the project (assuming the new file wasn't added using cp -a or mv). The case that isn't covered is the deletion of a file.
Recompilation on deletion is useful because it catches leftovers in the remaining source code and because it removes superfluous data from the executable.
What is a succinct and efficient way of ensuring the make command rebuilds all objects after a source code file is deleted from the project?
The answer can use any common Linux command via $(shell ...).

A:

The reply provided by MadScientist is very good (particularly regarting the use of a modern auto-generated dependencies method).
If the modern auto-generated dependencies method is not an option, an alternative to using echo and cmp would be to have the dependencies handled by make, using include and $(file ...) (note the extra dependency for $(OBJECTS)):
HEADERS := $(shell find . -name "*.h" | sort)
SOURCES := $(shell find . -name "*.c" | sort)
OBJECTS := $(patsubst %.c, %.o, $(SOURCES))

executable: $(OBJECTS)
    $(CC) $(CFLAGS) -o $@ $(OBJECTS)

%.o: %.c
    rm -f $@
    $(CC) $(CFLAGS) -c -o $@ $< || { rm -f $@; exit 1; }

$(OBJECTS): Makefile $(HEADERS) deps.mk

include deps.mk

deps.mk: $(HEADERS) $(SOURCES)
    $(file >$@,$@: $(HEADERS) $(SOURCES))
    $(file >>$@,$(HEADERS) $(SOURCES):)

That is only one example and any combination of behavior is possible. For instance if your requirements were:

recompile everything when 

a header file is created or modified; or
a header or source file is deleted

otherwise, recompile only the added or modified source files - if any

you could capture the list of deleted files in a MISSING using the filter-out function:
HEADERS := $(shell find . -name "*.h" | sort)
SOURCES := $(shell find . -name "*.c" | sort)
OBJECTS := $(patsubst %.c, %.o, $(SOURCES))

executable: $(OBJECTS)
    $(CC) $(CFLAGS) -o $@ $(OBJECTS)

%.o: %.c
    rm -f $@
    $(CC) $(CFLAGS) -c -o $@ $< || { rm -f $@; exit 1; }

include missing.mk
ifneq (,$(MISSING))
$(MISSING):
endif

$(OBJECTS): Makefile $(HEADERS) $(MISSING)

missing.mk: $(MISSING) $(HEADERS) $(SOURCES)
    $(file >$@,MISSING=$$(filter-out $$(HEADERS) $$(SOURCES),$(HEADERS) $(SOURCES)))

