Basic interface inference for modules.

src/interface.h

Index: src/interface.h
diff --git a/src/interface.h b/src/interface.h
new file mode 100644
index 0000000000000000000000000000000000000000..37bbccb280a22b1884542fe49064584a7fc4b6ae
--- /dev/null
+++ b/src/interface.h
@@ -0,0 +1,156 @@
+// Copyright 2012 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+//       notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+//       copyright notice, this list of conditions and the following
+//       disclaimer in the documentation and/or other materials provided
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef V8_INTERFACE_H_
+#define V8_INTERFACE_H_
+
+#include "zone-inl.h"

[Sven Panne, 2012/03/08 08:55:00]

Do we really need a zone-inl.h here or is zone.h enough? Furthermore, a lot of
entities are used in the current header which get only accidentally pulled in by
zone-inl.h, so a bit more IWYU would be nice, making things less fragile.

[rossberg, 2012/03/08 10:47:06]

It's needed for the use of 'new' below. Added a comment.

+
+namespace v8 {
+namespace internal {
+
+
+// This class implements the following abstract grammar of interfaces
+// (i.e. module types):
+//   interface ::= UNDETERMINED | VALUE | MODULE(exports)
+//   exports ::= {name : interface, [CLOSED]}

[Sven Panne, 2012/03/08 08:55:00]

Hmmm, according to the code below, VALUEs can be CLOSED, too. Either the comment
or the code is wrong...

[rossberg, 2012/03/08 10:47:06]

Yeah, I generalized the semantics of closed/frozen last minute and forgot to
update the comment properly. Done.

+// A frozen module type is one that is fully determined. Unification does not
+// allow adding additional exports to frozen interfaces.
+// Otherwise, unifying modules merges their exports.
+// Undetermined types are unification variables that can be unified freely.
+
+class Interface : public ZoneObject {
+ public:
+  // ---------------------------------------------------------------------------
+  // Factory methods.
+
+  static Interface* NewValue() {
+    static Interface value_interface(VALUE);

[Sven Panne, 2012/03/08 08:55:00]

Huh? Why is this a singleton?

[rossberg, 2012/03/08 10:47:06]

Should be VALUE + FROZEN now.

There is only one such value type, so I "cache" it to avoid reallocation. Added
a comment.

+    return &value_interface;
+  }
+
+  static Interface* NewUnknown() {
+    return new Interface(NONE);
+  }
+
+  static Interface* NewModule() {
+    return new Interface(MODULE);
+  }
+
+  // ---------------------------------------------------------------------------
+  // Mutators.
+
+  // Add a name to the list of exports. If it already exists, unify with
+  // interface, otherwise insert unless this is closed.
+  void Add(Handle<String> name, Interface* interface, bool* ok) {
+    DoAdd(name.location(), name->Hash(), interface, ok);
+  }
+
+  // Unify with another interface. If successful, both interface objects will
+  // represent the same type, and changes to one are reflected in the other.
+  void Unify(Interface* that, bool* ok);
+
+  // Determine this interface to be a value interface.
+  void MakeValue(bool* ok) {
+    *ok = !IsModule();
+    if (*ok) Chase()->flags_ |= VALUE;
+  }
+
+  // Determine this interface to be a module interface.
+  void MakeModule(bool* ok) {
+    *ok = !IsValue();
+    if (*ok) Chase()->flags_ |= MODULE;
+  }
+
+  // Do not allow any further refinements, directly or through unification.
+  void Freeze(bool* ok) {
+    *ok = IsValue() || IsModule();
+    if (*ok) Chase()->flags_ |= FROZEN;
+  }
+
+  // ---------------------------------------------------------------------------
+  // Accessors.
+
+  // Look up an exported name. Returns NULL if not (yet) defined.
+  Interface* Lookup(Handle<String> name);
+
+  // Check whether this is still a fully undetermined type.
+  bool IsUndetermined() { return Chase()->flags_ == NONE; }
+
+  // Check whether this is a value type.
+  bool IsValue() { return Chase()->flags_ & VALUE; }
+
+  // Check whether this is a module type.
+  bool IsModule() { return Chase()->flags_ & MODULE; }
+
+  // Check whether this is closed (i.e. fully determined).
+  bool IsFrozen() { return Chase()->flags_ & FROZEN; }
+
+  // ---------------------------------------------------------------------------
+  // Debugging.
+#ifdef DEBUG
+  void Print(int n = 0);  // n = indentation; n < 0 => don't print recursively
+#endif
+
+  // ---------------------------------------------------------------------------
+  // Implementation.
+ private:
+  enum Flags {    // All flags are monotonous

[Sven Panne, 2012/03/08 08:55:00]

Hmmm, I am not totally happy with that representation. I think what is actually
modeled is something like:

   data Kind = Value | Module;
   data Flexibility = Flexible | Frozen
   data State = Unknown | Known Kind Flexibility

This type has 5 values, your type has 8. It would be nicer if the C stuff would
be closer to the Haskell types above, but I leave it up to you to polish this or
not.

[rossberg, 2012/03/08 10:47:06]

What I really want is a lattice where

Unknown < Value < Frozen Value
Unknown < Module < Frozen Module
Value < Module

and efficient checks whether something is below a certain bound. The most
efficient way to do that is with a bit mask, even if that contains some
nonsensical values.

+    NONE = 0,
+    VALUE = 1,    // This type describes a value
+    MODULE = 2,   // This type describes a module
+    FROZEN = 4    // This type is fully determined
+  };
+
+  int flags_;
+  Interface* forward_;     // Unification link
+  ZoneHashMap* exports_;   // Module exports and their types (allocated lazily)
+
+  explicit Interface(int flags)
+    : flags_(flags),
+      forward_(NULL),
+      exports_(NULL) {
+#ifdef DEBUG
+    if (FLAG_print_interface_details)
+      PrintF("# Creating %p\n", static_cast<void*>(this));
+#endif
+  }
+
+  Interface* Chase() {
+    Interface* result = this;
+    while (result->forward_ != NULL) result = result->forward_;
+    if (result != this) forward_ = result;  // On-the-fly path compression.
+    return result;
+  }
+
+  void DoAdd(void* name, uint32_t hash, Interface* interface, bool* ok);
+  void DoUnify(Interface* that, bool* ok);
+};
+
+} }  // namespace v8::internal
+
+#endif  // V8_INTERFACE_H_