[Automake-NG] [PATCH] vars: implement make variable memoization (new function 'am__memoize')

[Stefano Lattarini]

This is a preparatory patch that introduces on-demand memoization through
the use of the new internal 'am__memoize' make function.  Rationale and a
more detailed explanation follow.

In GNU make (as well as in portable make), "recursive" variables (the
default kind, deriving from assignments like "var = value") have their
value recomputed every time they get expanded.

Most of the time, this has no actual impact on performance, since the
value of a recursive variable is usually either static:

    prefix = /usr/local

or only contains references to other recursive variables with static
values:

    datadir = ${prefix}/share

In other cases, though, the expansion of the value might require some
non-trivial calculation, or other time-costly operation:

    TESTS = $(sort LONG-LIST-OF-FILES)
    VC-VERSION = $(shell git describe)

Having such operation performed over and over again (each time the
variable is expanded) might become inefficient, sometimes intolerably
so.

"Immediate" variables (deriving from assignments like "var := value")
are better in this respect, since their definition evaluates the LHS
immediately, and only once.

But immediate variables have their drawbacks as well.

First of all, the fact that the LHS is expanded immediately means that
the definition of immediate variables is overly sensitive to ordering,
in that any variable referenced in the LHS must be completely defined
before the definition of the affected immediate variable is seen.
Ensuring this might be tricky in general, and even more so with Automake,
which performs non-trivial reordering of make variable.

Also, the LHS in an immediate variable definition is computed
unconditionally, which might be wasteful if it is the case that only
few of the immediate variables defined in the Makefile are actually
going to be used in a given make invocation.

So we'd like to go for a good middle ground solutions: implementing
memoization for recursive-evaluations variable which are expected to
be expanded often.

Apparently, this is easy to do:

    LAZY-VAR = $(override LAZY-VAR := VALUE)$(LAZY-VAR)

But alas, a bug in all the GNU make versions up to *and including* 3.82
prevents the above to working correctly in some non-uncommon situations:

  <http://lists.gnu.org/archive/html/bug-make/2012-05/msg00013.html>
  <https://savannah.gnu.org/patch/?7534>

Still, we *seem* to have founnd an implementation that works around the
above issue.  Referencing again the examples above, we would now write
something like this:

    memo/TESTS = $(sort LONG-LIST-OF-FILES)
    memo/VC-VERSION = $(shell git describe)
    $(call am__memoize, TESTS VC-VERSION)

This API is a little more verbose and clumsy than we'd like, but since
it apparently doesn't tickle the nasty bug referenced above, we'll stick
with it for the moment.

The idea of memoizing recursive variables stemmed from a suggestion
by Akim Demaille:
<http://lists.gnu.org/archive/html/automake-ng/2012-05/msg00062.html>

* lib/am/header-vars.am (am__memoize): New internal function.
(am__memoize_0): Likewise.
* t/memoize.tap: New test, checking $(am__memoize).
* t/spy-override.sh: New test, check that we can use the 'override'
directive as we do in the 'am__memoize' implementation.

Signed-off-by: Stefano Lattarini <address@hidden>
---

 This has been far more tricky than I hoped it would be :-(
 A review on this would be extremely welcome.   Otherwise, I
 will push in a couple of days if.

 Regards,
   Stefano

 lib/am/header-vars.am |   20 ++++
 t/memoize.tap         |  255 +++++++++++++++++++++++++++++++++++++++++++++++++
 t/spy-override.sh     |   51 ++++++++++
 3 files changed, 326 insertions(+)
 create mode 100755 t/memoize.tap
 create mode 100755 t/spy-override.sh

diff --git a/lib/am/header-vars.am b/lib/am/header-vars.am
index 0d73850..ae38a70 100644
--- a/lib/am/header-vars.am
+++ b/lib/am/header-vars.am
@@ -75,6 +75,26 @@ am__uniq = $(strip \
            $(am__empty), \
            $(call am__lastword,$(1)))))
 
