tools/jfuzz/jfuzz.cc

/*
 * Copyright 2016, The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <cmath>
#include <random>

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <sys/time.h>

namespace {

/*
 * Operators.
 */

static constexpr const char* kIncDecOps[]   = { "++", "--" };
static constexpr const char* kIntUnaryOps[] = { "+", "-", "~" };
static constexpr const char* kFpUnaryOps[]  = { "+", "-" };

static constexpr const char* kBoolBinOps[] = { "&&", "||", "&", "|", "^" };  // few less common
static constexpr const char* kIntBinOps[]  = { "+", "-", "*", "/", "%",
                                               ">>", ">>>", "<<", "&", "|", "^" };
static constexpr const char* kFpBinOps[]   = { "+", "-", "*", "/" };

static constexpr const char* kBoolAssignOps[] = { "=", "&=" , "|=", "^=" };  // few less common
static constexpr const char* kIntAssignOps[]  = { "=", "+=", "-=", "*=", "/=", "%=",
                                                  ">>=", ">>>=", "<<=", "&=", "|=", "^=" };
static constexpr const char* kFpAssignOps[]   = { "=", "+=", "-=", "*=", "/=" };

static constexpr const char* kBoolRelOps[] = { "==", "!=" };
static constexpr const char* kRelOps[]     = { "==", "!=", ">", ">=", "<", "<=" };

/*
 * Exceptions.
 */
static const char* kExceptionTypes[] = {
  "IllegalStateException",
  "NullPointerException",
  "IllegalArgumentException",
  "ArrayIndexOutOfBoundsException"
};

/*
 * Version of JFuzz. Increase this each time changes are made to the program
 * to preserve the property that a given version of JFuzz yields the same
 * fuzzed program for a deterministic random seed.
 */
const char* VERSION = "1.5";

/*
 * Maximum number of array dimensions, together with corresponding maximum size
 * within each dimension (to keep memory/runtime requirements roughly the same).
 */
static const uint32_t kMaxDim = 10;
static const uint32_t kMaxDimSize[kMaxDim + 1] = { 0, 1000, 32, 10, 6, 4, 3, 3, 2, 2, 2 };

/*
 * Utility function to return the number of elements in an array.
 */
template <typename T, uint32_t N>
constexpr uint32_t countof(T const (&)[N]) {
  return N;
}

/**
 * A class that generates a random program that compiles correctly. The program
 * is generated using rules that generate various programming constructs. Each rule
 * has a fixed probability to "fire". Running a generated program yields deterministic
 * output, making it suited to test various modes of execution (e.g an interpreter vs.
 * an compiler or two different run times) for divergences.
 */
class JFuzz {
 public:
  JFuzz(FILE* out,
        uint32_t seed,
        uint32_t expr_depth,
        uint32_t stmt_length,
        uint32_t if_nest,
        uint32_t loop_nest,
        uint32_t try_nest)
      : out_(out),
        fuzz_random_engine_(seed),
        fuzz_seed_(seed),
        fuzz_expr_depth_(expr_depth),
        fuzz_stmt_length_(stmt_length),
        fuzz_if_nest_(if_nest),
        fuzz_loop_nest_(loop_nest),
        fuzz_try_nest_(try_nest),
        return_type_(randomType()),
        array_type_(randomType()),
        array_dim_(random1(kMaxDim)),
        array_size_(random1(kMaxDimSize[array_dim_])),
        indentation_(0),
        expr_depth_(0),
        stmt_length_(0),
        if_nest_(0),
        loop_nest_(0),
        switch_nest_(0),
        do_nest_(0),
        try_nest_(0),
        boolean_local_(0),
        int_local_(0),
        long_local_(0),
        float_local_(0),
        double_local_(0),
        in_inner_(false) { }

  ~JFuzz() { }

  void emitProgram() {
    emitHeader();
    emitTestClassWithMain();
  }

 private:
  //
  // Types.
  //

  // Current type of each expression during generation.
  enum Type {
    kBoolean,
    kInt,
    kLong,
    kFloat,
    kDouble
  };

  // Test for an integral type.
  static bool isInteger(Type tp) {
    return tp == kInt || tp == kLong;
  }

  // Test for a floating-point type.
  static bool isFP(Type tp) {
    return tp == kFloat || tp == kDouble;
  }

  // Emit type.
  void emitType(Type tp) const {
    switch (tp) {
      case kBoolean: fputs("boolean", out_); break;
      case kInt:     fputs("int",     out_); break;
      case kLong:    fputs("long",    out_); break;
      case kFloat:   fputs("float",   out_); break;
      case kDouble:  fputs("double",  out_); break;
    }
  }

  // Emit type class.
  void emitTypeClass(Type tp) const {
    switch (tp) {
      case kBoolean: fputs("Boolean", out_); break;
      case kInt:     fputs("Integer", out_); break;
      case kLong:    fputs("Long",    out_); break;
      case kFloat:   fputs("Float",   out_); break;
      case kDouble:  fputs("Double",  out_); break;
    }
  }

  // Return a random type.
  Type randomType() {
    switch (random1(5)) {
      case 1:  return kBoolean;
      case 2:  return kInt;
      case 3:  return kLong;
      case 4:  return kFloat;
      default: return kDouble;
    }
  }

  // Emits a random strong selected from an array of operator strings.
  template <std::uint32_t N>
  inline void emitOneOf(const char* const (&ops)[N]) {
    fputs(ops[random0(N)], out_);
  }

