Revert "Macros: convert to tree for speed of lookup"

This reverts commit 165acdd1ea3b7399b2279f94c881f8e366efaf71.

12 files changed, 218 insertions, 389 deletions

diff --git a/src/OS/Makefile-Base b/src/OS/Makefile-Base
index 91ab876f9..eefc02bbd 100644
--- a/src/OS/Makefile-Base
+++ b/src/OS/Makefile-Base
@@ -36,7 +36,7 @@ FE       = $(FULLECHO)
 # are set up, and finally it goes to the main Exim target.
 
 all:       utils exim
-config:    $(EDITME) checklocalmake Makefile os.c config.h version.h version.sh macro_defs.c
+config:    $(EDITME) checklocalmake Makefile os.c config.h version.h version.sh macro.c
 
 checklocalmake:
 	@if $(SHELL) $(SCRIPTS)/newer $(EDITME)-$(OSTYPE) $(EDITME) || \
@@ -135,7 +135,7 @@ OBJ_MACRO = macro_predef.o \
 	macro-manualroute.o macro-queryprogram.o macro-redirect.o \
 	macro-auth-spa.o macro-cram_md5.o macro-cyrus_sasl.o macro-dovecot.o macro-gsasl_exim.o \
 	macro-heimdal_gssapi.o macro-plaintext.o macro-spa.o macro-authtls.o \
-	macro-dkim.o macro-malware.o macro-macro.o macro-tree.o macro-signing.o
+	macro-dkim.o macro-malware.o macro-signing.o
 
 $(OBJ_MACRO):	$(MACRO_HSRC)
 