+## Simple memoization for recursive make variables.  It is useful for
+## situations where immediate variables can't be used (due, say, to
+## ordering issues with the assignments of the referenced variables),
+## but where the value of the lazy variable is costly to calculate
+## (e.g., a $(shell ...) call with a non-trivial command line), so that
+## we can't afford to re-calculate it over and over every time the
+## variable gets expanded.  Example of usage:
+##
+##   memo/var1 = $(shell EXPENSIVE-COMMAND-LINE)
+##   memo/var2 = $(sort VERY-LONG-LIST)
+##   $(call am__memoize, var1 var2)
+##
+## This API and implementation seems to work around a bug in GNU make
+## (present up to and including 3.82) which caused our first
+## implementation attempt to fail:
+##   <http://lists.gnu.org/archive/html/bug-make/2012-05/msg00013.html>
+##   <https://savannah.gnu.org/patch/?7534>
+## So please don't change this without a very goo reason.
+am__memoize_0 = $(eval $1 = $$(eval override $1 := $$$$($2))$$($1))
+am__memoize = $(foreach am__memo_var, $1, \
+                $(call $(0)_0,$(am__memo_var),memo/$(am__memo_var)))
 
 ## Some derived variables that have been found to be useful.
 pkgdatadir = $(datadir)/@PACKAGE@
