generator: Generators for C
authorDavid Gibson <david@gibson.dropbear.id.au>
Thu, 25 Feb 2016 11:07:17 +0000 (22:07 +1100)
committerDavid Gibson <david@gibson.dropbear.id.au>
Thu, 25 Feb 2016 11:07:17 +0000 (22:07 +1100)
Generators are a limited form of co-routine, which people may be familiar
with from Python.  This module adds an implementation of generators for C.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
13 files changed:
Makefile-ccan
ccan/generator/LICENSE [new symlink]
ccan/generator/_info [new file with mode: 0644]
ccan/generator/generator.c [new file with mode: 0644]
ccan/generator/generator.h [new file with mode: 0644]
ccan/generator/test/api.c [new file with mode: 0644]
ccan/generator/test/compile_fail-1.c [new file with mode: 0644]
ccan/generator/test/compile_fail-2.c [new file with mode: 0644]
ccan/generator/test/compile_fail-3.c [new file with mode: 0644]
ccan/generator/test/compile_fail-4.c [new file with mode: 0644]
ccan/generator/test/compile_fail-5.c [new file with mode: 0644]
ccan/generator/test/example-gens.c [new file with mode: 0644]
ccan/generator/test/example-gens.h [new file with mode: 0644]

index 2c80720c9595af367c49c391b78cf43515f132ef..a0be58f8c2d93acfe2ffdc8111423cf2a8aebd54 100644 (file)
@@ -64,6 +64,7 @@ MODS_WITH_SRC := aga \
        err \
        failtest \
        foreach \
+       generator \
        grab_file \
        hash \
        heap \