  //
  // Expressions.
  //

  // Emit an unary operator (same type in-out).
  void emitUnaryOp(Type tp) {
    if (tp == kBoolean) {
      fputc('!', out_);
    } else if (isInteger(tp)) {
      emitOneOf(kIntUnaryOps);
    } else {  // isFP(tp)
      emitOneOf(kFpUnaryOps);
    }
  }

  // Emit a pre/post-increment/decrement operator (same type in-out).
  void emitIncDecOp(Type tp) {
    if (tp == kBoolean) {
      // Not applicable, just leave "as is".
    } else {  // isInteger(tp) || isFP(tp)
      emitOneOf(kIncDecOps);
    }
  }

  // Emit a binary operator (same type in-out).
  void emitBinaryOp(Type tp) {
    if (tp == kBoolean) {
      emitOneOf(kBoolBinOps);
    } else if (isInteger(tp)) {
      emitOneOf(kIntBinOps);
    } else {  // isFP(tp)
      emitOneOf(kFpBinOps);
    }
  }

  // Emit an assignment operator (same type in-out).
  void emitAssignmentOp(Type tp) {
    if (tp == kBoolean) {
      emitOneOf(kBoolAssignOps);
    } else if (isInteger(tp)) {
      emitOneOf(kIntAssignOps);
    } else {  // isFP(tp)
      emitOneOf(kFpAssignOps);
    }
  }

  // Emit a relational operator (one type in, boolean out).
  void emitRelationalOp(Type tp) {
    if (tp == kBoolean) {
      emitOneOf(kBoolRelOps);
    } else {  // isInteger(tp) || isFP(tp)
      emitOneOf(kRelOps);
    }
  }

  // Emit a type conversion operator sequence (out type given, new suitable in type picked).
  Type emitTypeConversionOp(Type tp) {
    if (tp == kInt) {
      switch (random1(5)) {
        case 1: fputs("(int)", out_); return kLong;
        case 2: fputs("(int)", out_); return kFloat;
        case 3: fputs("(int)", out_); return kDouble;
        // Narrowing-widening.
        case 4: fputs("(int)(byte)(int)",  out_); return kInt;
        case 5: fputs("(int)(short)(int)", out_); return kInt;
      }
    } else if (tp == kLong) {
      switch (random1(6)) {
        case 1: /* implicit */         return kInt;
        case 2: fputs("(long)", out_); return kFloat;
        case 3: fputs("(long)", out_); return kDouble;
        // Narrowing-widening.
        case 4: fputs("(long)(byte)(long)",  out_); return kLong;
        case 5: fputs("(long)(short)(long)", out_); return kLong;
        case 6: fputs("(long)(int)(long)",   out_); return kLong;
      }
    } else if (tp == kFloat) {
      switch (random1(4)) {
        case 1: fputs("(float)", out_); return kInt;
        case 2: fputs("(float)", out_); return kLong;
        case 3: fputs("(float)", out_); return kDouble;
        // Narrowing-widening.
        case 4: fputs("(float)(int)(float)", out_); return kFloat;
      }
    } else if (tp == kDouble) {
      switch (random1(5)) {
        case 1: fputs("(double)", out_); return kInt;
        case 2: fputs("(double)", out_); return kLong;
        case 3: fputs("(double)", out_); return kFloat;
        // Narrowing-widening.
        case 4: fputs("(double)(int)(double)",   out_); return kDouble;
        case 5: fputs("(double)(float)(double)", out_); return kDouble;
      }
    }
    return tp;  // nothing suitable, just keep type
  }

  // Emit a type conversion (out type given, new suitable in type picked).
  void emitTypeConversion(Type tp) {
    if (tp == kBoolean) {
      Type tp = randomType();
      emitExpression(tp);
      fputc(' ', out_);
      emitRelationalOp(tp);
      fputc(' ', out_);
      emitExpression(tp);
    } else {
      tp = emitTypeConversionOp(tp);
      fputc(' ', out_);
      emitExpression(tp);
    }
  }

  // Emit an unary intrinsic (out type given, new suitable in type picked).
  Type emitIntrinsic1(Type tp) {
    if (tp == kBoolean) {
      switch (random1(6)) {
        case 1: fputs("Float.isNaN",       out_); return kFloat;
        case 2: fputs("Float.isFinite",    out_); return kFloat;
        case 3: fputs("Float.isInfinite",  out_); return kFloat;
        case 4: fputs("Double.isNaN",      out_); return kDouble;
        case 5: fputs("Double.isFinite",   out_); return kDouble;
        case 6: fputs("Double.isInfinite", out_); return kDouble;
      }
    } else if (isInteger(tp)) {
      const char* prefix = tp == kLong ? "Long" : "Integer";
      switch (random1(13)) {
        case 1: fprintf(out_, "%s.highestOneBit",         prefix); break;
        case 2: fprintf(out_, "%s.lowestOneBit",          prefix); break;
        case 3: fprintf(out_, "%s.numberOfLeadingZeros",  prefix); break;
        case 4: fprintf(out_, "%s.numberOfTrailingZeros", prefix); break;
        case 5: fprintf(out_, "%s.bitCount",              prefix); break;
        case 6: fprintf(out_, "%s.signum",                prefix); break;
        case 7: fprintf(out_, "%s.reverse",               prefix); break;
        case 8: fprintf(out_, "%s.reverseBytes",          prefix); break;
        case 9:  fputs("Math.incrementExact", out_); break;
        case 10: fputs("Math.decrementExact", out_); break;
        case 11: fputs("Math.negateExact",    out_); break;
        case 12: fputs("Math.abs",            out_); break;
        case 13: fputs("Math.round", out_);
                 return tp == kLong ? kDouble : kFloat;
      }
    } else {  // isFP(tp)
      switch (random1(6)) {
        case 1: fputs("Math.abs",      out_); break;
        case 2: fputs("Math.ulp",      out_); break;
        case 3: fputs("Math.signum",   out_); break;
        case 4: fputs("Math.nextUp",   out_); break;
        case 5: fputs("Math.nextDown", out_); break;
        case 6: if (tp == kDouble) {
                  fputs("Double.longBitsToDouble", out_);
                  return kLong;
                } else {
                  fputs("Float.intBitsToFloat", out_);
                  return kInt;
                }
      }
    }
    return tp;  // same type in-out
  }