diff --git a/t/memoize.tap b/t/memoize.tap
new file mode 100755
index 0000000..516d335
--- /dev/null
+++ b/t/memoize.tap
@@ -0,0 +1,255 @@
+#! /bin/sh
+# Copyright (C) 2012 Free Software Foundation, Inc.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2, or (at your option)
+# any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Test Automake-provided memoization for make variables.
+
+am_create_testdir=empty
+. ./defs || Exit 1
+
+plan_ 12
+
+ocwd=`pwd` || fatal_ "couldn't get current working directory"
+
+cp "$am_amdir"/header-vars.am . \
+  || fatal_ "fetching makefile fragment headers-vars.am"
+
+# Filter out Automake comments and things that would need configure
+# substitutions.
+LC_ALL=C $EGREP -v '(^##|address@hidden@)' header-vars.am > defn.mk
+rm -f header-vars.am
+
+T ()
+{
+  tcount=`expr $tcount + 1`
+  mkdir $tcount.d
+  cd $tcount.d
+  echo include ../defn.mk > Makefile
+  cat >> Makefile
+  command_ok_ "$1" "$MAKE" test
+  cd ..
+}
+tcount=0
+
+#---------------------------------------------------------------------------
+
+## NOTE: Every repeated check in the recipes of the tests below is
+##       really intended!
+
+#---------------------------------------------------------------------------
+
+T "basic usage" <<'END'
+
+memo/foo = ok
+$(call am__memoize,foo)
+
+test:
+       test '$(foo)' = ok
+       test '$(foo)' = ok
+END
+
+#---------------------------------------------------------------------------
+
+T "call with extra spaces" <<'END'
+
+memo/foo = ok
+## There are extra spaces and tabs here; do not normalize them!
+$(call am__memoize,    foo             )
+
+test:
+       test '$(foo)' = ok
+       test '$(foo)' = ok
+END
+
+#---------------------------------------------------------------------------
+
+T "memoize several variables at once" <<'END'
+
+memo/foo1 = bar
+memo/foo2 = baz
+$(call am__memoize, foo1 foo2)
+
+test:
+       test '$(foo1)' = bar
+       test '$(foo2)' = baz
+END
+
+#---------------------------------------------------------------------------
+
+# $var will be 3 * 2^12 ~ 12000 characters long.
+var=foo
+for i in 1 2 3 4 5 6 7 8 9 10 11 12; do
+  var=$var$var
+done
+
+T "very long variable name" <<END
+
+memo/$var = foo
+\$(call am__memoize,$var)
+
+test:
+       test '\$($var)' = foo
+       test '\$($var)' = foo
+END
+
+#---------------------------------------------------------------------------
+
+T "on indirect recursive variable expansion" <<'END'
+
+memo/foo = $(indir)
+$(call am__memoize,foo)
+
+## This is delibrately placed after the memoize call.
+indir = zardoz
+
+test:
+       test '$(foo)' = zardoz
+       test '$(foo)' = zardoz
+END
+
+#---------------------------------------------------------------------------
+
+T "on indirect immediate variable expansion" <<'END'
+
+memo/foo = $(indir)
+$(call am__memoize,foo)
+
+## This is delibrately placed after the memoize call.
+indir := blob
+
+test:
+       test '$(foo)' = blob
+       test '$(foo)' = blob
+END
+
+#---------------------------------------------------------------------------
+
+T "on function call" <<'END'
+
+my_func = $(firstword $(sort $(1)))
+
+memo/foo = $(call my_func, 6 3 1 7)
+$(call am__memoize,foo)
+
+test:
+       test '$(foo)' = 1
+       test '$(foo)' = 1
+END
+
+#---------------------------------------------------------------------------
+
+T "out-of-order memoization should work" <<'END'
+
+$(call am__memoize,foo)
+test:
+       test '$(foo)' = ok
+       test '$(foo)' = ok
+memo/foo = ok
+END
+
+#---------------------------------------------------------------------------
+
+T "memoization actually takes place (1)" <<'END'
+
+indir := ok
+memo/foo = $(indir)
+$(call am__memoize,foo)
+expand-it := $(foo)
+override indir := ko
+
+test:
+       test '$(foo)' = ok
+       test '$(indir)' = ko
+END
+
+#---------------------------------------------------------------------------
+
+T "memoization actually takes place (2)" <<'END'
+
+memo/foo1 = $(shell test -f x && echo "+")
+memo/foo2 = $(shell test -f y || echo "-")
+$(call am__memoize,foo1)
+$(call am__memoize,foo2)
+
+test: one two
+two: one
+.PHONY: one two one-setup two-setup
+one-setup:
+       rm -f y
+       echo dummy > x
+one: one-setup
+       test -f x
+       test '$(foo1)' = '+'
+       test ! -f y
+       test '$(foo2)' = '-'
+two-setup:
+       rm -f x
+       echo dummy > y
+two: two-setup
+       test ! -f x
+       test '$(foo1)' = '+'
+       test -f y
+       test '$(foo2)' = '-'
+END
+
+#---------------------------------------------------------------------------
+
+
+T "definition on multiple lines" <<'END'
+
+memo/foo = a \
+b \
+c \
+\
+d
+$(call am__memoize,foo)
+
+test:
+       test '$(foo)' = 'a b c d'
+       test '$(foo)' = 'a b c d'
+END
+
+#---------------------------------------------------------------------------
+
+# Try memoization with variables having a very long content.  Our first
+# (unpublished) memoization implementation didn't work in that case -- it
+# triggered errors like "*** unterminated variable reference.  Stop" when
+# the content's length because big enough.
+
+line='dummy abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ='
+
+# About 1 million lines.
+echo "  $line \\" > t
+for i in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20; do
+  cat t t > t1
+  mv -f t1 t
+done
+
+(echo 'memo/list = \' && cat t && echo "  $line") > big.mk
+
+cat >> big.mk << 'END'
+$(call am__memoize,list)
+test:
+       test x'$(word  1, $(list))' = x'dummy'
+       test x'$(word  3, $(list))' = x'='
+       test x'$(word 31, $(list))' = x'dummy'
+       test x'$(word 93, $(list))' = x'='
+END
+
+T "very long variable content" < big.mk
+
+#---------------------------------------------------------------------------
+
+:
diff --git a/t/spy-override.sh b/t/spy-override.sh
new file mode 100755
index 0000000..de552e4
--- /dev/null
+++ b/t/spy-override.sh
@@ -0,0 +1,51 @@
+#! /bin/sh
+# Copyright (C) 2012 Free Software Foundation, Inc.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2, or (at your option)
+# any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Verify that use of 'override' directive to re-set a variable does
+# not cause any warning or extra output.
+
+am_create_testdir=empty
+. ./defs || Exit 1
+
+cat > Makefile <<'END'
+foo = 1
+override foo = 2
+
+bar = 3
+override bar := 4
+
+override baz = 6
+override zap := 8
+
+override zardoz += doz
+
+nihil:
+       @:
+sanity-check:
+       test '$(foo)' = 2
+       test '$(bar)' = 4
+       test '$(baz)' = 6
+       test '$(zap)' = 8
+       test '$(zardoz)' = 'zar doz'
+.PHONY: nihil sanity-check
+END
+
+$MAKE sanity-check baz=5 zap=7 zardoz=zar
+$MAKE --no-print-directory nihil >output 2>&1 \
+  && test ! -s output \
+  || { cat output; Exit 1; }
+
+:
-- 
1.7.9.5