Start on DexBuilder

This change begins work on DexBuilder, which will allow us to generate DEX files
directly from layouts. This version is rather limited, but we will expand its
functionality in future CLs. The DexBuilder in this CL can create a DEX file
from scratch, define classes, and define methods on those classes. Within
methods, it supports extremely simple instructions, such as storing a small
constant in a register and returning a value from a register. Additionally,
there are tests to make sure that at least at a structural level, the generated
DEX files are valid.

DexBuilder and its associated builder classes use functionality from
libartdexfile and the Dex Slicer tool to support the actual encoding of DEX
files.

Test: atest, also manually tested by loaded a generated DEX file in an Android
app and verifying its behavior.

Change-Id: Iaa01aa7e3a0c7e4d5f4fa8dbce1492499c93c222

5 files changed, 513 insertions, 6 deletions

diff --git a/startop/tools/view_compiler/Android.bp b/startop/tools/view_compiler/Android.bp
index c3e91849e636..3681529643bc 100644
--- a/startop/tools/view_compiler/Android.bp
+++ b/startop/tools/view_compiler/Android.bp
@@ -14,19 +14,30 @@
 // limitations under the License.
 //
 
+cc_defaults {
+    name: "viewcompiler_defaults",
+    shared_libs: [
+        "libdexfile",
+        "slicer",
+    ],
+}
+
 cc_library_host_static {
     name: "libviewcompiler",
+    defaults: ["viewcompiler_defaults"],
     srcs: [
+        "dex_builder.cc",
         "java_lang_builder.cc",
         "util.cc",
     ],
     static_libs: [
-        "libbase"
-    ]
+        "libbase",
+    ],
 }
 
 cc_binary_host {
     name: "viewcompiler",
+    defaults: ["viewcompiler_defaults"],
     srcs: [
         "main.cc",
     ],
@@ -40,10 +51,12 @@ cc_binary_host {
 
 cc_test_host {
     name: "view-compiler-tests",
+    defaults: ["viewcompiler_defaults"],
     srcs: [
+        "dex_builder_test.cc",
         "util_test.cc",
     ],
     static_libs: [
         "libviewcompiler",
-    ]
+    ],
 }
diff --git a/startop/tools/view_compiler/dex_builder.cc b/startop/tools/view_compiler/dex_builder.cc
new file mode 100644
index 000000000000..7a9f41fd8f38
--- /dev/null
+++ b/startop/tools/view_compiler/dex_builder.cc
@@ -0,0 +1,214 @@
+/*
+ * Copyright (C) 2018 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 "dex_builder.h"
+
+#include "dex/descriptors_names.h"
+#include "dex/dex_instruction.h"
+
+#include <fstream>
+#include <memory>
+
+namespace startop {
+namespace dex {
+
+using std::shared_ptr;
+using std::string;
+
+using art::Instruction;
+using ::dex::kAccPublic;
+
+const TypeDescriptor TypeDescriptor::Int() { return TypeDescriptor{"I"}; };
+const TypeDescriptor TypeDescriptor::Void() { return TypeDescriptor{"V"}; };
+
+namespace {
+// From https://source.android.com/devices/tech/dalvik/dex-format#dex-file-magic
+constexpr uint8_t kDexFileMagic[]{0x64, 0x65, 0x78, 0x0a, 0x30, 0x33, 0x38, 0x00};
+
+// Strings lengths can be 32 bits long, but encoded as LEB128 this can take up to five bytes.
+constexpr size_t kMaxEncodedStringLength{5};
+
+}  // namespace
+
+void* TrackingAllocator::Allocate(size_t size) {
+  std::unique_ptr<uint8_t[]> buffer = std::make_unique<uint8_t[]>(size);
+  void* raw_buffer = buffer.get();
+  allocations_[raw_buffer] = std::move(buffer);
+  return raw_buffer;
+}
+
+void TrackingAllocator::Free(void* ptr) { allocations_.erase(allocations_.find(ptr)); }
+
+// Write out a DEX file that is basically:
+//
+// package dextest;
+// public class DexTest {
+//     public static int foo() { return 5; }
+// }
+void WriteTestDexFile(const string& filename) {
+  DexBuilder dex_file;
+
+  ClassBuilder cbuilder{dex_file.MakeClass("dextest.DexTest")};
+  cbuilder.set_source_file("dextest.java");
+
+  MethodBuilder method{cbuilder.CreateMethod("foo", Prototype{TypeDescriptor::Int()})};
+
+  MethodBuilder::Register r = method.MakeRegister();
+  method.BuildConst4(r, 5);
+  method.BuildReturn(r);
+
+  method.Encode();
+
+  slicer::MemView image{dex_file.CreateImage()};
+
+  std::ofstream out_file(filename);
+  out_file.write(image.ptr<const char>(), image.size());
+}
+
+DexBuilder::DexBuilder() : dex_file_{std::make_shared<ir::DexFile>()} {
+  dex_file_->magic = slicer::MemView{kDexFileMagic, sizeof(kDexFileMagic)};
+}
+
+slicer::MemView DexBuilder::CreateImage() {
+  ::dex::Writer writer(dex_file_);
+  size_t image_size{0};
+  ::dex::u1* image = writer.CreateImage(&allocator_, &image_size);
+  return slicer::MemView{image, image_size};
+}
+
+ir::String* DexBuilder::GetOrAddString(const std::string& string) {
+  ir::String*& entry = strings_[string];
+
+  if (entry == nullptr) {
+    // Need to encode the length and then write out the bytes, including 1 byte for null terminator
+    auto buffer = std::make_unique<uint8_t[]>(string.size() + kMaxEncodedStringLength + 1);
+    uint8_t* string_data_start = ::dex::WriteULeb128(buffer.get(), string.size());
+
+    size_t header_length =
+        reinterpret_cast<uintptr_t>(string_data_start) - reinterpret_cast<uintptr_t>(buffer.get());
+
+    auto end = std::copy(string.begin(), string.end(), string_data_start);
+    *end = '\0';
+
+    entry = Alloc<ir::String>();
+    // +1 for null terminator
+    entry->data = slicer::MemView{buffer.get(), header_length + string.size() + 1};
+    string_data_.push_back(std::move(buffer));
+  }
+  return entry;
+}
+
+ClassBuilder DexBuilder::MakeClass(const std::string& name) {
+  auto* class_def = Alloc<ir::Class>();
+  ir::Type* type_def = GetOrAddType(art::DotToDescriptor(name.c_str()));
+  type_def->class_def = class_def;
+
+  class_def->type = type_def;
+  class_def->super_class = GetOrAddType(art::DotToDescriptor("java.lang.Object"));
+  class_def->access_flags = kAccPublic;
+  return ClassBuilder{this, class_def};
+}
+
+// TODO(eholk): we probably want GetOrAddString() also
+ir::Type* DexBuilder::GetOrAddType(const std::string& descriptor) {
+  if (types_by_descriptor_.find(descriptor) != types_by_descriptor_.end()) {
+    return types_by_descriptor_[descriptor];
+  }
+
+  ir::Type* type = Alloc<ir::Type>();
+  type->descriptor = GetOrAddString(descriptor);
+  types_by_descriptor_[descriptor] = type;
+  return type;
+}
+
+ir::Proto* Prototype::Encode(DexBuilder* dex) const {
+  auto* proto = dex->Alloc<ir::Proto>();
+  proto->shorty = dex->GetOrAddString(Shorty());
+  proto->return_type = dex->GetOrAddType(return_type_.descriptor());
+  if (param_types_.size() > 0) {
+    proto->param_types = dex->Alloc<ir::TypeList>();
+    for (const auto& param_type : param_types_) {
+      proto->param_types->types.push_back(dex->GetOrAddType(param_type.descriptor()));
+    }
+  } else {
+    proto->param_types = nullptr;
+  }
+  return proto;
+}
+
+std::string Prototype::Shorty() const {
+  std::string shorty;
+  shorty.append(return_type_.short_descriptor());
+  for (const auto& type_descriptor : param_types_) {
+    shorty.append(type_descriptor.short_descriptor());
+  }
+  return shorty;
+}
+
+ClassBuilder::ClassBuilder(DexBuilder* parent, ir::Class* class_def)
+    : parent_(parent), class_(class_def) {}
+
+MethodBuilder ClassBuilder::CreateMethod(const std::string& name, Prototype prototype) {
+  ir::String* dex_name{parent_->GetOrAddString(name)};
+
+  auto* decl = parent_->Alloc<ir::MethodDecl>();
+  decl->name = dex_name;
+  decl->parent = class_->type;
+  decl->prototype = prototype.Encode(parent_);
+
+  return MethodBuilder{parent_, class_, decl};
+}
+
+void ClassBuilder::set_source_file(const string& source) {
+  class_->source_file = parent_->GetOrAddString(source);
+}
+
+MethodBuilder::MethodBuilder(DexBuilder* dex, ir::Class* class_def, ir::MethodDecl* decl)
+    : dex_{dex}, class_{class_def}, decl_{decl} {}
+
+ir::EncodedMethod* MethodBuilder::Encode() {
+  auto* method = dex_->Alloc<ir::EncodedMethod>();
+  method->decl = decl_;
+
+  // TODO: make access flags configurable
+  method->access_flags = kAccPublic | ::dex::kAccStatic;
+
+  auto* code = dex_->Alloc<ir::Code>();
+  code->registers = num_registers_;
+  // TODO: support ins and outs
+  code->instructions = slicer::ArrayView<const ::dex::u2>(buffer_.data(), buffer_.size());
+  method->code = code;
+
+  class_->direct_methods.push_back(method);
+
+  return method;
+}
+
+MethodBuilder::Register MethodBuilder::MakeRegister() { return num_registers_++; }
+
+void MethodBuilder::BuildReturn() { buffer_.push_back(Instruction::RETURN_VOID); }
+
+void MethodBuilder::BuildReturn(Register src) { buffer_.push_back(Instruction::RETURN | src << 8); }
+
+void MethodBuilder::BuildConst4(Register target, int value) {
+  DCHECK_LT(value, 16);
+  // TODO: support more registers
+  DCHECK_LT(target, 16);
+  buffer_.push_back(Instruction::CONST_4 | (value << 12) | (target << 8));
+}
+
+}  // namespace dex
+}  // namespace startop
diff --git a/startop/tools/view_compiler/dex_builder.h b/startop/tools/view_compiler/dex_builder.h
new file mode 100644
index 000000000000..d280abce21f5
--- /dev/null
+++ b/startop/tools/view_compiler/dex_builder.h
@@ -0,0 +1,189 @@
+/*
+ * Copyright (C) 2018 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.
+ */
+#ifndef DEX_BUILDER_H_
+#define DEX_BUILDER_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "slicer/dex_ir.h"
+#include "slicer/writer.h"
+
+namespace startop {
+namespace dex {
+
+// TODO: remove this once the dex generation code is complete.
+void WriteTestDexFile(const std::string& filename);
+
+//////////////////////////
+// Forward declarations //
+//////////////////////////
+class DexBuilder;
+
+// Our custom allocator for dex::Writer
+//
+// This keeps track of all allocations and ensures they are freed when
+// TrackingAllocator is destroyed. Pointers to memory allocated by this
+// allocator must not outlive the allocator.
+class TrackingAllocator : public ::dex::Writer::Allocator {
+ public:
+  virtual void* Allocate(size_t size);
+  virtual void Free(void* ptr);
+
+ private:
+  std::map<void*, std::unique_ptr<uint8_t[]>> allocations_;
+};
+
+// Represents a DEX type descriptor.
+//
+// TODO: add a way to create a descriptor for a reference of a class type.
+class TypeDescriptor {
+ public:
+  // Named constructors for base type descriptors.
+  static const TypeDescriptor Int();
+  static const TypeDescriptor Void();
+
+  // Return the full descriptor, such as I or Ljava/lang/Object
+  const std::string& descriptor() const { return descriptor_; }
+  // Return the shorty descriptor, such as I or L
+  std::string short_descriptor() const { return descriptor().substr(0, 1); }
+
+ private:
+  TypeDescriptor(std::string descriptor) : descriptor_{descriptor} {}
+
+  const std::string descriptor_;
+};
+
+// Defines a function signature. For example, Prototype{TypeDescriptor::VOID, TypeDescriptor::Int}
+// represents the function type (Int) -> Void.
+class Prototype {
+ public:
+  template <typename... TypeDescriptors>
+  Prototype(TypeDescriptor return_type, TypeDescriptors... param_types)
+      : return_type_{return_type}, param_types_{param_types...} {}
+
+  // Encode this prototype into the dex file.
+  ir::Proto* Encode(DexBuilder* dex) const;
+
+  // Get the shorty descriptor, such as VII for (Int, Int) -> Void
+  std::string Shorty() const;
+
+ private:
+  const TypeDescriptor return_type_;
+  const std::vector<TypeDescriptor> param_types_;
+};
+
+// Tools to help build methods and their bodies.
+class MethodBuilder {
+ public:
+  MethodBuilder(DexBuilder* dex, ir::Class* class_def, ir::MethodDecl* decl);
+
+  // Encode the method into DEX format.
+  ir::EncodedMethod* Encode();
+
+  // Registers are just represented by their number.
+  using Register = size_t;
+
+  // Create a new register to be used to storing values. Note that these are not SSA registers, like
+  // might be expected in similar code generators. This does no liveness tracking or anything, so
+  // it's up to the caller to reuse registers as appropriate.
+  Register MakeRegister();
+
+  /////////////////////////////////
+  // Instruction builder methods //
+  /////////////////////////////////
+
+  // return-void
+  void BuildReturn();
+  void BuildReturn(Register src);
+  // const/4
+  void BuildConst4(Register target, int value);
+
+  // TODO: add builders for more instructions
+
+ private:
+  DexBuilder* dex_;
+  ir::Class* class_;
+  ir::MethodDecl* decl_;
+
+  // A buffer to hold instructions we are generating.
+  std::vector<::dex::u2> buffer_;
+
+  // How many registers we've allocated
+  size_t num_registers_;
+};
+
+// A helper to build class definitions.
+class ClassBuilder {
+ public:
+  ClassBuilder(DexBuilder* parent, ir::Class* class_def);
+
+  void set_source_file(const std::string& source);
+
+  // Create a method with the given name and prototype. The returned MethodBuilder can be used to
+  // fill in the method body.
+  MethodBuilder CreateMethod(const std::string& name, Prototype prototype);
+
+ private:
+  DexBuilder* parent_;
+  ir::Class* class_;
+};
+
+// Builds Dex files from scratch.
+class DexBuilder {
+ public:
+  DexBuilder();
+
+  // Create an in-memory image of the DEX file that can either be loaded directly or written to a
+  // file.
+  slicer::MemView CreateImage();
+
+  template <typename T>
+  T* Alloc() {
+    return dex_file_->Alloc<T>();
+  }
+
+  // Find the ir::String that matches the given string, creating it if it does not exist.
+  ir::String* GetOrAddString(const std::string& string);
+  // Create a new class of the given name.
+  ClassBuilder MakeClass(const std::string& name);
+
+  // Add a type for the given descriptor, or return the existing one if it already exists.
+  // See the TypeDescriptor class for help generating these.
+  ir::Type* GetOrAddType(const std::string& descriptor);
+
+ private:
+  std::shared_ptr<ir::DexFile> dex_file_;
+
+  // allocator_ is needed to be able to encode the image.
+  TrackingAllocator allocator_;
+
+  // We'll need to allocate buffers for all of the encoded strings we create. This is where we store
+  // all of them.
+  std::vector<std::unique_ptr<uint8_t[]>> string_data_;
+
+  // Keep track of what types we've defined so we can look them up later.
+  std::map<std::string, ir::Type*> types_by_descriptor_;
+
+  // Keep track of what strings we've defined so we can look them up later.
+  std::map<std::string, ir::String*> strings_;
+};
+
+}  // namespace dex
+}  // namespace startop
+
+#endif  // DEX_BUILDER_H_
diff --git a/startop/tools/view_compiler/dex_builder_test.cc b/startop/tools/view_compiler/dex_builder_test.cc
new file mode 100644
index 000000000000..0d8b8541caeb
--- /dev/null
+++ b/startop/tools/view_compiler/dex_builder_test.cc
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2018 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 "dex_builder.h"
+
+#include "dex/art_dex_file_loader.h"
+#include "dex/dex_file.h"
+#include "gtest/gtest.h"
+
+using namespace startop::dex;
+
+// Takes a DexBuilder, encodes it into an in-memory DEX file, verifies the resulting DEX file and
+// returns whether the verification was successful.
+bool EncodeAndVerify(DexBuilder* dex_file) {
+  slicer::MemView image{dex_file->CreateImage()};
+
+  art::ArtDexFileLoader loader;
+  std::string error_msg;
+  std::unique_ptr<const art::DexFile> loaded_dex_file{loader.Open(image.ptr<const uint8_t>(),
+                                                                  image.size(),
+                                                                  /*location=*/"",
+                                                                  /*location_checksum=*/0,
+                                                                  /*oat_dex_file=*/nullptr,
+                                                                  /*verify=*/true,
+                                                                  /*verify_checksum=*/false,
+                                                                  &error_msg)};
+  return loaded_dex_file != nullptr;
+}
+
+TEST(DexBuilderTest, VerifyDexWithClassMethod) {
+  DexBuilder dex_file;
+
+  auto cbuilder{dex_file.MakeClass("dextest.DexTest")};
+
+  auto method{cbuilder.CreateMethod("foo", Prototype{TypeDescriptor::Void()})};
+  method.BuildReturn();
+  method.Encode();
+
+  EXPECT_TRUE(EncodeAndVerify(&dex_file));
+}
+
+// Makes sure a bad DEX class fails to verify.
+TEST(DexBuilderTest, VerifyBadDexWithClassMethod) {
+  DexBuilder dex_file;
+
+  auto cbuilder{dex_file.MakeClass("dextest.DexTest")};
+
+  // This method has the error, because methods cannot take Void() as a parameter.
+  auto method{
+      cbuilder.CreateMethod("foo", Prototype{TypeDescriptor::Void(), TypeDescriptor::Void()})};
+  method.BuildReturn();
+  method.Encode();
+
+  EXPECT_FALSE(EncodeAndVerify(&dex_file));
+}
+
+TEST(DexBuilderTest, VerifyDexReturn5) {
+  DexBuilder dex_file;
+
+  auto cbuilder{dex_file.MakeClass("dextest.DexTest")};
+
+  auto method{cbuilder.CreateMethod("foo", Prototype{TypeDescriptor::Int()})};
+  auto r = method.MakeRegister();
+  method.BuildConst4(r, 5);
+  method.BuildReturn(r);
+  method.Encode();
+
+  EXPECT_TRUE(EncodeAndVerify(&dex_file));
+}
diff --git a/startop/tools/view_compiler/main.cc b/startop/tools/view_compiler/main.cc
index 0ad7e24feb3b..7d791c229a98 100644
--- a/startop/tools/view_compiler/main.cc
+++ b/startop/tools/view_compiler/main.cc
@@ -16,6 +16,7 @@
 
 #include "gflags/gflags.h"
 
+#include "dex_builder.h"
 #include "java_lang_builder.h"
 #include "util.h"
 
@@ -27,15 +28,17 @@
 #include <string>
 #include <vector>
 
+namespace {
+
 using namespace tinyxml2;
 using std::string;
 
 constexpr char kStdoutFilename[]{"stdout"};
 
-DEFINE_string(package, "", "The package name for the generated class (required)");
+DEFINE_bool(dex, false, "Generate a DEX file instead of Java");
 DEFINE_string(out, kStdoutFilename, "Where to write the generated class");
+DEFINE_string(package, "", "The package name for the generated class (required)");
 
-namespace {
 class ViewCompilerXmlVisitor : public XMLVisitor {
  public:
   ViewCompilerXmlVisitor(JavaLangViewBuilder* builder) : builder_(builder) {}
@@ -63,6 +66,7 @@ class ViewCompilerXmlVisitor : public XMLVisitor {
  private:
   JavaLangViewBuilder* builder_;
 };
+
 }  // end namespace
 
 int main(int argc, char** argv) {
@@ -82,6 +86,11 @@ int main(int argc, char** argv) {
     return 1;
   }
 
+  if (FLAGS_dex) {
+    startop::dex::WriteTestDexFile("test.dex");
+    return 0;
+  }
+
   const char* const filename = argv[kFileNameParam];
   const string layout_name = FindLayoutNameFromFilename(filename);
 
@@ -102,4 +111,4 @@ int main(int argc, char** argv) {
   xml.Accept(&visitor);
 
   return 0;
-}
\ No newline at end of file
+}