  // Emit a binary intrinsic (out type given, new suitable in type picked).
  Type emitIntrinsic2(Type tp) {
    if (tp == kBoolean) {
      switch (random1(3)) {
        case 1: fputs("Boolean.logicalAnd", out_); break;
        case 2: fputs("Boolean.logicalOr",  out_); break;
        case 3: fputs("Boolean.logicalXor", out_); break;
      }
    } else if (isInteger(tp)) {
      const char* prefix = tp == kLong ? "Long" : "Integer";
      switch (random1(11)) {
        case 1: fprintf(out_, "%s.compare", prefix); break;
        case 2: fprintf(out_, "%s.sum",     prefix); break;
        case 3: fprintf(out_, "%s.min",     prefix); break;
        case 4: fprintf(out_, "%s.max",     prefix); break;
        case 5:  fputs("Math.min",           out_); break;
        case 6:  fputs("Math.max",           out_); break;
        case 7:  fputs("Math.floorDiv",      out_); break;
        case 8:  fputs("Math.floorMod",      out_); break;
        case 9:  fputs("Math.addExact",      out_); break;
        case 10: fputs("Math.subtractExact", out_); break;
        case 11: fputs("Math.multiplyExact", out_); break;
      }
    } else {  // isFP(tp)
      const char* prefix = tp == kDouble ? "Double" : "Float";
      switch (random1(5)) {
        case 1: fprintf(out_, "%s.sum", prefix); break;
        case 2: fprintf(out_, "%s.min", prefix); break;
        case 3: fprintf(out_, "%s.max", prefix); break;
        case 4: fputs("Math.min", out_); break;
        case 5: fputs("Math.max", out_); break;
      }
    }
    return tp;  // same type in-out
  }

  // Emit an intrinsic (out type given, new suitable in type picked).
  void emitIntrinsic(Type tp) {
    if (random1(2) == 1) {
      tp = emitIntrinsic1(tp);
      fputc('(', out_);
      emitExpression(tp);
      fputc(')', out_);
    } else {
      tp = emitIntrinsic2(tp);
      fputc('(', out_);
      emitExpression(tp);
      fputs(", ", out_);
      emitExpression(tp);
      fputc(')', out_);
    }
  }

  // Emit a method call (out type given).
  void emitMethodCall(Type tp) {
    if (tp != kBoolean && !in_inner_) {
      // Accept all numerical types (implicit conversion) and when not
      // declaring inner classes (to avoid infinite recursion).
      switch (random1(8)) {
        case 1: fputs("mA.a()",  out_); break;
        case 2: fputs("mB.a()",  out_); break;
        case 3: fputs("mB.x()",  out_); break;
        case 4: fputs("mBX.x()", out_); break;
        case 5: fputs("mC.s()",  out_); break;
        case 6: fputs("mC.c()",  out_); break;
        case 7: fputs("mC.x()",  out_); break;
        case 8: fputs("mCX.x()", out_); break;
      }
    } else {
      // Fall back to intrinsic.
      emitIntrinsic(tp);
    }
  }

  // Emit unboxing boxed object.
  void emitUnbox(Type tp) {
    fputc('(', out_);
    emitType(tp);
    fputs(") new ", out_);
    emitTypeClass(tp);
    fputc('(', out_);
    emitExpression(tp);
    fputc(')', out_);
  }

  // Emit miscellaneous constructs.
  void emitMisc(Type tp) {
    if (tp == kBoolean) {
      fprintf(out_, "this instanceof %s", in_inner_ ? "X" : "Test");
    } else if (isInteger(tp)) {
      const char* prefix = tp == kLong ? "Long" : "Integer";
      switch (random1(2)) {
        case 1: fprintf(out_, "%s.MIN_VALUE", prefix); break;
        case 2: fprintf(out_, "%s.MAX_VALUE", prefix); break;
      }
    } else {  // isFP(tp)
      const char* prefix = tp == kDouble ? "Double" : "Float";
      switch (random1(6)) {
        case 1: fprintf(out_, "%s.MIN_NORMAL", prefix);        break;
        case 2: fprintf(out_, "%s.MIN_VALUE", prefix);         break;
        case 3: fprintf(out_, "%s.MAX_VALUE", prefix);         break;
        case 4: fprintf(out_, "%s.POSITIVE_INFINITY", prefix); break;
        case 5: fprintf(out_, "%s.NEGATIVE_INFINITY", prefix); break;
        case 6: fprintf(out_, "%s.NaN", prefix);               break;
      }
    }
  }

