scripts/gen-tree.awk

   1 #!/bin/awk -f
   2 #
   3 # Copyright © 2021-2022 Nick Bowler
   4 #
   5 # Generate one or more C array initializers to encode simple tree structures
   6 # in a compact format.
   7 #
   8 # Each nonempty line of the input file is either a comment, an option
   9 # specification or a tree specification.  Each line is distinguished by
  10 # its first character.  A # character introduces a comment, an @ character
  11 # introduces an option specification (described later), and all other
  12 # nonempty lines are tree nodes.
  13 #
  14 # The first field of a tree specification must be a valid C identifier,
  15 # optionally followed by a comma.  The identifiers used on non-leaf nodes
  16 # must be unique with respect to other non-leaf nodes, but leaf nodes may
  17 # share the same identifier as other nodes.
  18 #
  19 # The tree structure is expressed through indentation.  Lines with no leading
  20 # whitespace designate root nodes.  When the number of white-space characters
  21 # at the beginning of a line is greater than that of the previous line, this
  22 # introduces a new subtree rooted at the previous node.  When the number of
  23 # leading white-space characters is less than the previous line, this concludes
  24 # the definition of the current subtree.
  25 #
  26 # For example, the input on the left describes the tree on the right.
  27 #
  28 #    INPUT: root           TREE: root -- a -- b -- c
  29 #              a                    |    |
  30 #                 b                 |    + -- d
  31 #                    c              |
  32 #                 d                 + -- e -- f
  33 #              e                         |
  34 #                 f                      + -- g
  35 #                 g
  36 #
  37 # For each root node X, the object-like macro X_INITIALIZER is defined.  This
  38 # can be used to initialize an array with static storage duration.  Each line
  39 # of the input is defines the initializer for one array element.  These are
  40 # then ordered topologically beginning with the root, but the root itself is
  41 # not included.  Each subtree is terminated by an "empty" element (with an
  42 # initializer of {0}).
  43 #
  44 # If there is a comma after the identifier which begins a tree element, or
  45 # if the identifier is the only text on the line, then the element initializer
  46 # is constructed by surrounding the entire line by braces.  Otherwise, the
  47 # identifier is removed and the remainder of the line is surrounded by braces
  48 # to construct the initializer.  This allows the exact form of the initializer
  49 # to be customized.
  50 #
  51 # For example, the above input will produce this (or an equivalent topological
  52 # ordering) initializer:
  53 #
  54 #    OUTPUT: #define root_INITIALIZER \
  55 #                 {a}, {e}, {0}, {b}, {d}, {0}, {f}, {g}, {0}, {c}, {0}
  56 #
  57 # Constants representing the array offset for each subtree are additionally
  58 # defined.  For a non-leaf node X, the enumeration constant X_OFFSET gives the
  59 # index of the first node rooted at X.  With the above example, the results
  60 # are:
  61 #
  62 #    OUTPUT: enum { a_OFFSET = 3, b_OFFSET = 9, e_OFFSET = 6 };
  63 #
  64 # By using an array of structures to represent the tree and including these
  65 # constants in initializers, it is possible for the flattened tree to describe
  66 # its own structure.
  67 #
  68 # Finally, each node identifier is defined as an enumeration constant
  69 # representing the nonzero offset into a string table tree_strtab.  These
  70 # constants will normally be in scope when using the root_INITIALIZER macro,
  71 # which means the resulting array initializers will use them.
  72 #
  73 # Options may be used to alter the normal behaviour.  They may be placed
  74 # anywhere in the input file.  The following options are defined:
  75 #
  76 #   @nostrtab
  77 #     Do not output a definition for tree_strtab or its associated
  78 #     enumeration constants.
  79 #
  80 # License WTFPL2: Do What The Fuck You Want To Public License, version 2.
  81 # This is free software: you are free to do what the fuck you want to.
  82 # There is NO WARRANTY, to the extent permitted by law.
  83
  84 END {
  85   print "/*"
  86   if (FILENAME) {
  87     print " * Automatically generated by gen-tree.awk from " FILENAME
  88   } else {
  89     print " * Automatically generated by gen-tree.awk"
  90   }
  91   print " * Do not edit."
  92   print " */"
  93 }
  94
  95 BEGIN {
  96   # Check if "\\\\" in substitutions gives just one backslash.
  97   bs = "x"; sub(/x/, "\\\\", bs);
  98   bs = (length(bs) == 1 ? "\\\\" : "\\");
  99
 100   opts["strtab"] = 1;
 101
 102   depth = max_depth = 0;
 103   num_entries = 0;
 104
 105   tree_name = "";
 106   entry_name = "";
 107
 108   indent_stack[0] = 0;
 109 }
 110
 111 # Comments
 112 NF == 0 { next }
 113 $0 ~ /^#/ { next }
 114
 115 # Options
 116 sub(/^@/, "", $0) {
 117   if (NF == 1) {
 118     orig=$1
 119     gsub(/-/, "_", $1);
 120     val = !sub(/^no_?/, "", $1);
 121     if ($1 in opts) {
 122       opts[$1] = val;
 123     } else {
 124       print "error: unrecognized option: @" orig | "cat 1>&2"
 125       exit 1
 126     }
 127   }
 128   next
 129 }
 130
 131 { indent = index($0, $1) - 1 }
 132
 133 indent > 0 {
 134   if (indent > indent_stack[depth]) {
 135     indent_stack[++depth] = indent;
 136     if (depth > 1) {
 137       subtree_offsets[entry_name] = level_count[depth];
 138       subtree_depth[entry_name] = depth;
 139     }
 140   } else {
 141     while (indent < indent_stack[depth]) {
 142       tree_items[depth] = tree_items[depth] ", \\\n\t{ 0 }";
 143       level_count[depth]++;
 144       depth--;
 145     }
 146   }
 147
 148   entry_name = $1; sub(/,$/, "", entry_name);
 149   all_items[num_entries++] = entry_name;
 150
 151   # Construct the element initializer for this tree node.
 152   $1 = " " $1;
 153   if (NF > 1) {
 154     # Check if entry name is followed by a comma.  If it is not, the entry
 155     # name is excluded from the initializer.
 156     check_str = $1$2;
 157     gsub(/[ \t]/, "", check_str);
 158     if (index(check_str, entry_name ",") == 0) {
 159       $1 = "";
 160     }
 161   }
 162   $1 = ", \\\n\t{" $1; $NF = $NF " }";
 163
 164   tree_items[depth] = tree_items[depth] $0;
 165   level_count[depth]++;
 166 }
 167
 168 indent == 0 && tree_identifier != "" {
 169   trees[tree_identifier] = format_items();
 170   tree_identifier = "";
 171 }
 172 END {
 173   if (tree_identifier != "")
 174     trees[tree_identifier] = format_items()
 175 }
 176 indent == 0 { tree_identifier = $1 }
 177
 178 END {
 179   prefix = "\nenum {\n";
 180
 181   if (opts["strtab"]) {
 182     entry_strtab = "\1";
 183     bucketsort(sorted_items, all_items);
 184     for (i = 0; i < num_entries; i++) {
 185       s = sorted_items[i];
 186       if ((n = index(entry_strtab, s "\1")) > 0) {
 187         entry_offsets[s] = n-1;
 188       } else {
 189         entry_offsets[s] = length(entry_strtab);
 190         entry_strtab = entry_strtab s "\1";
 191       }
 192     }
 193
 194     gsub("\1", "\"\n\t\"" bs "0\" \"", entry_strtab);
 195     sub(/^"/, "", entry_strtab);
 196     sub(/\n[^\n]*$/, ";", entry_strtab);
 197     print "\nstatic const char tree_strtab[] =" entry_strtab
 198
 199     for (item in entry_offsets) {
 200       printf "%s\t%s = %d", prefix, item, entry_offsets[item];
 201       prefix = ",\n";
 202     }
 203   }
 204
 205   for (i in subtree_offsets) {
 206     printf "%s\t%s_OFFSET = %d", prefix, i, subtree_offsets[i];
 207     prefix = ",\n";
 208   }
 209   if (!index(prefix, "enum")) {
 210     print "\n};";
 211   }
 212 }
 213
 214 END {
 215   for (tree in trees) {
 216     print "\n" trees[tree];
 217   }
 218 }
 219
 220 function format_items(s, i)
 221 {
 222   while (depth > 0) {
 223     tree_items[depth] = tree_items[depth] ", \\\n\t{ 0 }";
 224     level_count[depth]++;
 225     depth--;
 226   }
 227
 228   for (i = 2; tree_items[i] != ""; i++) {
 229     level_count[i] += level_count[i-1];
 230   }
 231
 232   for (i in subtree_depth) {
 233     subtree_offsets[i] += level_count[subtree_depth[i]-1];
 234     delete subtree_depth[i];
 235   }
 236
 237   for (i = 1; tree_items[i] != ""; i++) {
 238     s = s tree_items[i];
 239     delete tree_items[i];
 240     delete level_count[i];
 241   }
 242
 243   sub(/^,/, "", s);
 244   return "#define " tree_identifier "_INITIALIZER" s;
 245 }
 246
 247 # bucketsort(dst, src)
 248 #
 249 # Sort the elements of src by descending string length,
 250 # placing them into dst[0] ... dst[n].
 251 #
 252 # Returns the number of elements.
 253 function bucketsort(dst, src, max, count, i, t)
 254 {
 255   # Note: ULTRIX 4.5 nawk does not support local array parameters
 256   split("", bucketsort_buckets);
 257
 258   for (t in src) {
 259     i = length(src[t])
 260     if (i > max) { max = i }
 261     bucketsort_buckets[i]++
 262   }
 263
 264   for (i = max; i > 0; i--) {
 265     if (i in bucketsort_buckets) {
 266       t = bucketsort_buckets[i]
 267       bucketsort_buckets[i] = count
 268       count += t
 269     }
 270   }
 271
 272   for (t in src) {
 273     i = length(t = src[t])
 274     dst[bucketsort_buckets[i]++] = t
 275   }
 276
 277   return count
 278 }