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#include "v8.h"
29
30#include "interface.h"
31
32namespace v8 {
33namespace internal {
34
35static bool Match(void* key1, void* key2) {
36  String* name1 = *static_cast<String**>(key1);
37  String* name2 = *static_cast<String**>(key2);
38  ASSERT(name1->IsInternalizedString());
39  ASSERT(name2->IsInternalizedString());
40  return name1 == name2;
41}
42
43
44Interface* Interface::Lookup(Handle<String> name, Zone* zone) {
45  ASSERT(IsModule());
46  ZoneHashMap* map = Chase()->exports_;
47  if (map == NULL) return NULL;
48  ZoneAllocationPolicy allocator(zone);
49  ZoneHashMap::Entry* p = map->Lookup(name.location(), name->Hash(), false,
50                                      allocator);
51  if (p == NULL) return NULL;
52  ASSERT(*static_cast<String**>(p->key) == *name);
53  ASSERT(p->value != NULL);
54  return static_cast<Interface*>(p->value);
55}
56
57
58#ifdef DEBUG
59// Current nesting depth for debug output.
60class Nesting {
61 public:
62  Nesting()  { current_ += 2; }
63  ~Nesting() { current_ -= 2; }
64  static int current() { return current_; }
65 private:
66  static int current_;
67};
68
69int Nesting::current_ = 0;
70#endif
71
72
73void Interface::DoAdd(
74    void* name, uint32_t hash, Interface* interface, Zone* zone, bool* ok) {
75  MakeModule(ok);
76  if (!*ok) return;
77
78#ifdef DEBUG
79  if (FLAG_print_interface_details) {
80    PrintF("%*s# Adding...\n", Nesting::current(), "");
81    PrintF("%*sthis = ", Nesting::current(), "");
82    this->Print(Nesting::current());
83    PrintF("%*s%s : ", Nesting::current(), "",
84           (*static_cast<String**>(name))->ToAsciiArray());
85    interface->Print(Nesting::current());
86  }
87#endif
88
89  ZoneHashMap** map = &Chase()->exports_;
90  ZoneAllocationPolicy allocator(zone);
91
92  if (*map == NULL)
93    *map = new ZoneHashMap(Match, ZoneHashMap::kDefaultHashMapCapacity,
94                           allocator);
95
96  ZoneHashMap::Entry* p = (*map)->Lookup(name, hash, !IsFrozen(), allocator);
97  if (p == NULL) {
98    // This didn't have name but was frozen already, that's an error.
99    *ok = false;
100  } else if (p->value == NULL) {
101    p->value = interface;
102  } else {
103#ifdef DEBUG
104    Nesting nested;
105#endif
106    static_cast<Interface*>(p->value)->Unify(interface, zone, ok);
107  }
108
109#ifdef DEBUG
110  if (FLAG_print_interface_details) {
111    PrintF("%*sthis' = ", Nesting::current(), "");
112    this->Print(Nesting::current());
113    PrintF("%*s# Added.\n", Nesting::current(), "");
114  }
115#endif
116}
117
118
119void Interface::Unify(Interface* that, Zone* zone, bool* ok) {
120  if (this->forward_) return this->Chase()->Unify(that, zone, ok);
121  if (that->forward_) return this->Unify(that->Chase(), zone, ok);
122  ASSERT(this->forward_ == NULL);
123  ASSERT(that->forward_ == NULL);
124
125  *ok = true;
126  if (this == that) return;
127  if (this->IsValue()) {
128    that->MakeValue(ok);
129    if (*ok && this->IsConst()) that->MakeConst(ok);
130    return;
131  }
132  if (that->IsValue()) {
133    this->MakeValue(ok);
134    if (*ok && that->IsConst()) this->MakeConst(ok);
135    return;
136  }
137
138#ifdef DEBUG
139  if (FLAG_print_interface_details) {
140    PrintF("%*s# Unifying...\n", Nesting::current(), "");
141    PrintF("%*sthis = ", Nesting::current(), "");
142    this->Print(Nesting::current());
143    PrintF("%*sthat = ", Nesting::current(), "");
144    that->Print(Nesting::current());
145  }
146#endif
147
148  // Merge the smaller interface into the larger, for performance.
149  if (this->exports_ != NULL && (that->exports_ == NULL ||
150      this->exports_->occupancy() >= that->exports_->occupancy())) {
151    this->DoUnify(that, ok, zone);
152  } else {
153    that->DoUnify(this, ok, zone);
154  }
155
156#ifdef DEBUG
157  if (FLAG_print_interface_details) {
158    PrintF("%*sthis' = ", Nesting::current(), "");
159    this->Print(Nesting::current());
160    PrintF("%*sthat' = ", Nesting::current(), "");
161    that->Print(Nesting::current());
162    PrintF("%*s# Unified.\n", Nesting::current(), "");
163  }
164#endif
165}
166
167
168void Interface::DoUnify(Interface* that, bool* ok, Zone* zone) {
169  ASSERT(this->forward_ == NULL);
170  ASSERT(that->forward_ == NULL);
171  ASSERT(!this->IsValue());
172  ASSERT(!that->IsValue());
173  ASSERT(this->index_ == -1);
174  ASSERT(that->index_ == -1);
175  ASSERT(*ok);
176
177#ifdef DEBUG
178    Nesting nested;
179#endif
180
181  // Try to merge all members from that into this.
182  ZoneHashMap* map = that->exports_;
183  if (map != NULL) {
184    for (ZoneHashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p)) {
185      this->DoAdd(p->key, p->hash, static_cast<Interface*>(p->value), zone, ok);
186      if (!*ok) return;
187    }
188  }
189
190  // If the new interface is larger than that's, then there were members in
191  // 'this' which 'that' didn't have. If 'that' was frozen that is an error.
192  int this_size = this->exports_ == NULL ? 0 : this->exports_->occupancy();
193  int that_size = map == NULL ? 0 : map->occupancy();
194  if (that->IsFrozen() && this_size > that_size) {
195    *ok = false;
196    return;
197  }
198
199  // Merge interfaces.
200  this->flags_ |= that->flags_;
201  that->forward_ = this;
202}
203
204
205#ifdef DEBUG
206void Interface::Print(int n) {
207  int n0 = n > 0 ? n : 0;
208
209  if (FLAG_print_interface_details) {
210    PrintF("%p", static_cast<void*>(this));
211    for (Interface* link = this->forward_; link != NULL; link = link->forward_)
212      PrintF("->%p", static_cast<void*>(link));
213    PrintF(" ");
214  }
215
216  if (IsUnknown()) {
217    PrintF("unknown\n");
218  } else if (IsConst()) {
219    PrintF("const\n");
220  } else if (IsValue()) {
221    PrintF("value\n");
222  } else if (IsModule()) {
223    PrintF("module %d %s{", Index(), IsFrozen() ? "" : "(unresolved) ");
224    ZoneHashMap* map = Chase()->exports_;
225    if (map == NULL || map->occupancy() == 0) {
226      PrintF("}\n");
227    } else if (n < 0 || n0 >= 2 * FLAG_print_interface_depth) {
228      // Avoid infinite recursion on cyclic types.
229      PrintF("...}\n");
230    } else {
231      PrintF("\n");
232      for (ZoneHashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p)) {
233        String* name = *static_cast<String**>(p->key);
234        Interface* interface = static_cast<Interface*>(p->value);
235        PrintF("%*s%s : ", n0 + 2, "", name->ToAsciiArray());
236        interface->Print(n0 + 2);
237      }
238      PrintF("%*s}\n", n0, "");
239    }
240  }
241}
242#endif
243
244} }  // namespace v8::internal
245