@@ -229,12 +229,6 @@ macro-dkim.o:		dkim.c
 macro-malware.o:	malware.c
 	@echo "$(CC) -DMACRO_PREDEF malware.c"
 	$(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ malware.c
-macro-macro.o:	macro.c
-	@echo "$(CC) -DMACRO_PREDEF macro.c"
-	$(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ macro.c
-macro-tree.o:	tree.c
-	@echo "$(CC) -DMACRO_PREDEF tree.c"
-	$(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ tree.c
 macro-signing.o:	pdkim/signing.c
 	@echo "$(CC) -DMACRO_PREDEF pdkim/signing.c"
 	$(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ pdkim/signing.c
@@ -243,8 +237,8 @@ macro_predef: $(OBJ_MACRO)
 	@echo "$(LNCC) -o $@"
 	$(FE)$(LNCC) -o $@ $(LFLAGS) $(OBJ_MACRO)
 
-macro_defs.c: macro_predef
-	./macro_predef > macro_defs.c
+macro.c: macro_predef
+	./macro_predef > macro.c
 
 # This target is recognized specially by GNU make. It records those targets
 # that do not correspond to files that are being built and which should
@@ -498,13 +492,14 @@ OBJ_EXPERIMENTAL = bmi_spam.o \
 OBJ_LOOKUPS = lookups/lf_quote.o lookups/lf_check_file.o lookups/lf_sqlperform.o
 
 OBJ_EXIM = acl.o base64.o child.o crypt16.o daemon.o dbfn.o debug.o deliver.o \
-        dkim.o dkim_transport.o directory.o dns.o drtables.o enq.o exim.o \
-	expand.o environment.o filter.o filtertest.o globals.o hash.o \
-        header.o host.o ip.o log.o lss.o macro.o macro_defs.o match.o moan.o \
+        directory.o dns.o drtables.o enq.o exim.o expand.o filter.o \
+        filtertest.o globals.o dkim.o dkim_transport.o hash.o \
+        header.o host.o ip.o log.o lss.o match.o moan.o \
         os.o parse.o queue.o \
         rda.o readconf.o receive.o retry.o rewrite.o rfc2047.o \
         route.o search.o sieve.o smtp_in.o smtp_out.o spool_in.o spool_out.o \
         std-crypto.o store.o string.o tls.o tod.o transport.o tree.o verify.o \
+        environment.o macro.o \
         $(OBJ_LOOKUPS) \
         local_scan.o $(EXIM_PERL) $(OBJ_WITH_CONTENT_SCAN) \
         $(OBJ_EXPERIMENTAL)
@@ -776,8 +771,6 @@ dbfn.o:          $(HDRS) dbfn.c
 debug.o:         $(HDRS) debug.c
 deliver.o:       $(HDRS) transports/smtp.h deliver.c
 directory.o:     $(HDRS) directory.c
-dkim.o:          $(HDRS) pdkim/pdkim.h dkim.c
-dkim_transport.o: $(HDRS) dkim_transport.c
 dns.o:           $(HDRS) dns.c
 enq.o:           $(HDRS) enq.c
 exim.o:          $(HDRS) exim.c
@@ -792,8 +785,6 @@ host.o:          $(HDRS) host.c
 ip.o:            $(HDRS) ip.c
 log.o:           $(HDRS) log.c
 lss.o:           $(HDRS) lss.c
-macro.o:         $(HDRS) macro.c
-macro_defs.o:    $(HDRS) macro_defs.c
 match.o:         $(HDRS) match.c
 moan.o:          $(HDRS) moan.c
 os.o:            $(HDRS) $(OS_C_INCLUDES) os.c
@@ -822,6 +813,8 @@ tod.o:           $(HDRS) tod.c
 transport.o:     $(HDRS) transport.c
 tree.o:          $(HDRS) tree.c
 verify.o:        $(HDRS) transports/smtp.h verify.c
+dkim.o:          $(HDRS) pdkim/pdkim.h dkim.c
+dkim_transport.o: $(HDRS) dkim_transport.c
 
 # Dependencies for WITH_CONTENT_SCAN modules
 
diff --git a/src/OS/os.c-SunOS5 b/src/OS/os.c-SunOS5
index 8ad8c9380..162486958 100644
--- a/src/OS/os.c-SunOS5
+++ b/src/OS/os.c-SunOS5
@@ -3,7 +3,7 @@
 *************************************************/
 
 /* Copyright (c) University of Cambridge 2016 */
-/* Copyright (c) Jeremy Harris 2018 */
+/* Copyright (c) Jeremy Harris 2016 */
 /* See the file NOTICE for conditions of use and distribution. */
 
 /* Solaris-specific code. This is concatenated onto the generic
@@ -13,15 +13,4 @@ src/os.c file. */
 # include "setenv.c"
 #endif
 
-/* This is missing in Solaris 10, present in Solaris 11.
-A feature-test would be good. */
-
-char *
-strndup(const char * s, unsigned long n)
-{
-char * dest;
-if (!(dest = malloc(n))) return NULL;
-return strncpy(dest, s, n);
-}
-
 /* End of os.c-SunOS5 */
diff --git a/src/OS/os.h-SunOS5 b/src/OS/os.h-SunOS5
index 113adc05f..dfbd8f1af 100644
--- a/src/OS/os.h-SunOS5
+++ b/src/OS/os.h-SunOS5
@@ -48,6 +48,4 @@ a buffer */
 # define MAX(a,b) (((a)>(b))?(a):(b))
 #endif
 
-extern char * strndup(const char *, unsigned long);
-
 /* End */
diff --git a/src/scripts/MakeLinks b/src/scripts/MakeLinks
index 7427a8a2b..6314fe441 100755
--- a/src/scripts/MakeLinks
+++ b/src/scripts/MakeLinks
@@ -110,7 +110,7 @@ for f in blob.h dbfunctions.h dbstuff.h exim.h functions.h globals.h \
   tod.c transport.c tree.c verify.c version.c \
   dkim.c dkim.h dkim_transport.c dmarc.c dmarc.h \
   valgrind.h memcheck.h \
-  macro.c macro_predef.c macro_predef.h
+  macro_predef.c macro_predef.h
 do
   ln -s ../src/$f $f
 done
diff --git a/src/src/exim.c b/src/src/exim.c
index 354cdf7a8..327a8ecfe 100644
--- a/src/src/exim.c
+++ b/src/src/exim.c
@@ -1295,32 +1295,6 @@ exit(EXIT_FAILURE);
 *    Validate that the macros given are okay     *
 *************************************************/
 
-#ifdef WHITELIST_D_MACROS
-static void
-wlist_check(uschar * name, uschar * val, void * ctx)
-{
-uschar ** w, ** whites = ctx;
-unsigned len;
-int n;
-
-for (w = whites; *w; ++w)
-  if (Ustrcmp(*w, name) == 0) break;
-if (*w) 
-  {
-  if (!val || !*val) return;
-  len = Ustrlen(val);
-  if ((n = pcre_exec(regex_whitelisted_macro, NULL, CS val, len,
-		    0, PCRE_EOPT, NULL, 0)) >= 0)
-    return;
-  if (n != PCRE_ERROR_NOMATCH)
-    debug_printf("macros_trusted checking %s returned %d\n", name, n);
-  }
-*whites = NULL;
-return;
-}
-#endif
-
-
 /* Typically, Exim will drop privileges if macros are supplied.  In some
 cases, we want to not do so.
 
@@ -1333,7 +1307,7 @@ macros_trusted(BOOL opt_D_used)
 {
 #ifdef WHITELIST_D_MACROS
 macro_item *m;
-uschar *whitelisted, *end, *p, **whites;
+uschar *whitelisted, *end, *p, **whites, **w;
 int white_count, i, n;
 size_t len;
 BOOL prev_char_item, found;
@@ -1396,9 +1370,32 @@ for (p = whitelisted, i = 0; (p != end) && (i < white_count); ++p)
   }
 whites[i] = NULL;
 
-tree_walk(tree_macros, wlist_check, whites);
-if (!*whites) return FALSE;
-
+/* The list of commandline macros should be very short.
+Accept the N*M complexity. */
+for (m = macros; m; m = m->next) if (m->command_line)
+  {
+  found = FALSE;
+  for (w = whites; *w; ++w)
+    if (Ustrcmp(*w, m->name) == 0)
+      {
+      found = TRUE;
+      break;
+      }
+  if (!found)
+    return FALSE;
+  if (!m->replacement)
+    continue;
+  if ((len = m->replen) == 0)
+    continue;
+  n = pcre_exec(regex_whitelisted_macro, NULL, CS m->replacement, len,
+   0, PCRE_EOPT, NULL, 0);
+  if (n < 0)
+    {
+    if (n != PCRE_ERROR_NOMATCH)
+      debug_printf("macros_trusted checking %s returned %d\n", m->name, n);
+    return FALSE;
+    }
+  }
 DEBUG(D_any) debug_printf("macros_trusted overridden to true by whitelisting\n");
 return TRUE;
 #endif
@@ -1430,10 +1427,7 @@ len = Ustrlen(big_buffer);
 if (isupper(big_buffer[0]))
   {
   if (macro_read_assignment(big_buffer))
-    {
-    uschar * s = Ustrchr(big_buffer, '=');
-    printf("Defined macro '%.*s'\n", (int)(s - big_buffer), big_buffer);
-    }
+    printf("Defined macro '%s'\n", mlast->name);
   }
 else
   if ((line = expand_string(big_buffer))) printf("%s\n", CS line);
@@ -2428,21 +2422,22 @@ for (i = 1; i < argc; i++)
         while (isspace(*s)) s++;
         }
 
-      if (macro_search(name))
-        {
-        fprintf(stderr, "exim: duplicated -D in command line\n");
-        exit(EXIT_FAILURE);
-        }
+      for (m = macros; m; m = m->next)
+        if (Ustrcmp(m->name, name) == 0)
+          {
+          fprintf(stderr, "exim: duplicated -D in command line\n");
+          exit(EXIT_FAILURE);
+          }
 
-      m = macro_create(name, s, TRUE);
+      m = macro_create(string_copy(name), string_copy(s), TRUE);
 
       if (clmacro_count >= MAX_CLMACROS)
         {
         fprintf(stderr, "exim: too many -D options on command line\n");
         exit(EXIT_FAILURE);
         }
-      clmacros[clmacro_count++] = string_sprintf("-D%s=%s",
-	m->tnode.name, m->tnode.data.ptr);
+      clmacros[clmacro_count++] = string_sprintf("-D%s=%s", m->name,
+        m->replacement);
       }
     #endif
     break;
@@ -4993,7 +4988,7 @@ if (expansion_test)
 
   /* Only admin users may see config-file macros this way */
 
-  if (!admin_user) tree_macros = NULL;
+  if (!admin_user) macros = mlast = NULL;
 
   /* Allow $recipients for this testing */
 
diff --git a/src/src/functions.h b/src/src/functions.h
index 2a4e54aeb..00da0cf20 100644
--- a/src/src/functions.h
+++ b/src/src/functions.h
@@ -256,10 +256,6 @@ extern int     log_create_as_exim(uschar *);
 extern void    log_close_all(void);
 
 extern macro_item * macro_create(const uschar *, const uschar *, BOOL);
-extern macro_item * macro_search(const uschar *);
-extern macro_item * macro_search_largest_prefix(const uschar *);
-extern macro_item * macro_search_prefix(const uschar *);
-extern void         macro_print(uschar *, uschar *, void *);
 extern BOOL    macro_read_assignment(uschar *);
 extern uschar *macros_expand(int, int *, BOOL *);
 extern void    mainlog_close(void);
diff --git a/src/src/globals.h b/src/src/globals.h
index 468bfa917..766b8a42f 100644
--- a/src/src/globals.h
+++ b/src/src/globals.h
@@ -565,7 +565,8 @@ extern uschar *lookup_dnssec_authenticated; /* AD status of dns lookup */
 extern int     lookup_open_max;        /* Max lookup files to cache */
 extern uschar *lookup_value;           /* Value looked up from file */
 
-extern unsigned m_number;	       /* count of macros */
+extern macro_item *macros;             /* Configuration macros */
+extern macro_item *mlast;              /* Last item in macro list */
 extern uschar *mailstore_basename;     /* For mailstore deliveries */
 #ifdef WITH_CONTENT_SCAN
 extern uschar *malware_name;           /* Name of virus or malware ("W32/Klez-H") */
@@ -954,7 +955,6 @@ extern int     transport_write_timeout;/* Set to time out individual writes */
 extern tree_node *tree_dns_fails;      /* Tree of DNS lookup failures */
 extern tree_node *tree_duplicates;     /* Tree of duplicate addresses */
 extern tree_node *tree_nonrecipients;  /* Tree of nonrecipient addresses */
-extern tree_node *tree_macros;         /* Configuration macros */
 extern tree_node *tree_unusable;       /* Tree of unusable addresses */
 
 extern BOOL    trusted_caller;         /* Caller is trusted */
diff --git a/src/src/macro.c b/src/src/macro.c
deleted file mode 100644
index 21e51044e..000000000
--- a/src/src/macro.c
+++ /dev/null
@@ -1,137 +0,0 @@
-/*************************************************
-*     Exim - an Internet mail transport agent    *
-*************************************************/
-
-/* Copyright (c) University of Cambridge 1995 - 2018 */
-/* See the file NOTICE for conditions of use and distribution. */
-
-/* Functions for handling macros */
-
-#include "exim.h"
-
-#ifdef MACRO_PREDEF
-# undef store_get
-# define store_get(nbytes) malloc((size_t)(nbytes))
-#define string_copyn(s, len) strndup(CS(s), (len))
-#endif
-
-/*************************************************
-*       Deal with an assignment to a macro       *
-*************************************************/
-
-/* We have a new definition; add to the collection.
-Items are numbered so we can avoid recursion in expansions.
-
-Args:
- name	Name of the macro.  Will be copied.
- val	Expansion result for the macro.  Will be copied.
-*/
-
-macro_item *
-macro_create(const uschar * name, const uschar * val, BOOL command_line)
-{
-int namelen = Ustrlen(name);
-macro_item * m = store_get(sizeof(macro_item) + namelen);
-
-/* fprintf(stderr, "%s: '%s' '%s'\n", __FUNCTION__, name, val); */
-
-m->command_line = command_line;
-m->namelen = namelen;
-m->replen = Ustrlen(val);
-m->m_number = m_number++;
-memset(&m->tnode, 0, sizeof(tree_node));
-/* Use memcpy here not Ustrcpy to avoid spurious compiler-inserted check
-when building with fortify-source. We know there is room for the copy into
-this dummy for a variable-size array because of the way we did the memory
-allocation above. */
-memcpy(m->tnode.name, name, namelen+1);
-m->tnode.data.ptr = string_copyn(val, m->replen);
-(void) tree_insertnode(&tree_macros, &m->tnode);
-
-return m;
-}
-
-
-/* Search for a macro, with an exact match on the name.
-Return the node, or NULL for not-found.
-
-Arguments:	name	key to search for
-*/
-
-macro_item *
-macro_search(const uschar * name)
-{
-tree_node * t;
-
-t = tree_search(tree_macros, name);
-return tnode_to_mitem(t);
-}
-
-
-/* Search for a macro with a (possibly improper) leading substring
-matching the given name.  Return the node, or NULL for not-found.
-
-Arguments:	name	key to search on
-*/
-
-macro_item *
-macro_search_prefix(const uschar * s)
-{
-tree_node * t;
-int c;
-
-for (t = tree_macros; t; t = c < 0 ? t->left : t->right)
-  if ((c = Ustrncmp(s, t->name, tnode_to_mitem(t)->namelen)) == 0)
-    return tnode_to_mitem(t);
-return NULL;
-}
-
-
-/* Search for the macro with the largest possible leading substring
-matching the given name. */
-
-macro_item *
-macro_search_largest_prefix(const uschar * s)
-{
-macro_item * found;
-tree_node * child;
-int c;
-
-if ((found = macro_search_prefix(s)))
-  {
-  /* There could be a node with a larger substring also matching the
-  name.  If so it must be in the right subtree; either the right child
-  or (if that sorts after the name) in the left subtree of the right child. */
-
-  child = found->tnode.right;
-  while (child)
-    if ((c = Ustrncmp(s, child->name, tnode_to_mitem(child)->namelen)) == 0)
-      {
-      found = tnode_to_mitem(child);
-      child = found->tnode.right;
-      }
-    else if (c < 0 && (child = child->left))
-      continue;
-    else
-      break;
-  }
-return found;
-}
-
-
-
-void
-macro_print(uschar * name, uschar * val, void * ctx)
-{
-BOOL names_only = (BOOL)(long)ctx;
-if (names_only)
-  printf("%s\n", CS name);
-else
-  printf("%s=%s\n", CS name, CS val);
-}
-
-
-
-/* vi: aw ai sw=2
-*/
-/* End of macro.c */
diff --git a/src/src/macro_predef.c b/src/src/macro_predef.c
index 30b5e8a54..0d70826bb 100644
--- a/src/src/macro_predef.c
+++ b/src/src/macro_predef.c
@@ -11,8 +11,7 @@ included in the main Exim build */
 #include "exim.h"
 #include "macro_predef.h"
 
-tree_node * tree_macros = NULL;
-unsigned m_number = 1;
+unsigned mp_index = 0;
 
 /* Global dummy variables */
 
@@ -24,7 +23,16 @@ uschar * syslog_facility_str;
 void
 builtin_macro_create_var(const uschar * name, const uschar * val)
 {
-macro_create(name, val, FALSE);
+printf ("static macro_item p%d = { ", mp_index);
+if (mp_index == 0)
+  printf(".next=NULL,");
+else
+  printf(".next=&p%d,", mp_index-1);
+
+printf(" .command_line=FALSE, .namelen=%d, .replen=%d,"
+	" .name=US\"%s\", .replacement=US\"%s\" };\n",
+	Ustrlen(name), Ustrlen(val), CS name, CS val);
+mp_index++;
 }
 
 
@@ -281,59 +289,15 @@ params_dkim();
 }
 
 
-static unsigned
-macro_dump(macro_item * m)
-{
-int left = 0, right = 0;
-tree_node * t;
-macro_item_64 * m64;
-
-/* fprintf(stderr, "%s %p\n", __FUNCTION__, m); */
-
-if (!m) return 0;
-/* fprintf(stderr, "%s '%s' l %p r %p\n", __FUNCTION__, m->tnode.name, m->tnode.left, m->tnode.left); */
-if ((t = m->tnode.left)) left = macro_dump(tnode_to_mitem(m->tnode.left));
-if ((t = m->tnode.right)) right = macro_dump(tnode_to_mitem(m->tnode.right));
-
-printf ("static macro_item_64 p%u = { ", m->m_number);
-printf(" .command_line=FALSE,"
-       " .namelen=%d,"
-       " .replen=%d,"
-       " .m_number=%u,"
-       " .tnode={",
-	Ustrlen(m->tnode.name), Ustrlen(m->tnode.data.ptr), m->m_number);
-printf(left  ? " .left=&p%d.tnode,"  : " .left=NULL,",  left);
-printf(right ? " .right=&p%d.tnode," : " .right=NULL,", right);
-printf(
-	" .data.ptr=\"%s\","
-	" .balance=%d,"
-	" .name=\"%s\"}};\n",
-	CS m->tnode.data.ptr,
-	m->tnode.balance,
-	CS m->tnode.name);
-
-if (Ustrlen(m->tnode.name) +1 > sizeof(m64->tnode.name))
-  {
-  printf("#error macro name too long for macro_item_64\n");
-  exit(1);
-  }
-return m->m_number;
-}
-
-
-
 int
 main(void)
 {
-unsigned idx;
-
 printf("#include \"exim.h\"\n");
 features();
 options();
 params();
 
-idx = macro_dump(tnode_to_mitem(tree_macros));
-printf("tree_node * tree_macros = (tree_node *) &p%u.tnode;\n", idx);
-printf("unsigned m_number = %u;\n", m_number);
+printf("macro_item * macros = &p%d;\n", mp_index-1);
+printf("macro_item * mlast = &p0;\n");
 exit(0);
 }
diff --git a/src/src/readconf.c b/src/src/readconf.c
index 42bb5afe5..5d519e996 100644
--- a/src/src/readconf.c
+++ b/src/src/readconf.c
@@ -592,6 +592,38 @@ return US"";
 
 
 
+/*************************************************
+*       Deal with an assignment to a macro       *
+*************************************************/
+
+/* We have a new definition; append to the list.
+
+Args:
+ name	Name of the macro.  Must be in storage persistent past the call
+ val	Expansion result for the macro.  Ditto persistence.
+*/
+
+macro_item *
+macro_create(const uschar * name, const uschar * val, BOOL command_line)
+{
+macro_item * m = store_get(sizeof(macro_item));
+
+/* fprintf(stderr, "%s: '%s' '%s'\n", __FUNCTION__, name, val); */
+m->next = NULL;
+m->command_line = command_line;
+m->namelen = Ustrlen(name);
+m->replen = Ustrlen(val);
+m->name = name;
+m->replacement = val;
+if (mlast)
+  mlast->next = m;
+else
+  macros = m;
+mlast = m;
+return m;
+}
+
+
 /* This function is called when a line that starts with an upper case letter is
 encountered. The argument "line" should contain a complete logical line, and
 start with the first letter of the macro name. The macro name and the
@@ -642,37 +674,53 @@ while (isspace(*s)) s++;
 just skip this definition. It's an error to attempt to redefine a macro without
 redef set to TRUE, or to redefine a macro when it hasn't been defined earlier.
 It is also an error to define a macro whose name begins with the name of a
-previously defined macro.
+previously defined macro.  This is the requirement that make using a tree
+for macros hard; we must check all macros for the substring.  Perhaps a
+sorted list, and a bsearch, would work?
 Note: it is documented that the other way round works. */
 
-if ((m = macro_search_prefix(name)))
+for (m = macros; m; m = m->next)
   {
-  if (m->namelen < namelen)	/* substring match */
+  if (Ustrcmp(m->name, name) == 0)
     {
-    log_write(0, LOG_CONFIG|LOG_PANIC, "\"%s\" cannot be defined as "
-      "a macro because previously defined macro \"%s\" is a substring",
-      name, m->tnode.name);
-    return FALSE;
+    if (!m->command_line && !redef)
+      {
+      log_write(0, LOG_CONFIG|LOG_PANIC, "macro \"%s\" is already "
+       "defined (use \"==\" if you want to redefine it", name);
+      return FALSE;
+      }
+    break;
     }
-  				/* exact match */
-  if (!m->command_line && !redef)
+
+  if (m->namelen < namelen && Ustrstr(name, m->name) != NULL)
     {
-    log_write(0, LOG_CONFIG|LOG_PANIC, "macro \"%s\" is already "
-       "defined (use \"==\" if you want to redefine it", name);
+    log_write(0, LOG_CONFIG|LOG_PANIC, "\"%s\" cannot be defined as "
+      "a macro because previously defined macro \"%s\" is a substring",
+      name, m->name);
     return FALSE;
     }
 
-  if (m->command_line)		/* overriding cmdline definition */
-    return TRUE;
+  /* We cannot have this test, because it is documented that a substring
+  macro is permitted (there is even an example).
+  *
+  * if (m->namelen > namelen && Ustrstr(m->name, name) != NULL)
+  *   log_write(0, LOG_CONFIG|LOG_PANIC_DIE, "\"%s\" cannot be defined as "
+  *     "a macro because it is a substring of previously defined macro \"%s\"",
+  *     name, m->name);
+  */
   }
 
+/* Check for an overriding command-line definition. */
+
+if (m && m->command_line) return TRUE;
+
 /* Redefinition must refer to an existing macro. */
 
 if (redef)
   if (m)
     {
     m->replen = Ustrlen(s);
-    m->tnode.data.ptr = string_copy(s);
+    m->replacement = string_copy(s);
     }
   else
     {
@@ -683,7 +731,7 @@ if (redef)
 
 /* We have a new definition. */
 else
-  (void) macro_create(name, s, FALSE);
+  (void) macro_create(string_copy(name), string_copy(s), FALSE);
 return TRUE;
 }
 
@@ -708,6 +756,7 @@ macros_expand(int len, int * newlen, BOOL * macro_found)
 {
 uschar * ss = big_buffer + len;
 uschar * s;
+macro_item * m;
 
 /* Find the true start of the physical line - leading spaces are always
 ignored. */
@@ -728,52 +777,56 @@ if (len == 0 && isupper(*s))
   if (*s != '=') s = ss;          /* Not a macro definition */
   }
 
-/* Scan the line (from after XXX= if present), replacing any macros. Rescan
-after replacement for any later-defined macros. */
+/* Skip leading chars which cannot start a macro name, to avoid multiple
+pointless rescans in Ustrstr calls. */
+
+while (*s && !isupper(*s) && *s != '_') s++;
+
+/* For each defined macro, scan the line (from after XXX= if present),
+replacing all occurrences of the macro. */
 
 *macro_found = FALSE;
-while (*s)
+for (m = macros; m; m = m->next)
   {
-  if (isupper(*s) || *s == '_' && isupper(s[1]))
-    {
-    macro_item * m;
-    unsigned mnum = 0;
+  uschar * p, *pp;
+  uschar * t = s;
 
-    while ((m = macro_search_largest_prefix(s)) && m->m_number > mnum)
-      {
-      uschar * pp;
-      int moveby;
+  while ((p = Ustrstr(t, m->name)) != NULL)
+    {
+    int moveby;
 
-      /* Expand the buffer if necessary */
+/* fprintf(stderr, "%s: matched '%s' in '%s'\n", __FUNCTION__, m->name, ss); */
+    /* Expand the buffer if necessary */
 
-      while (*newlen - m->namelen + m->replen + 1 > big_buffer_size)
-	{
-	int newsize = big_buffer_size + BIG_BUFFER_SIZE;
-	uschar *newbuffer = store_malloc(newsize);
-	memcpy(newbuffer, big_buffer, *newlen + 1);
-	s = newbuffer  + (s - big_buffer);
-	ss = newbuffer + (ss - big_buffer);
-	big_buffer_size = newsize;
-	store_free(big_buffer);
-	big_buffer = newbuffer;
-	}
+    while (*newlen - m->namelen + m->replen + 1 > big_buffer_size)
+      {
+      int newsize = big_buffer_size + BIG_BUFFER_SIZE;
+      uschar *newbuffer = store_malloc(newsize);
+      memcpy(newbuffer, big_buffer, *newlen + 1);
+      p = newbuffer  + (p - big_buffer);
+      s = newbuffer  + (s - big_buffer);
+      ss = newbuffer + (ss - big_buffer);
+      t = newbuffer  + (t - big_buffer);
+      big_buffer_size = newsize;
+      store_free(big_buffer);
+      big_buffer = newbuffer;
+      }
 
-      /* Shuffle the remaining characters up or down in the buffer before
-      copying in the replacement text. Don't rescan the replacement for this
-      same macro. */
+    /* Shuffle the remaining characters up or down in the buffer before
+    copying in the replacement text. Don't rescan the replacement for this
+    same macro. */
 
-      pp = s + m->namelen;
-      if ((moveby = m->replen - m->namelen) != 0)
-	{
-	memmove(s + m->replen, pp, (big_buffer + *newlen) - pp + 1);
-	*newlen += moveby;
-	}
-      Ustrncpy(s, m->tnode.data.ptr, m->replen);
-      *macro_found = TRUE;
-      mnum = m->m_number;
+    pp = p + m->namelen;
+    if ((moveby = m->replen - m->namelen) != 0)
+      {
+      memmove(p + m->replen, pp, (big_buffer + *newlen) - pp + 1);
+      *newlen += moveby;
       }
+    Ustrncpy(p, m->replacement, m->replen);
+    t = p + m->replen;
+    while (*t && !isupper(*t) && *t != '_') t++;
+    *macro_found = TRUE;
     }
-  s++;
   }
 
 /* An empty macro replacement at the start of a line could mean that ss no
@@ -2810,25 +2863,26 @@ else if (Ustrcmp(type, "macro") == 0)
     fprintf(stderr, "exim: permission denied\n");
     return FALSE;
     }
-
-  if (name)
-    if ((m = macro_search(name)))
-      macro_print(m->tnode.name, m->tnode.data.ptr, (void *)(long)names_only);
-    else
+  for (m = macros; m; m = m->next)
+    if (!name || Ustrcmp(name, m->name) == 0)
       {
-      printf("%s %s not found\n", type, name);
-      return FALSE;
+      if (names_only)
+        printf("%s\n", CS m->name);
+      else
+        printf("%s=%s\n", CS m->name, CS m->replacement);
+      if (name)
+        return TRUE;
       }
-  else
-    tree_walk(tree_macros, macro_print, (void *)(long)names_only);
+  if (!name) return TRUE;
 
-  return TRUE;
+  printf("%s %s not found\n", type, name);
+  return FALSE;
   }
 
 if (names_only)
   {
   for (; d; d = d->next) printf("%s\n", CS d->name);
-  return TRUE;;
+  return TRUE;
   }
 
 /* Either search for a given driver, or print all of them */
@@ -2838,8 +2892,7 @@ for (; d; d = d->next)
   BOOL rc = FALSE;
   if (!name)
     printf("\n%s %s:\n", d->name, type);
-  else if (Ustrcmp(d->name, name) != 0)
-    continue;
+  else if (Ustrcmp(d->name, name) != 0) continue;
 
   for (ol = ol2; ol < ol2 + size; ol++)
     if (!(ol->type & opt_hidden))
diff --git a/src/src/structs.h b/src/src/structs.h
index c8798e366..dfe5685e6 100644
--- a/src/src/structs.h
+++ b/src/src/structs.h
@@ -32,6 +32,17 @@ typedef struct gstring {
   uschar * s;		/* The string memory */
 } gstring;
 
+/* Structure for remembering macros for the configuration file */
+
+typedef struct macro_item {
+  struct  macro_item * next;
+  BOOL     	command_line;
+  unsigned	namelen;
+  unsigned	replen;
+  const uschar * name;
+  const uschar * replacement;
+} macro_item;
+
 /* Structure for bit tables for debugging and logging */
 
 typedef struct bit_table {
@@ -694,38 +705,6 @@ typedef struct tree_node {
   uschar  name[1];                /* node name - variable length */
 } tree_node;
 
-typedef struct tree_node_64 {
-  struct tree_node_64 *left;      /* pointer to left child */
-  struct tree_node_64 *right;     /* pointer to right child */
-  union
-    {
-    void  *ptr;                   /* pointer to data */
-    int val;                      /* or integer data */
-    } data;
-  uschar  balance;                /* balancing factor */
-  uschar  name[64];               /* node name - bounded length */
-} tree_node_64;
-
-/* Structure for remembering macros for the configuration file */
-
-typedef struct macro_item {
-  BOOL     	command_line;
-  unsigned	namelen;
-  unsigned	replen;
-  unsigned	m_number;
-  tree_node	tnode;		/* contains name; ptr indicates val */
-} macro_item;
-
-typedef struct macro_item_64 {
-  BOOL     	command_line;
-  unsigned	namelen;
-  unsigned	replen;
-  unsigned	m_number;
-  tree_node_64	tnode;		/* contains name; ptr indicates val */
-} macro_item_64;
-
-#define tnode_to_mitem(tp) (tp ? (macro_item *) (CS(tp) - offsetof(macro_item, tnode)) : NULL)
-
 /* Structure for holding time-limited data such as DNS returns.
 We use this rather than extending tree_node to avoid wasting
 space for most tree use (variables...) at the cost of complexity
diff --git a/src/src/tree.c b/src/src/tree.c
index b5918a6a3..3b6c3603b 100644
--- a/src/src/tree.c
+++ b/src/src/tree.c
@@ -12,7 +12,6 @@ functions as well. */
 #include "exim.h"
 
 
-#ifndef MACRO_PREDEF
 
 
 /*************************************************
@@ -116,9 +115,10 @@ Returns:     nothing
 static void
 write_tree(tree_node *p, FILE *f)
 {
-fprintf(f, "%c%c %s\n", p->left ? 'Y':'N', p->right ? 'Y':'N', p->name);
-if (p->left) write_tree(p->left, f);
-if (p->right) write_tree(p->right, f);
+fprintf(f, "%c%c %s\n",
+  (p->left == NULL)? 'N':'Y', (p->right == NULL)? 'N':'Y', p->name);
+if (p->left != NULL) write_tree(p->left, f);
+if (p->right != NULL) write_tree(p->right, f);
 }
 
 /* This is the top-level function, with the same arguments. */
@@ -126,7 +126,7 @@ if (p->right) write_tree(p->right, f);
 void
 tree_write(tree_node *p, FILE *f)
 {
-if (!p)
+if (p == NULL)
   {
   fprintf(f, "XX\n");
   return;
@@ -135,7 +135,6 @@ write_tree(p, f);
 }
 
 
-#endif
 
 
 
@@ -186,7 +185,7 @@ node->balance = 0;
 
 /* Deal with an empty tree */
 
-if (!p)
+if (p == NULL)
   {
   *treebase = node;
   return TRUE;
@@ -209,9 +208,9 @@ for (;;)
   /* Deal with climbing down the tree, exiting from the loop
   when we reach a leaf. */
 
-  q = c > 0 ? &p->right : &p->left;
+  q = (c > 0)? &(p->right) : &(p->left);
   p = *q;
-  if (!p) break;
+  if (p == NULL) break;
 
   /* Save the address of the pointer to the last node en route
   which has a non-zero balance factor. */
@@ -228,13 +227,14 @@ that is the place at which the new node must be inserted. */
 next node after it along the route. */
 
 s = *t;
-r = Ustrcmp(node->name, s->name) > 0 ? s->right : s->left;
+r = (Ustrcmp(node->name, s->name) > 0)? s->right : s->left;
 
 /* Adjust balance factors along the route from s to node. */
 
 p = r;
 
 while (p != node)
+  {
   if (Ustrcmp(node->name, p->name) < 0)
     {
     p->balance = tree_lbal;
@@ -245,16 +245,15 @@ while (p != node)
     p->balance = tree_rbal;
     p = p->right;
     }
+  }
 
 /* Now the World-Famous Balancing Act */
 
-a = Ustrcmp(node->name, s->name) < 0 ? tree_lbal : tree_rbal;
+a = (Ustrcmp(node->name, s->name) < 0)? tree_lbal : tree_rbal;
 
-if (s->balance == 0)
-  s->balance = (uschar)a;			/* The tree has grown higher */
-else if (s->balance != (uschar)a)
-   s->balance = 0;				/* It's become more balanced */
-else						/* It's got out of balance */
+if (s->balance == 0) s->balance = (uschar)a;        /* The tree has grown higher */
+  else if (s->balance != (uschar)a) s->balance = 0; /* It's become more balanced */
+else                                              /* It's got out of balance */
   {
   /* Perform a single rotation */
 
@@ -284,7 +283,7 @@ else						/* It's got out of balance */
     {
     if (a == tree_rbal)
       {
-      if (!r->left) return TRUE;   /* Bail out if tree corrupt */
+      if (r->left == NULL) return TRUE;   /* Bail out if tree corrupt */
       p = r->left;
       r->left = p->right;
       p->right = r;
@@ -293,7 +292,7 @@ else						/* It's got out of balance */
       }
     else
       {
-      if (!r->right) return TRUE;  /* Bail out if tree corrupt */
+      if (r->right == NULL) return TRUE;  /* Bail out if tree corrupt */
       p = r->right;
       r->right = p->left;
       p->left = r;
@@ -301,8 +300,8 @@ else						/* It's got out of balance */
       p->right = s;
       }
 
-    s->balance = p->balance == (uschar)a ? (uschar)(a^tree_bmask) : 0;
-    r->balance = p->balance == (uschar)(a^tree_bmask) ? (uschar)a : 0;
+    s->balance = (p->balance == (uschar)a)? (uschar)(a^tree_bmask) : 0;
+    r->balance = (p->balance == (uschar)(a^tree_bmask))? (uschar)a : 0;
     p->balance = 0;
     }
 
@@ -331,15 +330,16 @@ Returns:    pointer to node, or NULL if not found
 tree_node *
 tree_search(tree_node *p, const uschar *name)
 {
-int c;
-for ( ; p; p = c < 0 ? p->left : p->right)
-  if ((c = Ustrcmp(name, p->name)) == 0)
-    return p;
+while (p)
+  {
+  int c = Ustrcmp(name, p->name);
+  if (c == 0) return p;
+  p = c < 0 ? p->left : p->right;
+  }
 return NULL;
 }
 
 
-#ifndef MACRO_PREDEF
 
 /*************************************************
 *   Walk tree recursively and execute function   *
@@ -361,6 +361,5 @@ tree_walk(p->left, f, ctx);
 tree_walk(p->right, f, ctx);
 }
 
-#endif
 
 /* End of tree.c */