  // Adjust local of given type and return adjusted value.
  uint32_t adjustLocal(Type tp, int32_t a) {
    switch (tp) {
      case kBoolean: boolean_local_ += a; return boolean_local_;
      case kInt:     int_local_     += a; return int_local_;
      case kLong:    long_local_    += a; return long_local_;
      case kFloat:   float_local_   += a; return float_local_;
      default:       double_local_  += a; return double_local_;
    }
  }

  // Emit an expression that is a strict upper bound for an array index.
  void emitUpperBound() {
    if (random1(8) == 1) {
      fputs("mArray.length", out_);
    } else if (random1(8) == 1) {
      fprintf(out_, "%u", random1(array_size_));  // random in range
    } else {
      fprintf(out_, "%u", array_size_);
    }
  }

  // Emit an array index, usually within proper range.
  void emitArrayIndex() {
    if (loop_nest_ > 0 && random1(2) == 1) {
      fprintf(out_, "i%u", random0(loop_nest_));
    } else if (random1(8) == 1) {
      fputs("mArray.length - 1", out_);
    } else {
      fprintf(out_, "%u", random0(array_size_));  // random in range
    }
    // Introduce potential off by one errors with low probability.
    if (random1(100) == 1) {
      if (random1(2) == 1) {
        fputs(" - 1", out_);
      } else {
        fputs(" + 1", out_);
      }
    }
  }

  // Emit a literal.
  void emitLiteral(Type tp) {
    switch (tp) {
      case kBoolean: fputs(random1(2) == 1 ? "true" : "false", out_); break;
      case kInt:     fprintf(out_, "%d",    random()); break;
      case kLong:    fprintf(out_, "%dL",   random()); break;
      case kFloat:   fprintf(out_, "%d.0f", random()); break;
      case kDouble:  fprintf(out_, "%d.0",  random()); break;
    }
  }

  // Emit array variable, if available.
  bool emitArrayVariable(Type tp) {
    if (tp == array_type_) {
      fputs("mArray", out_);
      for (uint32_t i = 0; i < array_dim_; i++) {
        fputc('[', out_);
        emitArrayIndex();
        fputc(']', out_);
      }
      return true;
    }
    return false;
  }

  // Emit a local variable, if available.
  bool emitLocalVariable(Type tp) {
    uint32_t locals = adjustLocal(tp, 0);
    if (locals > 0) {
      uint32_t local = random0(locals);
      switch (tp) {
        case kBoolean: fprintf(out_, "lZ%u", local); break;
        case kInt:     fprintf(out_, "lI%u", local); break;
        case kLong:    fprintf(out_, "lJ%u", local); break;
        case kFloat:   fprintf(out_, "lF%u", local); break;
        case kDouble:  fprintf(out_, "lD%u", local); break;
      }
      return true;
    }
    return false;
  }

  // Emit a field variable.
  void emitFieldVariable(Type tp) {
    switch (tp) {
      case kBoolean:fputs("mZ", out_); break;
      case kInt:    fputs("mI", out_); break;
      case kLong:   fputs("mJ", out_); break;
      case kFloat:  fputs("mF", out_); break;
      case kDouble: fputs("mD", out_); break;
    }
  }

  // Emit a variable.
  void emitVariable(Type tp) {
    switch (random1(4)) {
      case 1:
        if (emitArrayVariable(tp))
          return;
        [[fallthrough]];
      case 2:
        if (emitLocalVariable(tp))
          return;
        [[fallthrough]];
      default:
        emitFieldVariable(tp);
        break;
    }
  }

  // Emit an expression.
  void emitExpression(Type tp) {
    // Continuing expression becomes less likely as the depth grows.
    if (random1(expr_depth_ + 1) > fuzz_expr_depth_) {
      if (random1(2) == 1) {
        emitLiteral(tp);
      } else {
        emitVariable(tp);
      }
      return;
    }

    expr_depth_++;

    fputc('(', out_);
    switch (random1(12)) {  // favor binary operations
      case 1:
        // Unary operator: ~ x
        emitUnaryOp(tp);
        fputc(' ', out_);
        emitExpression(tp);
        break;
      case 2:
        // Pre-increment: ++x
        emitIncDecOp(tp);
        emitVariable(tp);
        break;
      case 3:
        // Post-increment: x++
        emitVariable(tp);
        emitIncDecOp(tp);
        break;
      case 4:
        // Ternary operator: b ? x : y
        emitExpression(kBoolean);
        fputs(" ? ", out_);
        emitExpression(tp);
        fputs(" : ", out_);
        emitExpression(tp);
        break;
      case 5:
        // Type conversion: (float) x
        emitTypeConversion(tp);
        break;
      case 6:
        // Intrinsic: foo(x)
        emitIntrinsic(tp);
        break;
      case 7:
        // Method call: mA.a()
        emitMethodCall(tp);
        break;
      case 8:
        // Emit unboxing boxed value: (int) Integer(x)
        emitUnbox(tp);
        break;
      case 9:
        // Miscellaneous constructs: a.length
        emitMisc(tp);
        break;
      default:
        // Binary operator: x + y
        emitExpression(tp);
        fputc(' ', out_);
        emitBinaryOp(tp);
        fputc(' ', out_);
        emitExpression(tp);
        break;
    }
    fputc(')', out_);

    --expr_depth_;
  }

  //
  // Statements.
  //

  // Emit current indentation.
  void emitIndentation() const {
    for (uint32_t i = 0; i < indentation_; i++) {
      fputc(' ', out_);
    }
  }

