Sort class arrays of parcels Some of the code generators require that parent classes are processed before subclasses. Sort the class array accordingly when building the hierarchy.
Also sort subclasses by class name to guarantee a consistent order. This should make the CFC output completely deterministic. (Except for output that depends on the order of parcels in the global parcel registry. I think the only example is the Perl typemap.) Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/e5b89002 Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/e5b89002 Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/e5b89002 Branch: refs/heads/master Commit: e5b89002ee752aee8563a953b530d4ddafddcf85 Parents: 22e055c Author: Nick Wellnhofer <wellnho...@aevum.de> Authored: Sun Feb 26 23:11:47 2017 +0100 Committer: Nick Wellnhofer <wellnho...@aevum.de> Committed: Thu Mar 2 20:08:03 2017 +0100 ---------------------------------------------------------------------- compiler/src/CFCHierarchy.c | 3 ++ compiler/src/CFCParcel.c | 75 ++++++++++++++++++++++++++++++++++++++++ compiler/src/CFCParcel.h | 10 ++++++ 3 files changed, 88 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/e5b89002/compiler/src/CFCHierarchy.c ---------------------------------------------------------------------- diff --git a/compiler/src/CFCHierarchy.c b/compiler/src/CFCHierarchy.c index 19a45ec..86ad2cc 100644 --- a/compiler/src/CFCHierarchy.c +++ b/compiler/src/CFCHierarchy.c @@ -256,6 +256,9 @@ CFCHierarchy_build(CFCHierarchy *self) { for (size_t i = 0; self->trees[i] != NULL; i++) { CFCClass_grow_tree(self->trees[i]); } + for (size_t i = 0; parcels[i] != NULL; i++) { + CFCParcel_sort_classes(parcels[i]); + } FREEMEM(source_parcels); } http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/e5b89002/compiler/src/CFCParcel.c ---------------------------------------------------------------------- diff --git a/compiler/src/CFCParcel.c b/compiler/src/CFCParcel.c index 2c134c5..96d5de8 100644 --- a/compiler/src/CFCParcel.c +++ b/compiler/src/CFCParcel.c @@ -609,6 +609,76 @@ CFCParcel_add_class(CFCParcel *self, CFCClass *klass) { self->num_classes = num_classes + 1; } +static int +S_compare_class_name(const void *va, const void *vb) { + const char *a = CFCClass_get_name(*(CFCClass**)va); + const char *b = CFCClass_get_name(*(CFCClass**)vb); + + return strcmp(a, b); +} + +void +CFCParcel_sort_classes(CFCParcel *self) { + size_t num_classes = self->num_classes; + size_t alloc_size = (num_classes + 1) * sizeof(CFCClass*); + CFCClass **classes = self->classes; + CFCClass **sorted = (CFCClass**)MALLOCATE(alloc_size); + + // Perform a depth-first search of the classes in the parcel, and store + // the classes in the order that they were visited. This makes sure + // that subclasses are sorted after their parents. + // + // To avoid a recursive algorithm, the end of the sorted array is used + // as a stack for classes that have yet to be visited. + // + // Root and child classes are sorted by name to get a deterministic + // order. + + // Find subtree roots in parcel. + size_t todo = num_classes; + for (size_t i = 0; i < num_classes; i++) { + CFCClass *klass = classes[i]; + CFCClass *parent = CFCClass_get_parent(klass); + if (!parent || !CFCClass_in_parcel(parent, self)) { + sorted[--todo] = klass; + } + } + + qsort(&sorted[todo], num_classes - todo, sizeof(sorted[0]), + S_compare_class_name); + + size_t num_sorted = 0; + while (todo < num_classes) { + CFCClass *klass = sorted[todo++]; + sorted[num_sorted++] = klass; + + // Find children in parcel. + CFCClass **children = CFCClass_children(klass); + size_t prev_todo = todo; + for (size_t i = 0; children[i]; i++) { + CFCClass *child = children[i]; + if (CFCClass_in_parcel(child, self)) { + if (todo <= num_sorted) { + CFCUtil_die("Internal error in CFCParcel_sort_classes"); + } + sorted[--todo] = child; + } + } + + qsort(&sorted[todo], prev_todo - todo, sizeof(sorted[0]), + S_compare_class_name); + } + + if (num_sorted != num_classes) { + CFCUtil_die("Internal error in CFCParcel_sort_classes"); + } + + sorted[num_classes] = NULL; + + FREEMEM(self->classes); + self->classes = sorted; +} + static CFCParcel* S_lookup_struct_sym(CFCParcel *self, const char *struct_sym) { for (size_t i = 0; self->classes[i]; ++i) { @@ -647,6 +717,11 @@ CFCParcel_is_cfish(CFCParcel *self) { return !strcmp(self->prefix, "cfish_"); } +CFCClass** +CFCParcel_get_classes(CFCParcel *self) { + return self->classes; +} + /**************************************************************************/ struct CFCPrereq { http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/e5b89002/compiler/src/CFCParcel.h ---------------------------------------------------------------------- diff --git a/compiler/src/CFCParcel.h b/compiler/src/CFCParcel.h index c8adbc9..0c02a48 100644 --- a/compiler/src/CFCParcel.h +++ b/compiler/src/CFCParcel.h @@ -179,6 +179,16 @@ CFCParcel_read_host_data_json(CFCParcel *self, const char *host_lang); void CFCParcel_add_class(CFCParcel *self, struct CFCClass *klass); +/** Sort parents before child classes. + */ +void +CFCParcel_sort_classes(CFCParcel *self); + +/** Return the ordered list of classes in the parcel. + */ +struct CFCClass** +CFCParcel_get_classes(CFCParcel *self); + /** Search the parcel and all direct prerequisites for a class with * struct_sym. Return the parcel in which the class was found or NULL. */
