Home | History | Annotate | Download | only in src 
      1 // Copyright 2012 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #ifndef V8_INTERFACE_H_
     29 #define V8_INTERFACE_H_
     30 
     31 #include "zone-inl.h"  // For operator new.
     32 
     33 namespace v8 {
     34 namespace internal {
     35 
     36 
     37 // This class implements the following abstract grammar of interfaces
     38 // (i.e. module types):
     39 //   interface ::= UNDETERMINED | VALUE | CONST | MODULE(exports)
     40 //   exports ::= {name : interface, ...}
     41 // A frozen type is one that is fully determined. Unification does not
     42 // allow to turn non-const values into const, or adding additional exports to
     43 // frozen interfaces. Otherwise, unifying modules merges their exports.
     44 // Undetermined types are unification variables that can be unified freely.
     45 // There is a natural subsort lattice that reflects the increase of knowledge:
     46 //
     47 //            undetermined
     48 //           //     |    \\                                                    .
     49 //       value  (frozen)  module
     50 //      //   \\  /    \  //
     51 //  const   fr.value  fr.module
     52 //      \\    /
     53 //     fr.const
     54 //
     55 // where the bold lines are the only transitions allowed.
     56 
     57 class Interface : public ZoneObject {
     58  public:
     59   // ---------------------------------------------------------------------------
     60   // Factory methods.
     61 
     62   static Interface* NewUnknown(Zone* zone) {
     63     return new(zone) Interface(NONE);
     64   }
     65 
     66   static Interface* NewValue() {
     67     static Interface value_interface(VALUE + FROZEN);  // Cached.
     68     return &value_interface;
     69   }
     70 
     71   static Interface* NewConst() {
     72     static Interface value_interface(VALUE + CONST + FROZEN);  // Cached.
     73     return &value_interface;
     74   }
     75 
     76   static Interface* NewModule(Zone* zone) {
     77     return new(zone) Interface(MODULE);
     78   }
     79 
     80   // ---------------------------------------------------------------------------
     81   // Mutators.
     82 
     83   // Add a name to the list of exports. If it already exists, unify with
     84   // interface, otherwise insert unless this is closed.
     85   void Add(Handle<String> name, Interface* interface, Zone* zone, bool* ok) {
     86     DoAdd(name.location(), name->Hash(), interface, zone, ok);
     87   }
     88 
     89   // Unify with another interface. If successful, both interface objects will
     90   // represent the same type, and changes to one are reflected in the other.
     91   void Unify(Interface* that, Zone* zone, bool* ok);
     92 
     93   // Determine this interface to be a value interface.
     94   void MakeValue(bool* ok) {
     95     *ok = !IsModule();
     96     if (*ok) Chase()->flags_ |= VALUE;
     97   }
     98 
     99   // Determine this interface to be an immutable interface.
    100   void MakeConst(bool* ok) {
    101     *ok = !IsModule() && (IsConst() || !IsFrozen());
    102     if (*ok) Chase()->flags_ |= VALUE + CONST;
    103   }
    104 
    105   // Determine this interface to be a module interface.
    106   void MakeModule(bool* ok) {
    107     *ok = !IsValue();
    108     if (*ok) Chase()->flags_ |= MODULE;
    109   }
    110 
    111   // Do not allow any further refinements, directly or through unification.
    112   void Freeze(bool* ok) {
    113     *ok = IsValue() || IsModule();
    114     if (*ok) Chase()->flags_ |= FROZEN;
    115   }
    116 
    117   // Assign an index.
    118   void Allocate(int index) {
    119     ASSERT(IsModule() && IsFrozen() && Chase()->index_ == -1);
    120     Chase()->index_ = index;
    121   }
    122 
    123   // ---------------------------------------------------------------------------
    124   // Accessors.
    125 
    126   // Check whether this is still a fully undetermined type.
    127   bool IsUnknown() { return Chase()->flags_ == NONE; }
    128 
    129   // Check whether this is a value type.
    130   bool IsValue() { return Chase()->flags_ & VALUE; }
    131 
    132   // Check whether this is a constant type.
    133   bool IsConst() { return Chase()->flags_ & CONST; }
    134 
    135   // Check whether this is a module type.
    136   bool IsModule() { return Chase()->flags_ & MODULE; }
    137 
    138   // Check whether this is closed (i.e. fully determined).
    139   bool IsFrozen() { return Chase()->flags_ & FROZEN; }
    140 
    141   bool IsUnified(Interface* that) {
    142     return Chase() == that->Chase()
    143         || (this->IsValue() == that->IsValue() &&
    144             this->IsConst() == that->IsConst());
    145   }
    146 
    147   int Length() {
    148     ASSERT(IsModule() && IsFrozen());
    149     ZoneHashMap* exports = Chase()->exports_;
    150     return exports ? exports->occupancy() : 0;
    151   }
    152 
    153   // The context slot in the hosting global context pointing to this module.
    154   int Index() {
    155     ASSERT(IsModule() && IsFrozen());
    156     return Chase()->index_;
    157   }
    158 
    159   // Look up an exported name. Returns NULL if not (yet) defined.
    160   Interface* Lookup(Handle<String> name, Zone* zone);
    161 
    162   // ---------------------------------------------------------------------------
    163   // Iterators.
    164 
    165   // Use like:
    166   //   for (auto it = interface->iterator(); !it.done(); it.Advance()) {
    167   //     ... it.name() ... it.interface() ...
    168   //   }
    169   class Iterator {
    170    public:
    171     bool done() const { return entry_ == NULL; }
    172     Handle<String> name() const {
    173       ASSERT(!done());
    174       return Handle<String>(*static_cast<String**>(entry_->key));
    175     }
    176     Interface* interface() const {
    177       ASSERT(!done());
    178       return static_cast<Interface*>(entry_->value);
    179     }
    180     void Advance() { entry_ = exports_->Next(entry_); }
    181 
    182    private:
    183     friend class Interface;
    184     explicit Iterator(const ZoneHashMap* exports)
    185         : exports_(exports), entry_(exports ? exports->Start() : NULL) {}
    186 
    187     const ZoneHashMap* exports_;
    188     ZoneHashMap::Entry* entry_;
    189   };
    190 
    191   Iterator iterator() const { return Iterator(this->exports_); }
    192 
    193   // ---------------------------------------------------------------------------
    194   // Debugging.
    195 #ifdef DEBUG
    196   void Print(int n = 0);  // n = indentation; n < 0 => don't print recursively
    197 #endif
    198 
    199   // ---------------------------------------------------------------------------
    200   // Implementation.
    201  private:
    202   enum Flags {    // All flags are monotonic
    203     NONE = 0,
    204     VALUE = 1,    // This type describes a value
    205     CONST = 2,    // This type describes a constant
    206     MODULE = 4,   // This type describes a module
    207     FROZEN = 8    // This type is fully determined
    208   };
    209 
    210   int flags_;
    211   Interface* forward_;     // Unification link
    212   ZoneHashMap* exports_;   // Module exports and their types (allocated lazily)
    213   int index_;
    214 
    215   explicit Interface(int flags)
    216     : flags_(flags),
    217       forward_(NULL),
    218       exports_(NULL),
    219       index_(-1) {
    220 #ifdef DEBUG
    221     if (FLAG_print_interface_details)
    222       PrintF("# Creating %p\n", static_cast<void*>(this));
    223 #endif
    224   }
    225 
    226   Interface* Chase() {
    227     Interface* result = this;
    228     while (result->forward_ != NULL) result = result->forward_;
    229     if (result != this) forward_ = result;  // On-the-fly path compression.
    230     return result;
    231   }
    232 
    233   void DoAdd(void* name, uint32_t hash, Interface* interface, Zone* zone,
    234              bool* ok);
    235   void DoUnify(Interface* that, bool* ok, Zone* zone);
    236 };
    237 
    238 } }  // namespace v8::internal
    239 
    240 #endif  // V8_INTERFACE_H_
    241