libcdecl: Replace yytname array in the Bison parser.

[cdecl99.git] / src / fix-yytname.awk

#!/bin/awk -f
#
# Copyright © 2023 Nick Bowler
#
# Hackjob to improve the horrible yytname array generated by Bison.
#
# Bison generates a list of symbol names as a static array of char pointers
# initialized with string literals, which is simply horrible.  These pointers
# are two to four times larger than necessary, but with position-independent
# code this also forces them into an unshareable, writeable segment since
# they are not compile-time constants and must be initialized by the dynamic
# loader at runtime.
#
# Furthermore, the names of nonterminal symbols are always included but they
# are not always needed; they should only be output by tracing code which
# is disabled by default at compile time.
#
# This script replaces the definition of the yytname array with a function
# that implements the same lookup using truly constant tables, and makes the
# inclusion of nonterminal symbols in these tables conditional on YYDEBUG.
#
# License WTFPL2: Do What The Fuck You Want To Public License, version 2.
# This is free software: you are free to do what the fuck you want to.
# There is NO WARRANTY, to the extent permitted by law.

BEGIN {
  in_table   = 0;
  num_tokens = 0;
  num_nterms = 0;
}

# Locate YYNTOKENS definition, needed to distinguish terminal symbols
# from nonterminals.
$1 == "#define" && $2 == "YYNTOKENS" { yyntokens = $3; }

