[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[17/18] argv_ref speedup: reuse $@ inside quoted strings
|
From: |
Eric Blake |
|
Subject: |
[17/18] argv_ref speedup: reuse $@ inside quoted strings |
|
Date: |
Fri, 22 Feb 2008 06:31:43 -0700 |
|
User-agent: |
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.9) Gecko/20071031 Thunderbird/2.0.0.9 Mnenhy/0.7.5.666 |
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Next in the series. Finally, we are starting to reach my original goal of
reducing the time complexity of m4! The idea here is that $@ occurs often
enough inside of quoted text that we should keep it as a single reference
rather than flattening it to contiguous text. This means that argument
collection must distinguish between a $@ ref representing multiple
arguments (a wrapper), and a $@ ref occurring inside a quoted context (new
in this patch). This provided the huge gain - for boxed recursion, a $@
ref can now be collected once then reused throughout the entire recursion
chain, achieving linear time and space! Typical unboxed recursion is
still quadratic in time, though, because each iteration is still creating
a new wrapper rather than reusing the existing $@ ref.
Also, since a $@ ref can contain arguments that are builtin function
tokens from defn, those tokens should only be flattened to the empty
string at the site(s) where they are used as strings rather than during
argument collection. Tracking whether $@ contains any builtin tokens led
to some minor improvements in its own right, as well as opening the door
for a later patch to allow user functions to transparently handle builtin
tokens.
2008-02-22 Eric Blake <address@hidden>
Stage 17: pass argv through quoted strings.
Allow the concatenation of $@ references with other text input
inside quoted contexts, which requires distinguishing between a
wrapper around many arguments vs. a reference serving as part of a
single argument. Also optimize based on whether argv contains
builtin tokens that might need flattening to the empty string.
Memory impact: noticeable improvement, due to O(n^2) to O(n)
reduction from total reuse of $@ references.
Speed impact: noticeable improvement, due to O(n^2) to O(n)
reduction in boxed recursion.
* src/input.c (append_quote_token): Allow an argv ref inside
quotes.
(init_argv_token): Populate new fields.
(push_macro): Ensure a macro is actually pushed.
* src/m4.h (struct token_chain): Add has_func member.
(struct token_data): Add wrapper and has_func members.
* src/macro.c (struct macro_arguments): Add flatten and has_func
members.
(expand_argument, collect_arguments, make_argv_ref_token)
(make_argv_ref): Populate new fields.
(arg_equal, arg_len) Handle embedded argv.
(arg_token, arg_mark, arg_type): Use new fields.
- --
Don't work too hard, make some time for fun as well!
Eric Blake address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHvs6/84KuGfSFAYARAiF5AKDVDuWTO/fxT9QK5KkN1G3gyt853wCeJpjc
gSyRRzYdBrjwlryKJCCKkm8=
=fMYV
-----END PGP SIGNATURE-----
>From 2cdf327333be152135f021988c8e0eb6f3e10b51 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Fri, 22 Feb 2008 05:43:04 -0700
Subject: [PATCH] Stage 17: pass argv through quoted strings.
* m4/m4module.h (m4_arg_equal, m4_arg_len): Add parameter.
(M4ARGLEN): Adjust definition.
* m4/m4private.h (struct m4__symbol_chain): Add has_func member.
(struct m4_symbol_value): Add wrapper and has_func members.
(struct m4_macro_args): Add flatten and has_func members.
* m4/input.c (append_quote_token): Return argv refs inside quoted
strings.
(init_argv_symbol): Populate new fields.
* m4/macro.c (expand_argument, collect_arguments, make_argv_ref)
(m4_make_argv_ref): Likewise.
(arg_symbol, arg_mark, m4_is_arg_text, m4_is_arg_func): Use new
fields.
(m4_arg_equal, m4_arg_len): Handle quoted argv references, and add
new parameter.
* modules/m4.c (ifelse): Adjust caller.
Signed-off-by: Eric Blake <address@hidden>
---
ChangeLog | 28 +++++++++
m4/input.c | 17 ++----
m4/m4module.h | 11 ++--
m4/m4private.h | 11 +++-
m4/macro.c | 175 +++++++++++++++++++++++++++++++++++++++++++-------------
modules/m4.c | 2 +-
6 files changed, 183 insertions(+), 61 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index abec593..cb6a845 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,31 @@
+2008-02-22 Eric Blake <address@hidden>
+
+ Stage 17: pass argv through quoted strings.
+ Allow the concatenation of $@ references with other text input
+ inside quoted contexts, which requires distinguishing between a
+ wrapper around many arguments vs. a reference serving as part of a
+ single argument. Also optimize based on whether argv contains
+ builtin tokens that might need flattening to the empty string.
+ Memory impact: noticeable improvement, due to O(n^2) to O(n)
+ reduction from total reuse of $@ references.
+ Speed impact: noticeable improvement, due to O(n^2) to O(n)
+ reduction in boxed recursion.
+ * m4/m4module.h (m4_arg_equal, m4_arg_len): Add parameter.
+ (M4ARGLEN): Adjust definition.
+ * m4/m4private.h (struct m4__symbol_chain): Add has_func member.
+ (struct m4_symbol_value): Add wrapper and has_func members.
+ (struct m4_macro_args): Add flatten and has_func members.
+ * m4/input.c (append_quote_token): Return argv refs inside quoted
+ strings.
+ (init_argv_symbol): Populate new fields.
+ * m4/macro.c (expand_argument, collect_arguments, make_argv_ref)
+ (m4_make_argv_ref): Likewise.
+ (arg_symbol, arg_mark, m4_is_arg_text, m4_is_arg_func): Use new
+ fields.
+ (m4_arg_equal, m4_arg_len): Handle quoted argv references, and add
+ new parameter.
+ * modules/m4.c (ifelse): Adjust caller.
+
2008-02-22 Gary V. Vaughan <address@hidden>
Fix regression in argument collection, from 2008-01-21.
diff --git a/m4/input.c b/m4/input.c
index fdfccc8..5ebf87f 100644
--- a/m4/input.c
+++ b/m4/input.c
@@ -1119,22 +1119,11 @@ append_quote_token (m4 *context, m4_obstack *obs,
m4_symbol_value *value)
return;
}
- /* TODO preserve $@ through quotes. */
- if (src_chain->type == M4__CHAIN_ARGV)
- {
- m4_arg_print (context, obs, src_chain->u.u_a.argv,
- src_chain->u.u_a.index,
- m4__quote_cache (M4SYNTAX, NULL, src_chain->quote_age,
- src_chain->u.u_a.quotes),
- src_chain->u.u_a.flatten, NULL, NULL, false, false);
- m4__arg_adjust_refcount (context, src_chain->u.u_a.argv, false);
- return;
- }
-
if (value->type == M4_SYMBOL_VOID)
{
value->type = M4_SYMBOL_COMP;
value->u.u_c.chain = value->u.u_c.end = NULL;
+ value->u.u_c.wrapper = value->u.u_c.has_func = false;
}
assert (value->type == M4_SYMBOL_COMP);
m4__make_text_link (obs, &value->u.u_c.chain, &value->u.u_c.end);
@@ -1144,6 +1133,8 @@ append_quote_token (m4 *context, m4_obstack *obs,
m4_symbol_value *value)
else
value->u.u_c.chain = chain;
value->u.u_c.end = chain;
+ if (chain->type == M4__CHAIN_ARGV && chain->u.u_a.has_func)
+ value->u.u_c.has_func = true;
chain->next = NULL;
}
@@ -1169,6 +1160,8 @@ init_argv_symbol (m4 *context, m4_obstack *obs,
m4_symbol_value *value)
/* Clone the link, since the input will be discarded soon. */
chain = (m4__symbol_chain *) obstack_copy (obs, src_chain, sizeof *chain);
value->u.u_c.chain = value->u.u_c.end = chain;
+ value->u.u_c.wrapper = true;
+ value->u.u_c.has_func = chain->u.u_a.has_func;
chain->next = NULL;
/* If the next character is not ',' or ')', then unlink the last
diff --git a/m4/m4module.h b/m4/m4module.h
index 13f5b4b..c1f1360 100644
--- a/m4/m4module.h
+++ b/m4/m4module.h
@@ -119,9 +119,9 @@ struct m4_string_pair
#define M4ARG(i) m4_arg_text (context, argv, i)
/* Grab the length of the text contents of argument I, or abort if the
- argument is not text. Assumes that `m4_macro_args *argv' is in
- scope. */
-#define M4ARGLEN(i) m4_arg_len (argv, i)
+ argument is not text. Assumes that `m4 *context' and
+ `m4_macro_args *argv' are in scope. */
+#define M4ARGLEN(i) m4_arg_len (context, argv, i)
extern bool m4_bad_argc (m4 *, int, const char *, size_t, size_t,
bool);
@@ -320,9 +320,10 @@ extern m4_symbol_value *m4_arg_symbol (m4_macro_args
*, size_t);
extern bool m4_is_arg_text (m4_macro_args *, size_t);
extern bool m4_is_arg_func (m4_macro_args *, size_t);
extern const char *m4_arg_text (m4 *, m4_macro_args *, size_t);
-extern bool m4_arg_equal (m4_macro_args *, size_t, size_t);
+extern bool m4_arg_equal (m4 *, m4_macro_args *, size_t,
+ size_t);
extern bool m4_arg_empty (m4_macro_args *, size_t);
-extern size_t m4_arg_len (m4_macro_args *, size_t);
+extern size_t m4_arg_len (m4 *, m4_macro_args *, size_t);
extern m4_builtin_func *m4_arg_func (m4_macro_args *, size_t);
extern m4_obstack *m4_arg_scratch (m4 *);
extern bool m4_arg_print (m4 *, m4_obstack *, m4_macro_args *,
diff --git a/m4/m4private.h b/m4/m4private.h
index ee6dc6a..9e10441 100644
--- a/m4/m4private.h
+++ b/m4/m4private.h
@@ -222,6 +222,7 @@ struct m4__symbol_chain
bool_bitfield flatten : 1; /* True to treat builtins as text. */
bool_bitfield comma : 1; /* True when `,' is next input. */
bool_bitfield skip_last : 1; /* True if last argument omitted. */
+ bool_bitfield has_func : 1; /* True if argv includes func. */
const m4_string_pair *quotes; /* NULL for $*, quotes for
address@hidden */
} u_a; /* M4__CHAIN_ARGV. */
} u;
@@ -254,8 +255,10 @@ struct m4_symbol_value
const m4_builtin * builtin;/* Valid when type is FUNC. */
struct
{
- m4__symbol_chain *chain; /* First link of the chain. */
- m4__symbol_chain *end; /* Last link of the chain. */
+ m4__symbol_chain *chain; /* First link of the chain. */
+ m4__symbol_chain *end; /* Last link of the chain. */
+ bool_bitfield wrapper : 1; /* True if this is a $@ ref. */
+ bool_bitfield has_func : 1; /* True if chain includes func. */
} u_c; /* Valid when type is COMP. */
} u;
};
@@ -278,6 +281,10 @@ struct m4_macro_args
/* False if all arguments belong to this argv, true if some of them
include references to another. */
bool_bitfield has_ref : 1;
+ /* True to flatten builtins contained in references. */
+ bool_bitfield flatten : 1;
+ /* True if any token contains builtins. */
+ bool_bitfield has_func : 1;
const char *argv0; /* The macro name being expanded. */
size_t argv0_len; /* Length of argv0. */
/* The value of quote_age for all tokens, or 0 if quote_age changed
diff --git a/m4/macro.c b/m4/macro.c
index 2288dea..0b86018 100644
--- a/m4/macro.c
+++ b/m4/macro.c
@@ -336,10 +336,15 @@ expand_argument (m4 *context, m4_obstack *obs,
m4_symbol_value *argp,
return type == M4_TOKEN_COMMA;
if (argp->type != M4_SYMBOL_COMP)
{
- obstack_1grow (obs, '\0');
VALUE_MODULE (argp) = NULL;
- m4_set_symbol_value_text (argp, obstack_finish (obs), len,
- age);
+ if (len)
+ {
+ obstack_1grow (obs, '\0');
+ m4_set_symbol_value_text (argp, obstack_finish (obs),
+ len, age);
+ }
+ else
+ m4_set_symbol_value_text (argp, "", len, 0);
}
else
m4__make_text_link (obs, NULL, &argp->u.u_c.end);
@@ -372,6 +377,7 @@ expand_argument (m4 *context, m4_obstack *obs,
m4_symbol_value *argp,
{
argp->type = M4_SYMBOL_COMP;
argp->u.u_c.chain = token.u.u_c.chain;
+ argp->u.u_c.wrapper = argp->u.u_c.has_func = false;
}
else
{
@@ -379,6 +385,8 @@ expand_argument (m4 *context, m4_obstack *obs,
m4_symbol_value *argp,
argp->u.u_c.end->next = token.u.u_c.chain;
}
argp->u.u_c.end = token.u.u_c.end;
+ if (token.u.u_c.has_func)
+ argp->u.u_c.has_func = true;
}
break;
@@ -396,6 +404,8 @@ expand_argument (m4 *context, m4_obstack *obs,
m4_symbol_value *argp,
&& token.u.u_c.chain->type == M4__CHAIN_ARGV);
argp->type = M4_SYMBOL_COMP;
argp->u.u_c.chain = argp->u.u_c.end = token.u.u_c.chain;
+ argp->u.u_c.wrapper = true;
+ argp->u.u_c.has_func = token.u.u_c.has_func;
type = m4__next_token (context, &token, NULL, NULL, false, caller);
if (argp->u.u_c.chain->u.u_a.skip_last)
assert (type == M4_TOKEN_COMMA);
@@ -584,6 +594,8 @@ collect_arguments (m4 *context, const char *name, size_t
len,
args.inuse = false;
args.wrapper = false;
args.has_ref = false;
+ args.flatten = !groks_macro_args;
+ args.has_func = false;
/* Must copy here, since we are consuming tokens, and since symbol
table can be changed during argument collection. */
args.argv0 = (char *) obstack_copy0 (arguments, name, len);
@@ -614,23 +626,36 @@ collect_arguments (m4 *context, const char *name, size_t
len,
obstack_ptr_grow (argv_stack, tokenp);
args.arraylen++;
args.argc++;
- /* Be conservative - any change in quoting while collecting
- arguments, or any unsafe argument, will require a rescan
- if $@ is reused. */
- if (m4_is_symbol_value_text (tokenp)
- && m4_get_symbol_value_len (tokenp)
- && m4_get_symbol_value_quote_age (tokenp) != args.quote_age)
- args.quote_age = 0;
- else if (tokenp->type == M4_SYMBOL_COMP)
+ switch (tokenp->type)
{
+ case M4_SYMBOL_TEXT:
+ /* Be conservative - any change in quoting while
+ collecting arguments, or any unsafe argument, will
+ require a rescan if $@ is reused. */
+ if (m4_get_symbol_value_len (tokenp)
+ && m4_get_symbol_value_quote_age (tokenp) != args.quote_age)
+ args.quote_age = 0;
+ break;
+ case M4_SYMBOL_FUNC:
+ args.has_func = true;
+ break;
+ case M4_SYMBOL_COMP:
args.has_ref = true;
- if (tokenp->u.u_c.chain->type == M4__CHAIN_ARGV)
+ if (tokenp->u.u_c.wrapper)
{
+ assert (tokenp->u.u_c.chain->type == M4__CHAIN_ARGV
+ && !tokenp->u.u_c.chain->next);
args.argc += (tokenp->u.u_c.chain->u.u_a.argv->argc
- tokenp->u.u_c.chain->u.u_a.index
- tokenp->u.u_c.chain->u.u_a.skip_last - 1);
args.wrapper = true;
}
+ if (tokenp->u.u_c.has_func)
+ args.has_func = true;
+ break;
+ default:
+ assert (!"expand_argument");
+ abort ();
}
}
while (more_args);
@@ -639,6 +664,7 @@ collect_arguments (m4 *context, const char *name, size_t
len,
argv->argc = args.argc;
argv->wrapper = args.wrapper;
argv->has_ref = args.has_ref;
+ argv->has_func = args.has_func;
if (args.quote_age != m4__quote_age (M4SYNTAX))
argv->quote_age = 0;
argv->arraylen = args.arraylen;
@@ -1031,15 +1057,13 @@ arg_mark (m4_macro_args *argv)
if (argv->wrapper)
{
for (i = 0; i < argv->arraylen; i++)
- if (argv->array[i]->type == M4_SYMBOL_COMP)
+ if (argv->array[i]->type == M4_SYMBOL_COMP
+ && argv->array[i]->u.u_c.wrapper)
{
chain = argv->array[i]->u.u_c.chain;
- while (chain)
- {
- if (chain->type == M4__CHAIN_ARGV && !chain->u.u_a.argv->inuse)
- arg_mark (chain->u.u_a.argv);
- chain = chain->next;
- }
+ assert (!chain->next && chain->type == M4__CHAIN_ARGV);
+ if (!chain->u.u_a.argv->inuse)
+ arg_mark (chain->u.u_a.argv);
}
}
}
@@ -1058,10 +1082,11 @@ make_argv_ref (m4 *context, m4_symbol_value *value,
m4_obstack *obs,
m4__symbol_chain *chain;
assert (obstack_object_size (obs) == 0);
+ /* TODO reuse $@ even if argv has multiple array slots. */
if (argv->wrapper && argv->arraylen == 1)
{
- /* TODO support $@ ref alongside other arguments. */
- assert (argv->array[0]->type == M4_SYMBOL_COMP);
+ assert (argv->array[0]->type == M4_SYMBOL_COMP
+ && argv->array[0]->u.u_c.wrapper);
chain= argv->array[0]->u.u_c.chain;
assert (!chain->next && chain->type == M4__CHAIN_ARGV
&& !chain->u.u_a.skip_last);
@@ -1074,12 +1099,15 @@ make_argv_ref (m4 *context, m4_symbol_value *value,
m4_obstack *obs,
chain = (m4__symbol_chain *) obstack_alloc (obs, sizeof *chain);
value->type = M4_SYMBOL_COMP;
value->u.u_c.chain = value->u.u_c.end = chain;
+ value->u.u_c.wrapper = true;
+ value->u.u_c.has_func = argv->has_func;
chain->next = NULL;
chain->type = M4__CHAIN_ARGV;
chain->quote_age = argv->quote_age;
chain->u.u_a.argv = argv;
chain->u.u_a.index = index;
chain->u.u_a.flatten = flatten;
+ chain->u.u_a.has_func = argv->has_func;
chain->u.u_a.comma = false;
chain->u.u_a.skip_last = false;
chain->u.u_a.quotes = m4__quote_cache (M4SYNTAX, obs, chain->quote_age,
@@ -1108,12 +1136,10 @@ arg_symbol (m4_macro_args *argv, size_t index, size_t
*level)
for (i = 0; i < argv->arraylen; i++)
{
value = argv->array[i];
- if (value->type == M4_SYMBOL_COMP
- && value->u.u_c.chain->type == M4__CHAIN_ARGV)
+ if (value->type == M4_SYMBOL_COMP && value->u.u_c.wrapper)
{
m4__symbol_chain *chain = value->u.u_c.chain;
- /* TODO - for now we support only a single $@ chain. */
- assert (!chain->next);
+ assert (!chain->next && chain->type == M4__CHAIN_ARGV);
if (index <= (chain->u.u_a.argv->argc - chain->u.u_a.index
- chain->u.u_a.skip_last))
{
@@ -1147,21 +1173,23 @@ bool
m4_is_arg_text (m4_macro_args *argv, size_t index)
{
m4_symbol_value *value;
- if (index == 0 || argv->argc <= index)
+ if (index == 0 || argv->argc <= index || argv->flatten || !argv->has_func)
return true;
value = m4_arg_symbol (argv, index);
- /* Composite tokens are currently sequences of text only. */
- if (m4_is_symbol_value_text (value) || value->type == M4_SYMBOL_COMP)
+ if (m4_is_symbol_value_text (value)
+ || (value->type == M4_SYMBOL_COMP && !value->u.u_c.has_func))
return true;
return false;
}
-/* Given ARGV, return true if argument INDEX is a builtin function.
- Only non-zero indices less than argc can return true. */
+/* TODO - add m4_is_arg_comp to distinguish concatenation of builtins. */
+/* Given ARGV, return true if argument INDEX is a single builtin
+ function. Only non-zero indices less than argc can return
+ true. */
bool
m4_is_arg_func (m4_macro_args *argv, size_t index)
{
- if (index == 0 || argv->argc <= index)
+ if (index == 0 || argv->argc <= index || argv->flatten || !argv->has_func)
return false;
return m4_is_symbol_value_func (m4_arg_symbol (argv, index));
}
@@ -1217,7 +1245,7 @@ m4_arg_text (m4 *context, m4_macro_args *argv, size_t
index)
!strcmp (m4_arg_text (context, argv, indexa),
m4_arg_text (context, argv, indexb)). */
bool
-m4_arg_equal (m4_macro_args *argv, size_t indexa, size_t indexb)
+m4_arg_equal (m4 *context, m4_macro_args *argv, size_t indexa, size_t indexb)
{
m4_symbol_value *sa = m4_arg_symbol (argv, indexa);
m4_symbol_value *sb = m4_arg_symbol (argv, indexb);
@@ -1225,6 +1253,7 @@ m4_arg_equal (m4_macro_args *argv, size_t indexa, size_t
indexb)
m4__symbol_chain tmpb;
m4__symbol_chain *ca = &tmpa;
m4__symbol_chain *cb = &tmpb;
+ m4_obstack *obs = m4_arg_scratch (context);
/* Quick tests. */
if (sa == &empty_symbol || sb == &empty_symbol)
@@ -1265,7 +1294,38 @@ m4_arg_equal (m4_macro_args *argv, size_t indexa, size_t
indexb)
/* Compare each link of the chain. */
while (ca && cb)
{
- /* TODO support comparison against $@ refs. */
+ if (ca->type == M4__CHAIN_ARGV)
+ {
+ tmpa.next = ca->next;
+ tmpa.type = M4__CHAIN_STR;
+ /* TODO support funcs in address@hidden */
+ assert (!ca->u.u_a.has_func || argv->flatten || ca->u.u_a.flatten);
+ m4_arg_print (context, obs, ca->u.u_a.argv, ca->u.u_a.index,
+ m4__quote_cache (M4SYNTAX, NULL, ca->quote_age,
+ ca->u.u_a.quotes),
+ argv->flatten || ca->u.u_a.flatten, NULL, NULL, false,
+ false);
+ tmpa.u.u_s.len = obstack_object_size (obs);
+ tmpa.u.u_s.str = (char *) obstack_finish (obs);
+ ca = &tmpa;
+ continue;
+ }
+ if (cb->type == M4__CHAIN_ARGV)
+ {
+ tmpb.next = cb->next;
+ tmpb.type = M4__CHAIN_STR;
+ /* TODO support funcs in address@hidden */
+ assert (!cb->u.u_a.has_func || argv->flatten || cb->u.u_a.flatten);
+ m4_arg_print (context, obs, cb->u.u_a.argv, cb->u.u_a.index,
+ m4__quote_cache (M4SYNTAX, NULL, cb->quote_age,
+ cb->u.u_a.quotes),
+ argv->flatten || cb->u.u_a.flatten, NULL, NULL, false,
+ false);
+ tmpb.u.u_s.len = obstack_object_size (obs);
+ tmpb.u.u_s.str = (char *) obstack_finish (obs);
+ cb = &tmpb;
+ continue;
+ }
assert (ca->type == M4__CHAIN_STR && cb->type == M4__CHAIN_STR);
if (ca->u.u_s.len == cb->u.u_s.len)
{
@@ -1316,7 +1376,7 @@ m4_arg_empty (m4_macro_args *argv, size_t index)
/* Given ARGV, return the length of argument INDEX. Abort if the
argument is not text. Indices beyond argc return 0. */
size_t
-m4_arg_len (m4_macro_args *argv, size_t index)
+m4_arg_len (m4 *context, m4_macro_args *argv, size_t index)
{
m4_symbol_value *value;
m4__symbol_chain *chain;
@@ -1329,14 +1389,43 @@ m4_arg_len (m4_macro_args *argv, size_t index)
value = m4_arg_symbol (argv, index);
if (m4_is_symbol_value_text (value))
return m4_get_symbol_value_len (value);
- /* TODO - for now, we assume all chain links are text. */
assert (value->type == M4_SYMBOL_COMP);
chain = value->u.u_c.chain;
len = 0;
while (chain)
{
- assert (chain->type == M4__CHAIN_STR);
- len += chain->u.u_s.len;
+ size_t i;
+ size_t limit;
+ const m4_string_pair *quotes;
+ switch (chain->type)
+ {
+ case M4__CHAIN_STR:
+ len += chain->u.u_s.len;
+ break;
+ case M4__CHAIN_ARGV:
+ i = chain->u.u_a.index;
+ limit = chain->u.u_a.argv->argc - i - chain->u.u_a.skip_last;
+ quotes = m4__quote_cache (M4SYNTAX, NULL, chain->quote_age,
+ chain->u.u_a.quotes);
+ assert (limit);
+ if (quotes)
+ len += (quotes->len1 + quotes->len2) * limit;
+ len += limit - 1;
+ while (limit--)
+ {
+ /* TODO handle concatenation of builtins. */
+ if (m4_is_symbol_value_func (m4_arg_symbol (chain->u.u_a.argv,
+ i)))
+ assert (argv->flatten);
+ else
+ len += m4_arg_len (context, chain->u.u_a.argv, i);
+ i++;
+ }
+ break;
+ default:
+ assert (!"m4_arg_len");
+ abort ();
+ }
chain = chain->next;
}
assert (len);
@@ -1428,7 +1517,10 @@ m4_make_argv_ref (m4 *context, m4_macro_args *argv,
const char *argv0,
new_argv = (m4_macro_args *) obstack_alloc (obs, offsetof (m4_macro_args,
array));
new_argv->arraylen = 0;
+ new_argv->wrapper = false;
new_argv->has_ref = false;
+ new_argv->flatten = false;
+ new_argv->has_func = false;
}
else
{
@@ -1439,6 +1531,8 @@ m4_make_argv_ref (m4 *context, m4_macro_args *argv, const
char *argv0,
new_argv->array[0] = value;
new_argv->wrapper = true;
new_argv->has_ref = argv->has_ref;
+ new_argv->flatten = flatten;
+ new_argv->has_func = argv->has_func;
}
new_argv->argc = argv->argc - (index - 1);
new_argv->inuse = false;
@@ -1488,10 +1582,9 @@ m4__push_arg_quote (m4 *context, m4_obstack *obs,
m4_macro_args *argv,
obstack_grow (obs, quotes->str2, quotes->len2);
}
-/* Push series of comma-separated arguments from ARGV, which should
- all be text, onto the expansion stack OBS for rescanning. If SKIP,
- then don't push the first argument. If QUOTE, also push quoting
- around each arg. */
+/* Push series of comma-separated arguments from ARGV onto the
+ expansion stack OBS for rescanning. If SKIP, then don't push the
+ first argument. If QUOTE, also push quoting around each arg. */
void
m4_push_args (m4 *context, m4_obstack *obs, m4_macro_args *argv, bool skip,
bool quote)
diff --git a/modules/m4.c b/modules/m4.c
index eb6540b..f5f0766 100644
--- a/modules/m4.c
+++ b/modules/m4.c
@@ -244,7 +244,7 @@ M4BUILTIN_HANDLER (ifelse)
while (true)
{
- if (m4_arg_equal (argv, index, index + 1))
+ if (m4_arg_equal (context, argv, index, index + 1))
{
m4_push_arg (context, obs, argv, index + 2);
return;
--
1.5.4
>From 10801988a863c045aa0dc06b56575f1cc52bc586 Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Thu, 15 Nov 2007 14:56:36 -0700
Subject: [PATCH] Stage 17: pass argv through quoted strings.
* src/input.c (append_quote_token): Allow an argv ref inside
quotes.
(init_argv_token): Populate new fields.
(push_macro): Ensure a macro is actually pushed.
* src/m4.h (struct token_chain): Add has_func member.
(struct token_data): Add wrapper and has_func members.
* src/macro.c (struct macro_arguments): Add flatten and has_func
members.
(expand_argument, collect_arguments, make_argv_ref_token)
(make_argv_ref): Populate new fields.
(arg_equal, arg_len) Handle embedded argv.
(arg_token, arg_mark, arg_type): Use new fields.
(cherry picked from commit 4ecf71f4afd15778cc8f0d10aaf4c344bf2b2b57)
Signed-off-by: Eric Blake <address@hidden>
---
ChangeLog | 25 +++++++++
src/input.c | 17 ++----
src/m4.h | 7 ++-
src/macro.c | 170 +++++++++++++++++++++++++++++++++++++++++++++--------------
4 files changed, 167 insertions(+), 52 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 6578264..62c4ad1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,28 @@
+2008-02-22 Eric Blake <address@hidden>
+
+ Stage 17: pass argv through quoted strings.
+ Allow the concatenation of $@ references with other text input
+ inside quoted contexts, which requires distinguishing between a
+ wrapper around many arguments vs. a reference serving as part of a
+ single argument. Also optimize based on whether argv contains
+ builtin tokens that might need flattening to the empty string.
+ Memory impact: noticeable improvement, due to O(n^2) to O(n)
+ reduction from total reuse of $@ references.
+ Speed impact: noticeable improvement, due to O(n^2) to O(n)
+ reduction in boxed recursion.
+ * src/input.c (append_quote_token): Allow an argv ref inside
+ quotes.
+ (init_argv_token): Populate new fields.
+ (push_macro): Ensure a macro is actually pushed.
+ * src/m4.h (struct token_chain): Add has_func member.
+ (struct token_data): Add wrapper and has_func members.
+ * src/macro.c (struct macro_arguments): Add flatten and has_func
+ members.
+ (expand_argument, collect_arguments, make_argv_ref_token)
+ (make_argv_ref): Populate new fields.
+ (arg_equal, arg_len) Handle embedded argv.
+ (arg_token, arg_mark, arg_type): Use new fields.
+
2008-02-21 Eric Blake <address@hidden>
Stage 16: cache quotes and improve arg_print.
diff --git a/src/input.c b/src/input.c
index bbd50f4..e2bf0aa 100644
--- a/src/input.c
+++ b/src/input.c
@@ -282,6 +282,7 @@ push_macro (builtin_func *func)
next = NULL;
}
+ assert (func);
i = (input_block *) obstack_alloc (current_input, sizeof *i);
i->type = INPUT_MACRO;
i->file = current_file;
@@ -1023,21 +1024,11 @@ append_quote_token (struct obstack *obs, token_data *td)
return;
}
- /* TODO preserve $@ through a quoted context. */
- if (src_chain->type == CHAIN_ARGV)
- {
- arg_print (obs, src_chain->u.u_a.argv, src_chain->u.u_a.index,
- quote_cache (NULL, src_chain->quote_age,
- src_chain->u.u_a.quotes),
- src_chain->u.u_a.flatten, NULL, NULL, false);
- arg_adjust_refcount (src_chain->u.u_a.argv, false);
- return;
- }
-
if (TOKEN_DATA_TYPE (td) == TOKEN_VOID)
{
TOKEN_DATA_TYPE (td) = TOKEN_COMP;
td->u.u_c.chain = td->u.u_c.end = NULL;
+ td->u.u_c.wrapper = td->u.u_c.has_func = false;
}
assert (TOKEN_DATA_TYPE (td) == TOKEN_COMP);
make_text_link (obs, &td->u.u_c.chain, &td->u.u_c.end);
@@ -1047,6 +1038,8 @@ append_quote_token (struct obstack *obs, token_data *td)
else
td->u.u_c.chain = chain;
td->u.u_c.end = chain;
+ if (chain->type == CHAIN_ARGV && chain->u.u_a.has_func)
+ td->u.u_c.has_func = true;
chain->next = NULL;
}
@@ -1073,6 +1066,8 @@ init_argv_token (struct obstack *obs, token_data *td)
/* Clone the link, since the input will be discarded soon. */
chain = (token_chain *) obstack_copy (obs, src_chain, sizeof *chain);
td->u.u_c.chain = td->u.u_c.end = chain;
+ td->u.u_c.wrapper = true;
+ td->u.u_c.has_func = chain->u.u_a.has_func;
chain->next = NULL;
/* If the next character is not ',' or ')', then unlink the last
diff --git a/src/m4.h b/src/m4.h
index 0c2a8c8..54deb42 100644
--- a/src/m4.h
+++ b/src/m4.h
@@ -311,6 +311,7 @@ struct token_chain
bool_bitfield flatten : 1; /* True to treat builtins as text. */
bool_bitfield comma : 1; /* True when `,' is next input. */
bool_bitfield skip_last : 1; /* True if last argument omitted. */
+ bool_bitfield has_func : 1; /* True if argv includes func. */
const string_pair *quotes; /* NULL for $*, quotes for
address@hidden */
}
u_a;
@@ -353,8 +354,10 @@ struct token_data
placeholders. */
struct
{
- token_chain *chain; /* First link of the chain. */
- token_chain *end; /* Last link of the chain. */
+ token_chain *chain; /* First link of the chain. */
+ token_chain *end; /* Last link of the chain. */
+ bool_bitfield wrapper : 1; /* True if this is a $@ ref. */
+ bool_bitfield has_func : 1; /* True if chain includes func. */
}
u_c;
}
diff --git a/src/macro.c b/src/macro.c
index 8b7e303..c0a24c4 100644
--- a/src/macro.c
+++ b/src/macro.c
@@ -49,6 +49,10 @@ struct macro_arguments
/* False if all arguments belong to this argv, true if some of them
include references to another. */
bool_bitfield has_ref : 1;
+ /* True to flatten builtins contained in references. */
+ bool_bitfield flatten : 1;
+ /* True if any token contains builtins. */
+ bool_bitfield has_func : 1;
const char *argv0; /* The macro name being expanded. */
size_t argv0_len; /* Length of argv0. */
/* The value of quote_age used when parsing all arguments in this
@@ -388,9 +392,14 @@ expand_argument (struct obstack *obs, token_data *argp,
const char *caller)
}
if (TOKEN_DATA_TYPE (argp) != TOKEN_COMP)
{
- obstack_1grow (obs, '\0');
TOKEN_DATA_TYPE (argp) = TOKEN_TEXT;
- TOKEN_DATA_TEXT (argp) = (char *) obstack_finish (obs);
+ if (len)
+ {
+ obstack_1grow (obs, '\0');
+ TOKEN_DATA_TEXT (argp) = (char *) obstack_finish (obs);
+ }
+ else
+ TOKEN_DATA_TEXT (argp) = NULL;
TOKEN_DATA_LEN (argp) = len;
TOKEN_DATA_QUOTE_AGE (argp) = age;
}
@@ -428,14 +437,16 @@ expand_argument (struct obstack *obs, token_data *argp,
const char *caller)
warn_builtin_concat (caller, TOKEN_DATA_FUNC (argp));
TOKEN_DATA_TYPE (argp) = TOKEN_COMP;
argp->u.u_c.chain = td.u.u_c.chain;
- argp->u.u_c.end = td.u.u_c.end;
+ argp->u.u_c.wrapper = argp->u.u_c.has_func = false;
}
else
{
assert (argp->u.u_c.end);
argp->u.u_c.end->next = td.u.u_c.chain;
- argp->u.u_c.end = td.u.u_c.end;
}
+ argp->u.u_c.end = td.u.u_c.end;
+ if (td.u.u_c.has_func)
+ argp->u.u_c.has_func = true;
}
break;
@@ -462,6 +473,8 @@ expand_argument (struct obstack *obs, token_data *argp,
const char *caller)
&& td.u.u_c.chain->type == CHAIN_ARGV);
TOKEN_DATA_TYPE (argp) = TOKEN_COMP;
argp->u.u_c.chain = argp->u.u_c.end = td.u.u_c.chain;
+ argp->u.u_c.wrapper = true;
+ argp->u.u_c.has_func = td.u.u_c.has_func;
t = next_token (&td, NULL, NULL, false, caller);
if (argp->u.u_c.chain->u.u_a.skip_last)
assert (t == TOKEN_COMMA);
@@ -501,6 +514,8 @@ collect_arguments (symbol *sym, struct obstack *arguments,
args.inuse = false;
args.wrapper = false;
args.has_ref = false;
+ args.flatten = !groks_macro_args;
+ args.has_func = false;
args.argv0 = SYMBOL_NAME (sym);
args.argv0_len = strlen (args.argv0);
args.quote_age = quote_age ();
@@ -526,23 +541,37 @@ collect_arguments (symbol *sym, struct obstack *arguments,
obstack_ptr_grow (argv_stack, tdp);
args.arraylen++;
args.argc++;
- /* Be conservative - any change in quoting while collecting
- arguments, or any argument that consists of unsafe text,
- will require a rescan if $@ is reused. */
- if (TOKEN_DATA_TYPE (tdp) == TOKEN_TEXT
- && TOKEN_DATA_LEN (tdp) > 0
- && TOKEN_DATA_QUOTE_AGE (tdp) != args.quote_age)
- args.quote_age = 0;
- else if (TOKEN_DATA_TYPE (tdp) == TOKEN_COMP)
+ switch (TOKEN_DATA_TYPE (tdp))
{
+ case TOKEN_TEXT:
+ /* Be conservative - any change in quoting while
+ collecting arguments, or any argument that consists
+ of unsafe text, will require a rescan if $@ is
+ reused. */
+ if (TOKEN_DATA_LEN (tdp) > 0
+ && TOKEN_DATA_QUOTE_AGE (tdp) != args.quote_age)
+ args.quote_age = 0;
+ break;
+ case TOKEN_FUNC:
+ args.has_func = true;
+ break;
+ case TOKEN_COMP:
args.has_ref = true;
- if (tdp->u.u_c.chain->type == CHAIN_ARGV)
+ if (tdp->u.u_c.wrapper)
{
+ assert (tdp->u.u_c.chain->type == CHAIN_ARGV
+ && !tdp->u.u_c.chain->next);
args.argc += (tdp->u.u_c.chain->u.u_a.argv->argc
- tdp->u.u_c.chain->u.u_a.index
- tdp->u.u_c.chain->u.u_a.skip_last - 1);
args.wrapper = true;
}
+ if (tdp->u.u_c.has_func)
+ args.has_func = true;
+ break;
+ default:
+ assert (!"expand_argument");
+ abort ();
}
}
while (more_args);
@@ -551,6 +580,7 @@ collect_arguments (symbol *sym, struct obstack *arguments,
argv->argc = args.argc;
argv->wrapper = args.wrapper;
argv->has_ref = args.has_ref;
+ argv->has_func = args.has_func;
if (args.quote_age != quote_age ())
argv->quote_age = 0;
argv->arraylen = args.arraylen;
@@ -802,12 +832,10 @@ arg_token (macro_arguments *argv, unsigned int index, int
*level)
for (i = 0; i < argv->arraylen; i++)
{
token = argv->array[i];
- if (TOKEN_DATA_TYPE (token) == TOKEN_COMP
- && token->u.u_c.chain->type == CHAIN_ARGV)
+ if (TOKEN_DATA_TYPE (token) == TOKEN_COMP && token->u.u_c.wrapper)
{
token_chain *chain = token->u.u_c.chain;
- /* TODO - for now we support only a single-length $@ chain. */
- assert (!chain->next);
+ assert (!chain->next && chain->type == CHAIN_ARGV);
if (index <= (chain->u.u_a.argv->argc - chain->u.u_a.index
- chain->u.u_a.skip_last))
{
@@ -840,15 +868,13 @@ arg_mark (macro_arguments *argv)
argv->inuse = true;
if (argv->wrapper)
for (i = 0; i < argv->arraylen; i++)
- if (TOKEN_DATA_TYPE (argv->array[i]) == TOKEN_COMP)
+ if (TOKEN_DATA_TYPE (argv->array[i]) == TOKEN_COMP
+ && argv->array[i]->u.u_c.wrapper)
{
chain = argv->array[i]->u.u_c.chain;
- while (chain)
- {
- if (chain->type == CHAIN_ARGV && !chain->u.u_a.argv->inuse)
- arg_mark (chain->u.u_a.argv);
- chain = chain->next;
- }
+ assert (!chain->next && chain->type == CHAIN_ARGV);
+ if (!chain->u.u_a.argv->inuse)
+ arg_mark (chain->u.u_a.argv);
}
}
@@ -867,14 +893,16 @@ arg_type (macro_arguments *argv, unsigned int index)
token_data_type type;
token_data *token;
- if (index == 0 || index >= argv->argc)
+ if (argv->flatten || !argv->has_func || index == 0 || index >= argv->argc)
return TOKEN_TEXT;
token = arg_token (argv, index, NULL);
type = TOKEN_DATA_TYPE (token);
- /* When accessed via the arg_* interface, composite tokens are
- currently sequences of text only. */
- if (type == TOKEN_COMP)
+ if (type == TOKEN_COMP && !token->u.u_c.has_func)
type = TOKEN_TEXT;
+ if (type != TOKEN_TEXT)
+ assert (argv->has_func);
+ /* TODO support TOKEN_COMP meaning concatenation of builtins. */
+ assert (type != TOKEN_COMP);
return type;
}
@@ -943,6 +971,7 @@ arg_equal (macro_arguments *argv, unsigned int indexa,
unsigned int indexb)
token_chain tmpb;
token_chain *ca = &tmpa;
token_chain *cb = &tmpb;
+ struct obstack *obs = arg_scratch ();
/* Quick tests. */
if (ta == &empty_token || tb == &empty_token)
@@ -983,7 +1012,34 @@ arg_equal (macro_arguments *argv, unsigned int indexa,
unsigned int indexb)
/* Compare each link of the chain. */
while (ca && cb)
{
- /* TODO support comparison against $@ refs. */
+ if (ca->type == CHAIN_ARGV)
+ {
+ tmpa.next = ca->next;
+ tmpa.type = CHAIN_STR;
+ /* TODO support $@ with funcs. */
+ assert (!ca->u.u_a.has_func || argv->flatten || ca->u.u_a.flatten);
+ arg_print (obs, ca->u.u_a.argv, ca->u.u_a.index,
+ quote_cache (NULL, ca->quote_age, ca->u.u_a.quotes),
+ argv->flatten || ca->u.u_a.flatten, NULL, NULL, false);
+ tmpa.u.u_s.len = obstack_object_size (obs);
+ tmpa.u.u_s.str = (char *) obstack_finish (obs);
+ ca = &tmpa;
+ continue;
+ }
+ if (cb->type == CHAIN_ARGV)
+ {
+ tmpb.next = cb->next;
+ tmpb.type = CHAIN_STR;
+ /* TODO support $@ with funcs. */
+ assert (!cb->u.u_a.has_func || argv->flatten || cb->u.u_a.flatten);
+ arg_print (obs, cb->u.u_a.argv, cb->u.u_a.index,
+ quote_cache (NULL, cb->quote_age, cb->u.u_a.quotes),
+ argv->flatten || cb->u.u_a.flatten, NULL, NULL, false);
+ tmpb.u.u_s.len = obstack_object_size (obs);
+ tmpb.u.u_s.str = (char *) obstack_finish (obs);
+ cb = &tmpb;
+ continue;
+ }
assert (ca->type == CHAIN_STR && cb->type == CHAIN_STR);
if (ca->u.u_s.len == cb->u.u_s.len)
{
@@ -1056,14 +1112,42 @@ arg_len (macro_arguments *argv, unsigned int index)
assert ((token == &empty_token) == (TOKEN_DATA_LEN (token) == 0));
return TOKEN_DATA_LEN (token);
case TOKEN_COMP:
- /* TODO - concatenate multiple arguments? For now, we assume
- all elements are text. */
chain = token->u.u_c.chain;
len = 0;
while (chain)
{
- assert (chain->type == CHAIN_STR);
- len += chain->u.u_s.len;
+ unsigned int i;
+ unsigned int limit;
+ const string_pair *quotes;
+ switch (chain->type)
+ {
+ case CHAIN_STR:
+ len += chain->u.u_s.len;
+ break;
+ case CHAIN_ARGV:
+ i = chain->u.u_a.index;
+ limit = chain->u.u_a.argv->argc - i - chain->u.u_a.skip_last;
+ quotes = quote_cache (NULL, chain->quote_age,
+ chain->u.u_a.quotes);
+ assert (limit);
+ if (quotes)
+ len += (quotes->len1 + quotes->len2) * limit;
+ len += limit - 1;
+ while (limit--)
+ {
+ /* TODO handle builtin concatenation. */
+ if (TOKEN_DATA_TYPE (arg_token (chain->u.u_a.argv, i,
+ NULL)) == TOKEN_FUNC)
+ assert (argv->flatten);
+ else
+ len += arg_len (chain->u.u_a.argv, i);
+ i++;
+ }
+ break;
+ default:
+ assert (!"arg_len");
+ abort ();
+ }
chain = chain->next;
}
assert (len);
@@ -1202,10 +1286,11 @@ make_argv_ref_token (token_data *token, struct obstack
*obs, int level,
token_chain *chain;
assert (obstack_object_size (obs) == 0);
+ /* TODO support $@ refs when argv array is larger than 1. */
if (argv->wrapper && argv->arraylen == 1)
{
- /* TODO for now we support only a single-length $@ chain. */
- assert (TOKEN_DATA_TYPE (argv->array[0]) == TOKEN_COMP);
+ assert (TOKEN_DATA_TYPE (argv->array[0]) == TOKEN_COMP
+ && argv->array[0]->u.u_c.wrapper);
chain = argv->array[0]->u.u_c.chain;
assert (!chain->next && chain->type == CHAIN_ARGV
&& !chain->u.u_a.skip_last);
@@ -1218,12 +1303,15 @@ make_argv_ref_token (token_data *token, struct obstack
*obs, int level,
chain = (token_chain *) obstack_alloc (obs, sizeof *chain);
TOKEN_DATA_TYPE (token) = TOKEN_COMP;
token->u.u_c.chain = token->u.u_c.end = chain;
+ token->u.u_c.wrapper = true;
+ token->u.u_c.has_func = argv->has_func;
chain->next = NULL;
chain->type = CHAIN_ARGV;
chain->quote_age = argv->quote_age;
chain->u.u_a.argv = argv;
chain->u.u_a.index = index;
chain->u.u_a.flatten = flatten;
+ chain->u.u_a.has_func = argv->has_func;
chain->u.u_a.comma = false;
chain->u.u_a.skip_last = false;
chain->u.u_a.quotes = quote_cache (obs, chain->quote_age, quotes);
@@ -1258,6 +1346,8 @@ make_argv_ref (macro_arguments *argv, const char *argv0,
size_t argv0_len,
new_argv->arraylen = 0;
new_argv->wrapper = false;
new_argv->has_ref = false;
+ new_argv->flatten = false;
+ new_argv->has_func = false;
}
else
{
@@ -1267,6 +1357,8 @@ make_argv_ref (macro_arguments *argv, const char *argv0,
size_t argv0_len,
new_argv->array[0] = token;
new_argv->wrapper = true;
new_argv->has_ref = argv->has_ref;
+ new_argv->flatten = flatten;
+ new_argv->has_func = argv->has_func;
}
new_argv->argc = argv->argc - (index - 1);
new_argv->inuse = false;
@@ -1314,10 +1406,10 @@ push_arg_quote (struct obstack *obs, macro_arguments
*argv, unsigned int index,
obstack_grow (obs, quotes->str2, quotes->len2);
}
-/* Push series of comma-separated arguments from ARGV, which should
- all be text, onto the expansion stack OBS for rescanning. If SKIP,
- then don't push the first argument. If QUOTE, the rescan also
- includes quoting around each arg. */
+/* Push series of comma-separated arguments from ARGV, which can
+ include builtins, onto the expansion stack OBS for rescanning. If
+ SKIP, then don't push the first argument. If QUOTE, the rescan
+ also includes quoting around each arg. */
void
push_args (struct obstack *obs, macro_arguments *argv, bool skip, bool quote)
{
--
1.5.4
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [17/18] argv_ref speedup: reuse $@ inside quoted strings,
Eric Blake <=