diff --git a/ccan/generator/LICENSE b/ccan/generator/LICENSE
new file mode 120000 (symlink)
index 0000000..dc314ec
--- /dev/null
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/generator/_info b/ccan/generator/_info
new file mode 100644 (file)
index 0000000..a6570e3
--- /dev/null
@@ -0,0 +1,71 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * generator - generators for C
+ *
+ * Generators are a limited form of coroutines, which provide a useful
+ * way of expressing certain problems, while being much simpler to
+ * understand than general coroutines.
+ *
+ * Instead of returning a single value, a generator can "yield" a
+ * value at various points during its execution.  Whenever it yields,
+ * the "calling" function resumes and obtains the newly yielded value
+ * to work with.  When the caller asks for the next value from the
+ * generator, the generator resumes execution from the last yield and
+ * continues onto the next.
+ *
+ * Example:
+ *     #include <stdio.h>
+ *     #include <ccan/generator/generator.h>
+ *
+ *     generator_def_static(simple_gen, int)
+ *     {
+ *             generator_yield(1);
+ *             generator_yield(3);
+ *             generator_yield(17);
+ *     }
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             generator_t(int) gen = simple_gen();
+ *             int *ret;
+ *
+ *             while ((ret = generator_next(gen)) != NULL) {
+ *                     printf("Generator returned %d\n", *ret);
+ *             }
+ *
+ *             return 0;
+ *     }
+ *
+ * Author: David Gibson <david@gibson.dropbear.id.au>
+ * License: LGPL (v2.1 or any later version)
+ *
+ * Ccanlint:
+ *      // We need several gcc extensions
+ *     objects_build_without_features FAIL
+ *      tests_compile_without_features FAIL
+ *     tests_helpers_compile_without_features FAIL
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/build_assert\n");
+               printf("ccan/ptrint\n");
+               printf("ccan/alignof\n");
+               printf("ccan/cppmagic\n");
+               return 0;
+       }
+
+       if (strcmp(argv[1], "testdepends") == 0) {
+               printf("ccan/str\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/generator/generator.c b/ccan/generator/generator.c
new file mode 100644 (file)
index 0000000..d217665
--- /dev/null
@@ -0,0 +1,54 @@
+/* Licensed LGPLv2.1+ - see LICENSE file for details */
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#include <ccan/alignof/alignof.h>
+
+#include <ccan/generator/generator.h>
+
+#define DEFAULT_STATE_SIZE     8192
+#define STATE_ALIGN            ALIGNOF(struct generator_)
+
+void *generator_new_(generator_wrapper_ *fn, size_t retsize)
+{
+       char *base;
+       size_t size = DEFAULT_STATE_SIZE;
+       void *ret;
+       struct generator_ *gen;
+
+       base = malloc(size);
+       if (!base)
+               abort();
+
+       retsize = (retsize + STATE_ALIGN) & ~(STATE_ALIGN - 1);
+       ret = base + size - retsize;
+       gen = (struct generator_ *)ret - 1;
+
+       gen->base = base;
+       gen->complete = false;
+
+       getcontext(&gen->gen);
+
+       gen->gen.uc_stack.ss_sp = gen->base;
+       gen->gen.uc_stack.ss_size = (char *)gen - base;
+
+       if (HAVE_POINTER_SAFE_MAKECONTEXT) {
+               makecontext(&gen->gen, (void *)fn, 1, ret);
+       } else {
+               ptrdiff_t si = ptr2int(ret);
+               ptrdiff_t mask = (1UL << (sizeof(int) * 8)) - 1;
+               int lo = si & mask;
+               int hi = si >> (sizeof(int) * 8);
+
+               makecontext(&gen->gen, (void *)fn, 2, lo, hi);
+       }
+
+       return ret;
+}
+
+void generator_free_(void *ret)
+{
+       struct generator_ *gen = generator_state_(ret);
+       free(gen->base);
+}
diff --git a/ccan/generator/generator.h b/ccan/generator/generator.h
new file mode 100644 (file)
index 0000000..6b2bd92
--- /dev/null
@@ -0,0 +1,202 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#ifndef CCAN_GENERATOR_H
+#define CCAN_GENERATOR_H
+#include "config.h"
+
+#if !HAVE_UCONTEXT
+#error Generators require working ucontext.h functions
+#endif
+
+#if !HAVE_TYPEOF
+#error Generators require typeof
+#endif
+
+#if !HAVE_STATEMENT_EXPR
+#error Generators require statement expressions
+#endif
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdbool.h>
+#include <ucontext.h>
+
+#include <ccan/ptrint/ptrint.h>
+#include <ccan/build_assert/build_assert.h>
+#include <ccan/cppmagic/cppmagic.h>
+
+/*
+ * Internals - included just for the use of inlines and macros
+ */
+
+struct generator_ {
+       ucontext_t gen;
+       ucontext_t caller;
+       bool complete;
+       void *base;
+};
+
+static inline struct generator_ *generator_state_(const void *ret)
+{
+       return (struct generator_ *)ret - 1;
+}
+
+struct generator_incomplete_;
+
+#define generator_rtype_(gen_)                 \
+       typeof((*(gen_))((struct generator_incomplete_ *)NULL))
+
+#if HAVE_POINTER_SAFE_MAKECONTEXT
+#define generator_wrapper_args_()      void *ret
+#else
+#define generator_wrapper_args_()      int lo, int hi
+#endif
+typedef void generator_wrapper_(generator_wrapper_args_());
+
+void *generator_new_(generator_wrapper_ *fn, size_t retsize);
+void generator_free_(void *ret);
+
+/*
+ * API
+ */
+
+/**
+ * generator_t - type for an in-progress generator
+ * @rtype: type of values the generator yield
+ */
+#define generator_t(rtype_)                    \
+       typeof(rtype_ (*)(struct generator_incomplete_ *))
+
+/**
+ * generator_declare - declare (but don't define) a generator function
+ * @name: name for the generator
+ * @rtype: return type for the generator
+ *
+ * Declares (as an extern) a generator function named @name, which
+ * will yield return values of type @rtype.
+ *
+ * Example:
+ *     generator_declare(count_to_3, int);
+ */
+#define generator_declare(name_, rtype_)       \
+       generator_t(rtype_) name_(void)
+
+/**
+ * generator_def - define a generator function
+ * @name: name for the generator
+ * @rtype: return type for the generator
+ *
+ * Define a generator function named @name yielding return values of
+ * type @rtype.  The generator_def() line is followed immediately by a
+ * block containing the generator's code.
+ *
+ * Example:
+ *     generator_def(count_to_3, int)
+ *     {
+ *             generator_yield(1);
+ *             generator_yield(2);
+ *             generator_yield(3);
+ *     }
+ */
+#define generator_def_(name_, rtype_, storage_)                                \
+       static void name_##_generator_(rtype_ *ret_);                   \
+       static void name_##_generator__(generator_wrapper_args_())      \
+       {                                                               \
+               struct generator_ *gen;                                 \
+               CPPMAGIC_IFELSE(HAVE_POINTER_SAFE_MAKECONTEXT)          \
+                       ()                                              \
+                       (ptrdiff_t hilo = ((ptrdiff_t)hi << (8*sizeof(int))) \
+                               + (ptrdiff_t)lo;                        \
+                       rtype_ *ret = (rtype_ *)int2ptr(hilo);          \
+                       BUILD_ASSERT(sizeof(struct generator_ *)        \
+                                    <= 2*sizeof(int));)                \
+               gen = generator_state_(ret);                            \
+               name_##_generator_(ret);                                \
+               gen->complete = true;                                   \
+               setcontext(&gen->caller);                               \
+               assert(0);                                              \
+       }                                                               \
+       storage_ generator_t(rtype_) name_(void)                        \
+       {                                                               \
+               return generator_new_(name_##_generator__,              \
+                                     sizeof(rtype_));                  \
+       }                                                               \
+       static void name_##_generator_(rtype_ *ret_)
+#define generator_def(name_, rtype_)           \
+       generator_def_(name_, rtype_, )
+
+/**
+ * generator_def_static - define a private / local generator function
+ * @name: name for the generator
+ * @rtype: return type for the generator
+ *
+ * As generator_def, but the resulting generator function will be
+ * local to this module.
+ */
+#define generator_def_static(name_, rtype_)    \
+       generator_def_(name_, rtype_, static)
+
+/**
+ * generator_yield - yield (return) a value from a generator
+ * @val: value to yield
+ *
+ * Invoke only from within a generator.  Yield the given value to the
+ * caller.  This will stop execution of the generator code until the
+ * caller next invokes generator_next(), at which point it will
+ * continue from the generator_yield statement.
+ */
+#define generator_yield(val_)                                          \
+       do {                                                            \
+               struct generator_ *gen_ = generator_state_(ret_);       \
+               int rc;                                                 \
+               *(ret_) = (val_);                                       \
+               rc = swapcontext(&gen_->gen, &gen_->caller);            \
+               assert(rc == 0);                                        \
+       } while (0)
+
+/**
+ * generator_next - get next value from a generator
+ * @gen: a generator state variable
+ *
+ * Returns a pointer to a (correctly typed) buffer containing the next
+ * value yielded by @gen, or NULL if @gen is finished.  The buffer
+ * contents is only valid until the next time @gen is called or
+ * manipulated.
+ */
+static inline void *generator_next_(void *ret_)
+{
+       struct generator_ *gen = generator_state_(ret_);
+       int rc;
+
+       if (gen->complete)
+               return NULL;
+
+       rc = swapcontext(&gen->caller, &gen->gen);
+       assert(rc == 0);
+
+       return gen->complete ? NULL : ret_;
+}
+#define generator_next(gen_)                           \
+       ((generator_rtype_(gen_) *)generator_next_(gen_))
+
+/**
+ * generator_next_val - store next value from a generator
+ * @val: a variable of type suitable to store the generator's return
+ *       type (lvalue)
+ * @gen: a generator state variable
+ *
+ * Returns 'true' if @gen yielded a new value, false if @gen is
+ * complete.  If a new value was yielded, it is stored in @val.
+ */
+#define generator_next_val(val_, gen_)                 \
+       ({                                              \
+               generator_rtype_(gen_) *ret;            \
+               ret = generator_next(gen_);             \
+               if (ret)                                \
+                       (val_) = *ret;                  \
+               !!ret;                                  \
+       })
+
+#define generator_free(gen_)                                   \
+       generator_free_((generator_rtype_(gen_) *)(gen_))
+
+#endif /* CCAN_GENERATOR_H */
diff --git a/ccan/generator/test/api.c b/ccan/generator/test/api.c
new file mode 100644 (file)
index 0000000..a5770fd
--- /dev/null
@@ -0,0 +1,62 @@
+#include <ccan/generator/generator.h>
+#include <ccan/tap/tap.h>
+#include <ccan/str/str.h>
+
+#include "example-gens.h"
+
+generator_def_static(genx, const char *)
+{
+       generator_yield("one");
+       generator_yield("two");
+       generator_yield("three");
+       generator_yield("four");
+}
+
+static void test1(void)
+{
+       generator_t(int) state1 = gen1();
+       int *ret;
+
+       ok1((ret = generator_next(state1)) != NULL);
+       ok1(*ret == 1);
+       ok1((ret = generator_next(state1)) != NULL);
+       ok1(*ret == 3);
+       ok1((ret = generator_next(state1)) != NULL);
+       ok1(*ret == 17);
+       ok1((ret = generator_next(state1)) == NULL);
+
+       /* Test that things don't go bad if we try to invoke an
+        * already completed generator */
+       ok1((ret = generator_next(state1)) == NULL);
+
+       generator_free(state1);
+}
+
+static void testx(void)
+{
+       generator_t(const char *) statex = genx();
+       const char *val;
+
+       ok1(generator_next_val(val, statex));
+       ok1(streq(val, "one"));
+       ok1(generator_next_val(val, statex));
+       ok1(streq(val, "two"));
+       ok1(generator_next_val(val, statex));
+       ok1(streq(val, "three"));
+       ok1(generator_next_val(val, statex));
+       ok1(streq(val, "four"));
+       ok1(!generator_next_val(val, statex));
+       generator_free(statex);
+}
+
+int main(void)
+{
+       /* This is how many tests you plan to run */
+       plan_tests(8 + 9);
+
+       test1();
+       testx();
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}
diff --git a/ccan/generator/test/compile_fail-1.c b/ccan/generator/test/compile_fail-1.c
new file mode 100644 (file)
index 0000000..38e623a
--- /dev/null
@@ -0,0 +1,21 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <ccan/generator/generator.h>
+
+#include <ccan/generator/generator.c>
+
+#include "example-gens.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+       int *g = gen1();
+#else
+       generator_t(int) g = gen1();
+#endif
+
+       printf("%d", *generator_next(g));
+
+       exit(0);
+}
diff --git a/ccan/generator/test/compile_fail-2.c b/ccan/generator/test/compile_fail-2.c
new file mode 100644 (file)
index 0000000..7f24131
--- /dev/null
@@ -0,0 +1,21 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <ccan/generator/generator.h>
+
+#include <ccan/generator/generator.c>
+
+#include "example-gens.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+       generator_t(char) g = gen1();
+#else
+       generator_t(int) g = gen1();
+#endif
+
+       printf("%d", *generator_next(g));
+
+       exit(0);
+}
diff --git a/ccan/generator/test/compile_fail-3.c b/ccan/generator/test/compile_fail-3.c
new file mode 100644 (file)
index 0000000..9347efc
--- /dev/null
@@ -0,0 +1,24 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <ccan/generator/generator.h>
+
+#include <ccan/generator/generator.c>
+
+generator_def_static(intgen, int)
+{
+#ifdef FAIL
+       generator_yield("a");
+#else
+       generator_yield(1);
+#endif
+}
+
+int main(int argc, char *argv[])
+{
+       generator_t(int) g = intgen();
+
+       printf("%d", *generator_next(g));
+
+       exit(0);
+}
diff --git a/ccan/generator/test/compile_fail-4.c b/ccan/generator/test/compile_fail-4.c
new file mode 100644 (file)
index 0000000..f7297cf
--- /dev/null
@@ -0,0 +1,23 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <ccan/generator/generator.h>
+
+#include <ccan/generator/generator.c>
+
+#include "example-gens.h"
+
+int main(int argc, char *argv[])
+{
+       generator_t(int) g = gen1();
+#ifdef FAIL
+       char *val;
+#else
+       int val;
+#endif
+
+       generator_next_val(val, g);
+       printf("%d", val);
+
+       exit(0);
+}
diff --git a/ccan/generator/test/compile_fail-5.c b/ccan/generator/test/compile_fail-5.c
new file mode 100644 (file)
index 0000000..ba8ced9
--- /dev/null
@@ -0,0 +1,21 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <ccan/generator/generator.h>
+
+#include <ccan/generator/generator.c>
+
+#include "example-gens.h"
+
+int main(int argc, char *argv[])
+{
+#ifdef FAIL
+       int *g = NULL;
+#else
+       generator_t(int) g = gen1();
+#endif
+
+       generator_free(g);
+
+       exit(0);
+}
diff --git a/ccan/generator/test/example-gens.c b/ccan/generator/test/example-gens.c
new file mode 100644 (file)
index 0000000..c554011
--- /dev/null
@@ -0,0 +1,10 @@
+#include <ccan/generator/generator.h>
+
+#include "example-gens.h"
+
+generator_def(gen1, int)
+{
+       generator_yield(1);
+       generator_yield(3);
+       generator_yield(17);
+}
diff --git a/ccan/generator/test/example-gens.h b/ccan/generator/test/example-gens.h
new file mode 100644 (file)
index 0000000..cf4ce3b
--- /dev/null
@@ -0,0 +1,8 @@
+#ifndef _EXAMPLE_GENS_H
+#define _EXAMPLE_GENS_H
+
+#include <ccan/generator/generator.h>
+
+generator_declare(gen1, int);
+
+#endif /* _EXAMPLE_GENS_H */