interface.h 7.99 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
// 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"  // For operator new.

namespace v8 {
namespace internal {


// This class implements the following abstract grammar of interfaces
// (i.e. module types):
39
//   interface ::= UNDETERMINED | VALUE | CONST | MODULE(exports)
40
//   exports ::= {name : interface, ...}
41 42 43
// A frozen type is one that is fully determined. Unification does not
// allow to turn non-const values into const, or adding additional exports to
// frozen interfaces. Otherwise, unifying modules merges their exports.
44
// Undetermined types are unification variables that can be unified freely.
45 46 47 48 49 50 51 52 53 54 55
// There is a natural subsort lattice that reflects the increase of knowledge:
//
//            undetermined
//           //     |    \\                                                    .
//       value  (frozen)  module
//      //   \\  /    \  //
//  const   fr.value  fr.module
//      \\    /
//     fr.const
//
// where the bold lines are the only transitions allowed.
56 57 58 59 60 61

class Interface : public ZoneObject {
 public:
  // ---------------------------------------------------------------------------
  // Factory methods.

62 63 64 65
  static Interface* NewUnknown(Zone* zone) {
    return new(zone) Interface(NONE);
  }

66 67 68 69 70
  static Interface* NewValue() {
    static Interface value_interface(VALUE + FROZEN);  // Cached.
    return &value_interface;
  }

71 72 73
  static Interface* NewConst() {
    static Interface value_interface(VALUE + CONST + FROZEN);  // Cached.
    return &value_interface;
74 75
  }

76 77
  static Interface* NewModule(Zone* zone) {
    return new(zone) Interface(MODULE);
78 79 80 81 82 83 84
  }

  // ---------------------------------------------------------------------------
  // Mutators.

  // Add a name to the list of exports. If it already exists, unify with
  // interface, otherwise insert unless this is closed.
85 86
  void Add(Handle<String> name, Interface* interface, Zone* zone, bool* ok) {
    DoAdd(name.location(), name->Hash(), interface, zone, ok);
87 88 89 90
  }

  // Unify with another interface. If successful, both interface objects will
  // represent the same type, and changes to one are reflected in the other.
91
  void Unify(Interface* that, Zone* zone, bool* ok);
92 93 94 95 96 97 98

  // Determine this interface to be a value interface.
  void MakeValue(bool* ok) {
    *ok = !IsModule();
    if (*ok) Chase()->flags_ |= VALUE;
  }

99 100 101 102 103 104
  // Determine this interface to be an immutable interface.
  void MakeConst(bool* ok) {
    *ok = !IsModule() && (IsConst() || !IsFrozen());
    if (*ok) Chase()->flags_ |= VALUE + CONST;
  }

105 106 107 108 109 110 111 112 113 114 115 116
  // 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;
  }

117 118 119 120 121 122
  // Assign an index.
  void Allocate(int index) {
    ASSERT(IsModule() && IsFrozen() && Chase()->index_ == -1);
    Chase()->index_ = index;
  }

123 124 125 126 127 128 129 130 131
  // ---------------------------------------------------------------------------
  // Accessors.

  // Check whether this is still a fully undetermined type.
  bool IsUnknown() { return Chase()->flags_ == NONE; }

  // Check whether this is a value type.
  bool IsValue() { return Chase()->flags_ & VALUE; }

132 133 134
  // Check whether this is a constant type.
  bool IsConst() { return Chase()->flags_ & CONST; }

135 136 137 138 139 140
  // 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; }

141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
  bool IsUnified(Interface* that) {
    return Chase() == that->Chase()
        || (this->IsValue() == that->IsValue() &&
            this->IsConst() == that->IsConst());
  }

  int Length() {
    ASSERT(IsModule() && IsFrozen());
    ZoneHashMap* exports = Chase()->exports_;
    return exports ? exports->occupancy() : 0;
  }

  // The context slot in the hosting global context pointing to this module.
  int Index() {
    ASSERT(IsModule() && IsFrozen());
    return Chase()->index_;
  }
158 159

  // Look up an exported name. Returns NULL if not (yet) defined.
160
  Interface* Lookup(Handle<String> name, Zone* zone);
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192

  // ---------------------------------------------------------------------------
  // Iterators.

  // Use like:
  //   for (auto it = interface->iterator(); !it.done(); it.Advance()) {
  //     ... it.name() ... it.interface() ...
  //   }
  class Iterator {
   public:
    bool done() const { return entry_ == NULL; }
    Handle<String> name() const {
      ASSERT(!done());
      return Handle<String>(*static_cast<String**>(entry_->key));
    }
    Interface* interface() const {
      ASSERT(!done());
      return static_cast<Interface*>(entry_->value);
    }
    void Advance() { entry_ = exports_->Next(entry_); }

   private:
    friend class Interface;
    explicit Iterator(const ZoneHashMap* exports)
        : exports_(exports), entry_(exports ? exports->Start() : NULL) {}

    const ZoneHashMap* exports_;
    ZoneHashMap::Entry* entry_;
  };

  Iterator iterator() const { return Iterator(this->exports_); }

193 194 195 196 197 198 199 200 201 202 203 204
  // ---------------------------------------------------------------------------
  // Debugging.
#ifdef DEBUG
  void Print(int n = 0);  // n = indentation; n < 0 => don't print recursively
#endif

  // ---------------------------------------------------------------------------
  // Implementation.
 private:
  enum Flags {    // All flags are monotonic
    NONE = 0,
    VALUE = 1,    // This type describes a value
205 206 207
    CONST = 2,    // This type describes a constant
    MODULE = 4,   // This type describes a module
    FROZEN = 8    // This type is fully determined
208 209 210 211 212
  };

  int flags_;
  Interface* forward_;     // Unification link
  ZoneHashMap* exports_;   // Module exports and their types (allocated lazily)
213
  int index_;
214 215 216 217

  explicit Interface(int flags)
    : flags_(flags),
      forward_(NULL),
218 219
      exports_(NULL),
      index_(-1) {
220 221 222 223 224 225 226 227 228 229 230 231 232
#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;
  }

233 234 235
  void DoAdd(void* name, uint32_t hash, Interface* interface, Zone* zone,
             bool* ok);
  void DoUnify(Interface* that, bool* ok, Zone* zone);
236 237 238 239 240
};

} }  // namespace v8::internal

#endif  // V8_INTERFACE_H_