  // Emit a return statement.
  bool emitReturn(bool mustEmit) {
    // Only emit when we must, or with low probability inside ifs/loops,
    // but outside do-while to avoid confusing the may follow status.
    if (mustEmit || ((if_nest_ + loop_nest_) > 0 && do_nest_ == 0 && random1(10) == 1)) {
      fputs("return ", out_);
      emitExpression(return_type_);
      fputs(";\n", out_);
      return false;
    }
    // Fall back to assignment.
    return emitAssignment();
  }

  // Emit a continue statement.
  bool emitContinue() {
    // Only emit with low probability inside loops.
    if (loop_nest_ > 0 && random1(10) == 1) {
      fputs("continue;\n", out_);
      return false;
    }
    // Fall back to assignment.
    return emitAssignment();
  }

  // Emit a break statement.
  bool emitBreak() {
    // Only emit with low probability inside loops, but outside switches
    // to avoid confusing the may follow status.
    if (loop_nest_ > 0 && switch_nest_ == 0 && random1(10) == 1) {
      fputs("break;\n", out_);
      return false;
    }
    // Fall back to assignment.
    return emitAssignment();
  }

  // Emit a new scope with a local variable declaration statement.
  bool emitScope() {
    Type tp = randomType();
    fputs("{\n", out_);
    indentation_ += 2;
    emitIndentation();
    emitType(tp);
    switch (tp) {
      case kBoolean: fprintf(out_, " lZ%u = ", boolean_local_); break;
      case kInt:     fprintf(out_, " lI%u = ", int_local_);     break;
      case kLong:    fprintf(out_, " lJ%u = ", long_local_);    break;
      case kFloat:   fprintf(out_, " lF%u = ", float_local_);   break;
      case kDouble:  fprintf(out_, " lD%u = ", double_local_);  break;
    }
    emitExpression(tp);
    fputs(";\n", out_);

    adjustLocal(tp, 1);  // local now visible

    bool mayFollow = emitStatementList();

    adjustLocal(tp, -1);  // local no longer visible

    indentation_ -= 2;
    emitIndentation();
    fputs("}\n", out_);
    return mayFollow;
  }

  // Emit one dimension of an array initializer, where parameter dim >= 1
  // denotes the number of remaining dimensions that should be emitted.
  void emitArrayInitDim(int dim) {
    if (dim == 1) {
      // Last dimension: set of values.
      fputs("{ ", out_);
      for (uint32_t i = 0; i < array_size_; i++) {
        emitExpression(array_type_);
        fputs(", ", out_);
      }
      fputs("}", out_);

    } else {
      // Outer dimensions: set of sets.
      fputs("{\n", out_);
      indentation_ += 2;
      emitIndentation();

      for (uint32_t i = 0; i < array_size_; i++) {
        emitArrayInitDim(dim - 1);
        if (i != array_size_ - 1) {
          fputs(",\n", out_);
          emitIndentation();
        }
      }

      fputs(",\n", out_);
      indentation_ -= 2;
      emitIndentation();
      fputs("}", out_);
    }
  }

  // Emit an array initializer of the following form.
  //   {
  //     type[]..[] tmp = { .. };
  //     mArray = tmp;
  //   }
  bool emitArrayInit() {
    // Avoid elaborate array initializers.
    uint64_t p = pow(array_size_, array_dim_);
    if (p > 20) {
      return emitAssignment();  // fall back
    }

    fputs("{\n", out_);

    indentation_ += 2;
    emitIndentation();
    emitType(array_type_);
    for (uint32_t i = 0; i < array_dim_; i++) {
      fputs("[]", out_);
    }
    fputs(" tmp = ", out_);
    emitArrayInitDim(array_dim_);
    fputs(";\n", out_);

    emitIndentation();
    fputs("mArray = tmp;\n", out_);

    indentation_ -= 2;
    emitIndentation();
    fputs("}\n", out_);
    return true;
  }

  // Emit a for loop.
  bool emitForLoop() {
    // Continuing loop nest becomes less likely as the depth grows.
    if (random1(loop_nest_ + 1) > fuzz_loop_nest_) {
      return emitAssignment();  // fall back
    }

    bool goesUp = random1(2) == 1;
    fprintf(out_, "for (int i%u = ", loop_nest_);
    if (goesUp) {
      fprintf(out_, "0; i%u < ", loop_nest_);
      emitUpperBound();
      fprintf(out_, "; i%u++) {\n", loop_nest_);
    } else {
      emitUpperBound();
      fprintf(out_, " - 1; i%d >= 0", loop_nest_);
      fprintf(out_, "; i%d--) {\n", loop_nest_);
    }

    ++loop_nest_;  // now in loop

    indentation_ += 2;
    emitStatementList();

    --loop_nest_;  // no longer in loop

    indentation_ -= 2;
    emitIndentation();
    fprintf(out_, "}\n");
    return true;  // loop-body does not block flow
  }