# Locate the yytname array definition to replace it.
$0 ~ /static.*yytname *\[/ { in_table = 1; }

# If we are not in the yytname definition, look for direct references to the
# array and replace them with a function call.
!in_table {
  left = ""
  right = $0;

  while ((m = match(right, /yytname *\[/))) {
    left  = substr(right, 1, m-1) "tname(";
    right = substr(right, m+RLENGTH);

    depth = 1;
    n = length(right);
    for (i = 1; i <= n; i++) {
      c = substr(right, i, 1);
      if (c == "]" && --depth == 0)
        break;
      if (c == "[")
        depth++;
    }

    left  = left substr(right, 1, i-1) ")";
    right = substr(right, i+1);
  }

  print left right;
}

# If we are in the yytname definition, collect all the string literals in the
# array initializer.  The first yyntokens strings are terminal symbols, the
# rest are nonterminals.
in_table {
  gsub(/\\\\/, "\2\2");
  gsub(/\\"/,  "\1");

  while ($1 ~ /^"/) {
    sub(/^[^"]*"/, "");

    x  = index($0, "\"");
    s  = substr($0, 1, x - 1);
    $0 = substr($0, x + 2);

    gsub("\1", "\\\"", s);

    # Bison will remove quotes from the token strings at runtime unless the
    # token contains an unescaped backslash, an apostrophe, or a comma.  It is
    # silly store all these quote characters if they aren't going to be used.
    if (s ~ /^\\"[^\'\\,]*\\"$/)
      s = substr(s, 3, length(s) - 4);

    if (num_tokens < yyntokens)
      tokens[num_tokens++] = s;
    else
      nterms[num_nterms++] = s;
  }
}

# At the end of the yytname definition, output our replacement function.
in_table && $0 ~ /^};/ {
  print "#if !defined(UINT_LEAST8_MAX) || !defined(UINT_LEAST16_MAX)";
  print "#  include <stdint.h>";
  print "#endif";
  print "#ifndef assert";
  print "#  include <assert.h>";
  print "#endif\n";

  print "static const char *tname(unsigned x)";
  print "{";

  count = bucketsort(sorted_tokens, tokens);
  table = build_strtab(sorted_tokens, count, token_offsets);
  token_offset_max = TMAX;
  nterm_offset = TLEN;

  sub("\1$", "", table);
  gsub("\1", "\"\n\t\t\"\\0\" \"", table);
  gsub("\2", "\\", table);

  print "\tstatic const char tname_strings[] =";
  print "\t\t     \"" table "\"";

  if ((count = bucketsort(sorted_nterms, nterms))) {
    table = build_strtab(sorted_nterms, count, nterm_offsets);
    offset_max = nterm_offset + TMAX;
    offset_chk = "(YYDEBUG ? " offset_max " : " token_offset_max ")";

    sub("\1$", "", table);
    gsub("\1", "\"\n\t\t\"\\0\" \"", table);
    gsub("\2", "\\", table);

    print "#if YYDEBUG";
    if (nterm_offset)
      print "\t\t\"\\0\" \"" table "\"";
    else
      print "\t\t     \"" table "\"";
    print "#endif";
  } else {
    offset_chk = offset_max = token_offset_max;
  }
  print "\t\t;\n";

  print "\tstatic const";
  print "#if UINT_LEAST8_MAX >= " offset_chk;
  print "\tuint_least8_t";
  print "#elif UINT_LEAST16_MAX >= " offset_chk;
  print "\tuint_least16_t";
  print "#else";
  print "\tuint_least32_t";
  print "#endif";

  print "\ttname_offsets[] = {";
  print_offsets(token_offsets, tokens, num_tokens, log10(offset_max));
  if (num_nterms) {
    print "#if YYDEBUG";
    print_offsets(nterm_offsets, nterms, num_nterms, log10(offset_max), nterm_offset);
    print "#endif";
  }
  print "\t};\n";

  print "\tassert(x < sizeof tname_offsets / sizeof tname_offsets[0]);";
  print "\treturn tname_strings + tname_offsets[x];";
  print "}";

  in_table = 0;
}

function log10(x)
{
  if (x < 10)
    return 1;
  if (x < 100)
    return 2;
  if (x < 1000)
    return 3;
  if (x < 10000)
    return 4;

  return 5;
}

# build_strtab(strings, count, offsets)
#
# Generate a string table.  Each token in the strings array (indexed from 0
# through count-1) is appended to a string, with a \1 byte terminating each
# item.
#
# The table is suffix-compressed: if the token exists as a suffix of one that
# is already in the table, no new entry is needed.  The input strings array
# must be sorted from longest to shortest in order to find all possible suffix
# matches.
#
# The offsets array is populated with the actual offsets (for C code),
# indexed by each token, and the resulting table is returned.
#
# The caller must transform the \1 characters to NUL terminators in the C code.
function build_strtab(in_strings, in_count, out_offsets, i, s, ret)
{
  ret = "";

  for (i = TLEN = 0; i < in_count; i++) {
    s = in_strings[i];
    if ((n = index(ret, s "\1")) > 0) {
      out_offsets[s] = real_length(substr(ret, 1, n-1));
    } else {
      ret = ret s "\1";
      out_offsets[s] = TMAX = TLEN;
      TLEN += real_length(s) + 1;
    }
  }

  return ret;
}

# print_offsets(offsets, strings, count, w, adj)
#
# Outputs the initializer portion of the tname offset array.
#
# Each token in the strings array (indexed from 0 through count-1) is used to
# index the offsets array, and the resulting value is printed, with commas
# between them.
#
# The w value specifies the minimum field width for the printed offsets, used
# to achieve a visually pleasing alignment of output.
#
# If adj is nonzero, it is added to all the printed offset values, and a comma
# is printed before the first line.
function print_offsets(in_offsets, in_strings, in_count, in_w, in_adj, i, t, s)
{
  t = in_adj ? "\t,\t" : "\t\t";
  s = "";

  for (i = 0; i < in_count; i++) {
    s = s sprintf("%" (in_w+1) "d,", (in_offsets[in_strings[i]] + in_adj));
    if (i+1 == in_count)
      sub(/,$/, "", s);

    if ((i+1) % 8 == 0) {
      print t s;
      t = "\t\t";
      s = "";
    }
  }

  print t s;
}

# bucketsort(dst, src)
#
# Sort the elements of src by descending string length,
# placing them into dst[0] ... dst[n].
#
# Returns the number of elements.
function bucketsort(dst, src, buckets, max, count, i, t)
{
  for (t in src) {
    i = length(src[t])
    if (i > max) { max = i }
    buckets[i]++
  }

  for (i = max; i > 0; i--) {
    if (i in buckets) {
      t = buckets[i]
      buckets[i] = count
      count += t
    }
  }

  for (t in src) {
    i = length(t = src[t])
    dst[buckets[i]++] = t
  }

  return count
}

# real_length(s)
#
# Calculate the length of s with backslash sequences counted as one character.
function real_length(s, t)
{
  t = length(s)
  return t - gsub(/\\./, "&", s) - gsub("\2\2", "&", s);
}