  // Emit while or do-while loop.
  bool emitDoLoop() {
    // Continuing loop nest becomes less likely as the depth grows.
    if (random1(loop_nest_ + 1) > fuzz_loop_nest_) {
      return emitAssignment();  // fall back
    }

    bool isWhile = random1(2) == 1;
    fputs("{\n", out_);
    indentation_ += 2;
    emitIndentation();
    fprintf(out_, "int i%u = %d;\n", loop_nest_, isWhile ? -1 : 0);
    emitIndentation();
    if (isWhile) {
      fprintf(out_, "while (++i%u < ", loop_nest_);
      emitUpperBound();
      fputs(") {\n", out_);
    } else {
      fputs("do {\n", out_);
      do_nest_++;
    }

    ++loop_nest_;  // now in loop

    indentation_ += 2;
    emitStatementList();

    --loop_nest_;  // no longer in loop

    indentation_ -= 2;
    emitIndentation();
    if (isWhile) {
      fputs("}\n", out_);
    } else {
      fprintf(out_, "} while (++i%u < ", loop_nest_);
      emitUpperBound();
      fputs(");\n", out_);
      --do_nest_;
    }
    indentation_ -= 2;
    emitIndentation();
    fputs("}\n", out_);
    return true;  // loop-body does not block flow
  }

  // Emit an if statement.
  bool emitIfStmt() {
    // Continuing if nest becomes less likely as the depth grows.
    if (random1(if_nest_ + 1) > fuzz_if_nest_) {
      return emitAssignment();  // fall back
    }

    fputs("if (", out_);
    emitExpression(kBoolean);
    fputs(") {\n", out_);

    ++if_nest_;  // now in if

    indentation_ += 2;
    bool mayFollowTrue = emitStatementList();
    indentation_ -= 2;
    emitIndentation();
    fprintf(out_, "} else {\n");
    indentation_ += 2;
    bool mayFollowFalse = emitStatementList();

    --if_nest_;  // no longer in if

    indentation_ -= 2;
    emitIndentation();
    fprintf(out_, "}\n");
    return mayFollowTrue || mayFollowFalse;
  }

  bool emitTry() {
    fputs("try {\n", out_);
    indentation_ += 2;
    bool mayFollow = emitStatementList();
    indentation_ -= 2;
    emitIndentation();
    fputc('}', out_);
    return mayFollow;
  }

  bool emitCatch() {
    uint32_t count = random1(countof(kExceptionTypes));
    bool mayFollow = false;
    for (uint32_t i = 0; i < count; ++i) {
      fprintf(out_, " catch (%s ex%u_%u) {\n", kExceptionTypes[i], try_nest_, i);
      indentation_ += 2;
      mayFollow |= emitStatementList();
      indentation_ -= 2;
      emitIndentation();
      fputc('}', out_);
    }
    return mayFollow;
  }

  bool emitFinally() {
    fputs(" finally {\n", out_);
    indentation_ += 2;
    bool mayFollow = emitStatementList();
    indentation_ -= 2;
    emitIndentation();
    fputc('}', out_);
    return mayFollow;
  }

  // Emit a try-catch-finally block.
  bool emitTryCatchFinally() {
    // Apply a hard limit on the number of catch blocks. This is for
    // javac which fails if blocks within try-catch-finally are too
    // large (much less than you'd expect).
    if (try_nest_ > fuzz_try_nest_) {
      return emitAssignment();  // fall back
    }

    ++try_nest_;  // Entering try-catch-finally

    bool mayFollow = emitTry();
    switch (random0(3)) {
      case 0:  // try..catch
        mayFollow |= emitCatch();
        break;
      case 1:  // try..finally
        mayFollow &= emitFinally();
        break;
      case 2:  // try..catch..finally
        // When determining whether code may follow, we observe that a
        // finally block always follows after try and catch
        // block. Code may only follow if the finally block permits
        // and either the try or catch block allows code to follow.
        mayFollow = (mayFollow | emitCatch());
        mayFollow &= emitFinally();
        break;
    }
    fputc('\n', out_);

    --try_nest_;  // Leaving try-catch-finally
    return mayFollow;
  }

  // Emit a switch statement.
  bool emitSwitch() {
    // Continuing if nest becomes less likely as the depth grows.
    if (random1(if_nest_ + 1) > fuzz_if_nest_) {
      return emitAssignment();  // fall back
    }

    bool mayFollow = false;
    fputs("switch (", out_);
    emitArrayIndex();  // restrict its range
    fputs(") {\n", out_);

    ++if_nest_;
    ++switch_nest_;  // now in switch

    indentation_ += 2;
    for (uint32_t i = 0; i < 2; i++) {
      emitIndentation();
      if (i == 0) {
        fprintf(out_, "case %u: {\n", random0(array_size_));
      } else {
        fprintf(out_, "default: {\n");
      }
      indentation_ += 2;
      if (emitStatementList()) {
        // Must end with break.
        emitIndentation();
        fputs("break;\n", out_);
        mayFollow = true;
      }
      indentation_ -= 2;
      emitIndentation();
      fputs("}\n", out_);
    }

    --if_nest_;
    --switch_nest_;  // no longer in switch

    indentation_ -= 2;
    emitIndentation();
    fprintf(out_, "}\n");
    return mayFollow;
  }

  bool emitNopCall() {
    fputs("nop();\n", out_);
    return true;
  }

  // Emit an assignment statement.
  bool emitAssignment() {
    Type tp = randomType();
    emitVariable(tp);
    fputc(' ', out_);
    emitAssignmentOp(tp);
    fputc(' ', out_);
    emitExpression(tp);
    fputs(";\n", out_);
    return true;
  }

  // Emit a single statement. Returns true if statements may follow.
  bool emitStatement() {
    switch (random1(16)) {  // favor assignments
      case 1:  return emitReturn(false);     break;
      case 2:  return emitContinue();        break;
      case 3:  return emitBreak();           break;
      case 4:  return emitScope();           break;
      case 5:  return emitArrayInit();       break;
      case 6:  return emitForLoop();         break;
      case 7:  return emitDoLoop();          break;
      case 8:  return emitIfStmt();          break;
      case 9:  return emitSwitch();          break;
      case 10: return emitTryCatchFinally(); break;
      case 11: return emitNopCall();         break;
      default: return emitAssignment();      break;
    }
  }

  // Emit a statement list. Returns true if statements may follow.
  bool emitStatementList() {
    while (stmt_length_ < 1000) {  // avoid run-away
      stmt_length_++;
      emitIndentation();
      if (!emitStatement()) {
        return false;  // rest would be dead code
      }
      // Continuing this list becomes less likely as the total statement list grows.
      if (random1(stmt_length_) > fuzz_stmt_length_) {
        break;
      }
    }
    return true;
  }

  // Emit interface and class declarations.
  void emitClassDecls() {
    in_inner_ = true;
    fputs("  private interface X {\n", out_);
    fputs("    int x();\n", out_);
    fputs("  }\n\n", out_);
    fputs("  private class A {\n", out_);
    fputs("    public int a() {\n", out_);
    fputs("      return ", out_);
    emitExpression(kInt);
    fputs(";\n    }\n", out_);
    fputs("  }\n\n", out_);
    fputs("  private class B extends A implements X {\n", out_);
    fputs("    public int a() {\n", out_);
    fputs("      return super.a() + ", out_);
    emitExpression(kInt);
    fputs(";\n    }\n", out_);
    fputs("    public int x() {\n", out_);
    fputs("      return ", out_);
    emitExpression(kInt);
    fputs(";\n    }\n", out_);
    fputs("  }\n\n", out_);
    fputs("  private static class C implements X {\n", out_);
    fputs("    public static int s() {\n", out_);
    fputs("      return ", out_);
    emitLiteral(kInt);
    fputs(";\n    }\n", out_);
    fputs("    public int c() {\n", out_);
    fputs("      return ", out_);
    emitLiteral(kInt);
    fputs(";\n    }\n", out_);
    fputs("    public int x() {\n", out_);
    fputs("      return ", out_);
    emitLiteral(kInt);
    fputs(";\n    }\n", out_);
    fputs("  }\n\n", out_);
    in_inner_ = false;
  }

  // Emit field declarations.
  void emitFieldDecls() {
    fputs("  private A mA  = new B();\n", out_);
    fputs("  private B mB  = new B();\n", out_);
    fputs("  private X mBX = new B();\n", out_);
    fputs("  private C mC  = new C();\n", out_);
    fputs("  private X mCX = new C();\n\n", out_);
    fputs("  private boolean mZ = false;\n", out_);
    fputs("  private int     mI = 0;\n", out_);
    fputs("  private long    mJ = 0;\n", out_);
    fputs("  private float   mF = 0;\n", out_);
    fputs("  private double  mD = 0;\n\n", out_);
  }

  // Emit array declaration.
  void emitArrayDecl() {
    fputs("  private ", out_);
    emitType(array_type_);
    for (uint32_t i = 0; i < array_dim_; i++) {
      fputs("[]", out_);
    }
    fputs(" mArray = new ", out_);
    emitType(array_type_);
    for (uint32_t i = 0; i < array_dim_; i++) {
      fprintf(out_, "[%d]", array_size_);
    }
    fputs(";\n\n", out_);
  }

  // Emit test constructor.
  void emitTestConstructor() {
    fputs("  private Test() {\n", out_);
    indentation_ += 2;
    emitIndentation();
    emitType(array_type_);
    fputs(" a = ", out_);
    emitLiteral(array_type_);
    fputs(";\n", out_);
    for (uint32_t i = 0; i < array_dim_; i++) {
      emitIndentation();
      fprintf(out_, "for (int i%u = 0; i%u < %u; i%u++) {\n", i, i, array_size_, i);
      indentation_ += 2;
    }
    emitIndentation();
    fputs("mArray", out_);
    for (uint32_t i = 0; i < array_dim_; i++) {
      fprintf(out_, "[i%u]", i);
    }
    fputs(" = a;\n", out_);
    emitIndentation();
    if (array_type_ == kBoolean) {
      fputs("a = !a;\n", out_);
    } else {
      fputs("a++;\n", out_);
    }
    for (uint32_t i = 0; i < array_dim_; i++) {
      indentation_ -= 2;
      emitIndentation();
      fputs("}\n", out_);
    }
    indentation_ -= 2;
    fputs("  }\n\n", out_);
  }

  // Emit test method.
  void emitTestMethod() {
    fputs("  private ", out_);
    emitType(return_type_);
    fputs(" testMethod() {\n", out_);
    indentation_ += 2;
    if (emitStatementList()) {
      // Must end with return.
      emitIndentation();
      emitReturn(true);
    }
    indentation_ -= 2;
    fputs("  }\n\n", out_);
  }

  // Emit main method driver.
  void emitMainMethod() {
    fputs("  public static void main(String[] args) {\n", out_);
    indentation_ += 2;
    fputs("    Test t = new Test();\n    ", out_);
    emitType(return_type_);
    fputs(" r = ", out_);
    emitLiteral(return_type_);
    fputs(";\n", out_);
    fputs("    try {\n", out_);
    fputs("      r = t.testMethod();\n", out_);
    fputs("    } catch (Exception e) {\n", out_);
    fputs("      // Arithmetic, null pointer, index out of bounds, etc.\n", out_);
    fputs("      System.out.println(\"An exception was caught.\");\n", out_);
    fputs("    }\n", out_);
    fputs("    System.out.println(\"r  = \" + r);\n",    out_);
    fputs("    System.out.println(\"mZ = \" + t.mZ);\n", out_);
    fputs("    System.out.println(\"mI = \" + t.mI);\n", out_);
    fputs("    System.out.println(\"mJ = \" + t.mJ);\n", out_);
    fputs("    System.out.println(\"mF = \" + t.mF);\n", out_);
    fputs("    System.out.println(\"mD = \" + t.mD);\n", out_);
    fputs("    System.out.println(\"mArray = \" + ", out_);
    if (array_dim_ == 1) {
      fputs("Arrays.toString(t.mArray)", out_);
    } else {
      fputs("Arrays.deepToString(t.mArray)", out_);
    }
    fputs(");\n", out_);
    indentation_ -= 2;
    fputs("  }\n", out_);
  }

  // Emit a static void method.
  void emitStaticNopMethod() {
    fputs("  public static void nop() {}\n\n", out_);
  }

  // Emit program header. Emit command line options in the comments.
  void emitHeader() {
    fputs("\n/**\n * AOSP JFuzz Tester.\n", out_);
    fputs(" * Automatically generated program.\n", out_);
    fprintf(out_,
            " * jfuzz -s %u -d %u -l %u -i %u -n %u (version %s)\n */\n\n",
            fuzz_seed_,
            fuzz_expr_depth_,
            fuzz_stmt_length_,
            fuzz_if_nest_,
            fuzz_loop_nest_,
            VERSION);
    fputs("import java.util.Arrays;\n\n", out_);
  }

  // Emit single test class with main driver.
  void emitTestClassWithMain() {
    fputs("public class Test {\n\n", out_);
    indentation_ += 2;
    emitClassDecls();
    emitFieldDecls();
    emitArrayDecl();
    emitTestConstructor();
    emitTestMethod();
    emitStaticNopMethod();
    emitMainMethod();
    indentation_ -= 2;
    fputs("}\n\n", out_);
  }

  //
  // Random integers.
  //

  // Return random integer.
  int32_t random() {
    return fuzz_random_engine_();
  }

  // Return random integer in range [0,max).
  uint32_t random0(uint32_t max) {
    std::uniform_int_distribution<uint32_t> gen(0, max - 1);
    return gen(fuzz_random_engine_);
  }

  // Return random integer in range [1,max].
  uint32_t random1(uint32_t max) {
    std::uniform_int_distribution<uint32_t> gen(1, max);
    return gen(fuzz_random_engine_);
  }

  // Fuzzing parameters.
  FILE* out_;
  std::mt19937 fuzz_random_engine_;
  const uint32_t fuzz_seed_;
  const uint32_t fuzz_expr_depth_;
  const uint32_t fuzz_stmt_length_;
  const uint32_t fuzz_if_nest_;
  const uint32_t fuzz_loop_nest_;
  const uint32_t fuzz_try_nest_;

  // Return and array setup.
  const Type return_type_;
  const Type array_type_;
  const uint32_t array_dim_;
  const uint32_t array_size_;

  // Current context.
  uint32_t indentation_;
  uint32_t expr_depth_;
  uint32_t stmt_length_;
  uint32_t if_nest_;
  uint32_t loop_nest_;
  uint32_t switch_nest_;
  uint32_t do_nest_;
  uint32_t try_nest_;
  uint32_t boolean_local_;
  uint32_t int_local_;
  uint32_t long_local_;
  uint32_t float_local_;
  uint32_t double_local_;
  bool in_inner_;
};

}  // anonymous namespace

int32_t main(int32_t argc, char** argv) {
  // Time-based seed.
  struct timeval tp;
  gettimeofday(&tp, nullptr);

  // Defaults.
  uint32_t seed = (tp.tv_sec * 1000000 + tp.tv_usec);
  uint32_t expr_depth = 1;
  uint32_t stmt_length = 8;
  uint32_t if_nest = 2;
  uint32_t loop_nest = 3;
  uint32_t try_nest = 2;

  // Parse options.
  while (1) {
    int32_t option = getopt(argc, argv, "s:d:l:i:n:vh");
    if (option < 0) {
      break;  // done
    }
    switch (option) {
      case 's':
        seed = strtoul(optarg, nullptr, 0);  // deterministic seed
        break;
      case 'd':
        expr_depth = strtoul(optarg, nullptr, 0);
        break;
      case 'l':
        stmt_length = strtoul(optarg, nullptr, 0);
        break;
      case 'i':
        if_nest = strtoul(optarg, nullptr, 0);
        break;
      case 'n':
        loop_nest = strtoul(optarg, nullptr, 0);
        break;
      case 't':
        try_nest = strtoul(optarg, nullptr, 0);
        break;
      case 'v':
        fprintf(stderr, "jfuzz version %s\n", VERSION);
        return 0;
      case 'h':
      default:
        fprintf(stderr,
                "usage: %s [-s seed] "
                "[-d expr-depth] [-l stmt-length] "
                "[-i if-nest] [-n loop-nest] [-t try-nest] [-v] [-h]\n",
                argv[0]);
        return 1;
    }
  }

  // Seed global random generator.
  srand(seed);

  // Generate fuzzed program.
  JFuzz fuzz(stdout, seed, expr_depth, stmt_length, if_nest, loop_nest, try_nest);
  fuzz.emitProgram();
  return 0;
}