Speed up JSGlobalObject initialization by making some properties lazy
[WebKit-https.git] / Source / JavaScriptCore / create_hash_table
1 #! /usr/bin/perl -w
2 #
3 # Static Hashtable Generator
4 #
5 # (c) 2000-2002 by Harri Porten <porten@kde.org> and
6 #                  David Faure <faure@kde.org>
7 # Modified (c) 2004 by Nikolas Zimmermann <wildfox@kde.org>
8 # Copyright (C) 2007, 2008, 2009, 2015-2016 Apple Inc. All rights reserved.
9 #
10 # This library is free software; you can redistribute it and/or
11 # modify it under the terms of the GNU Lesser General Public
12 # License as published by the Free Software Foundation; either
13 # version 2 of the License, or (at your option) any later version.
14 #
15 # This library is distributed in the hope that it will be useful,
16 # but WITHOUT ANY WARRANTY; without even the implied warranty of
17 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 # Lesser General Public License for more details.
19 #
20 # You should have received a copy of the GNU Lesser General Public
21 # License along with this library; if not, write to the Free Software
22 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
23 #
24  
25 use strict;
26 use Getopt::Long qw(:config pass_through);
27
28 my $file = shift @ARGV or die("Must provide source file as final argument.");
29
30 open(IN, $file) or die "No such file $file";
31
32 my @keys = ();
33 my @attrs = ();
34 my @values = ();
35 my @hashes = ();
36 my @table = ();
37 my @links = ();
38
39 my $hasSetter = "false";
40
41 my $includeBuiltin = 0;
42 my $inside = 0;
43 my $name;
44 my $pefectHashSize;
45 my $compactSize;
46 my $compactHashSizeMask;
47 my $banner = 0;
48 sub calcPerfectHashSize();
49 sub calcCompactHashSize();
50 sub output();
51 sub jsc_ucfirst($);
52 sub hashValue($);
53
54 while (<IN>) {
55     chomp;
56     s/^\s+//;
57     next if /^\#|^$/; # Comment or blank line. Do nothing.
58     if (/^\@begin/ && !$inside) {
59         if (/^\@begin\s*([:_\w]+)\s*\d*\s*$/) {
60             $inside = 1;
61             $name = $1;
62         } else {
63             print STDERR "WARNING: \@begin without table name, skipping $_\n";
64         }
65     } elsif (/^\@end\s*$/ && $inside) {
66         calcPerfectHashSize();
67         calcCompactHashSize();
68         output();
69
70         @keys = ();
71         @attrs = ();
72         @values = ();
73         @hashes = ();
74         @table = ();
75         @links = ();
76         $includeBuiltin = 0;
77
78         $inside = 0;
79     } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
80         my $key = $1;
81         my $val = $2;
82         my $att = $3;
83         my $param = $4;
84
85         push(@keys, $key);
86         push(@attrs, length($att) > 0 ? $att : "0");
87
88         if ($val eq "JSBuiltin") {
89             $includeBuiltin = 1;
90         }
91
92         if ($att =~ m/Function/) {
93             push(@values, { "type" => "Function", "function" => $val, "params" => (length($param) ? $param : "") });
94             #printf STDERR "WARNING: Number of arguments missing for $key/$val\n" if (length($param) == 0);
95         } elsif ($att =~ m/Accessor/) {
96             my $get = $val;
97             my $put = "nullptr";
98             $hasSetter = "true";
99             push(@values, { "type" => "Accessor", "get" => $get, "put" => $put });
100         } elsif ($att =~ m/CellProperty/) {
101             my $property = $val;
102             push(@values, { "type" => "CellProperty", "property" => $property });
103         } elsif ($att =~ m/ClassStructure/) {
104             my $property = $val;
105             push(@values, { "type" => "ClassStructure", "property" => $property });
106         } elsif ($att =~ m/PropertyCallback/) {
107             my $cback = $val;
108             push(@values, { "type" => "PropertyCallback", "cback" => $cback });
109         } elsif (length($att)) {
110             my $get = $val;
111             my $put = "0";
112             if (!($att =~ m/ReadOnly/)) {
113                 $put = "set" . jsc_ucfirst($val);
114             }
115             $hasSetter = "true";
116             push(@values, { "type" => "Property", "get" => $get, "put" => $put });
117         } else {
118             push(@values, { "type" => "Lexer", "value" => $val });        
119         }
120         push(@hashes, hashValue($key));
121     } elsif ($inside) {
122         die "invalid data {" . $_ . "}";
123     }
124 }
125
126 die "missing closing \@end" if ($inside);
127
128 sub jsc_ucfirst($)
129 {
130     my ($value) = @_;
131
132     if ($value =~ /js/) {
133         $value =~ s/js/JS/;
134         return $value;
135     }
136
137     return ucfirst($value);
138 }
139
140
141 sub ceilingToPowerOf2
142 {
143     my ($pefectHashSize) = @_;
144
145     my $powerOf2 = 1;
146     while ($pefectHashSize > $powerOf2) {
147         $powerOf2 <<= 1;
148     }
149
150     return $powerOf2;
151 }
152
153 sub calcPerfectHashSize()
154 {
155 tableSizeLoop:
156     for ($pefectHashSize = ceilingToPowerOf2(scalar @keys); ; $pefectHashSize += $pefectHashSize) {
157         my @table = ();
158         foreach my $key (@keys) {
159             my $h = hashValue($key) % $pefectHashSize;
160             next tableSizeLoop if $table[$h];
161             $table[$h] = 1;
162         }
163         last;
164     }
165 }
166
167 sub leftShift($$) {
168     my ($value, $distance) = @_;
169     return (($value << $distance) & 0xFFFFFFFF);
170 }
171
172 sub calcCompactHashSize()
173 {
174     my $compactHashSize = ceilingToPowerOf2(2 * @keys);
175     $compactHashSizeMask = $compactHashSize - 1;
176     $compactSize = $compactHashSize;
177     my $collisions = 0;
178     my $maxdepth = 0;
179     my $i = 0;
180     foreach my $key (@keys) {
181         my $depth = 0;
182         my $h = hashValue($key) % $compactHashSize;
183         while (defined($table[$h])) {
184             if (defined($links[$h])) {
185                 $h = $links[$h];
186                 $depth++;
187             } else {
188                 $collisions++;
189                 $links[$h] = $compactSize;
190                 $h = $compactSize;
191                 $compactSize++;
192             }
193         }
194         $table[$h] = $i;
195         $i++;
196         $maxdepth = $depth if ( $depth > $maxdepth);
197     }
198 }
199
200 # Paul Hsieh's SuperFastHash
201 # http://www.azillionmonkeys.com/qed/hash.html
202 sub hashValue($) {
203   my @chars = split(/ */, $_[0]);
204
205   # This hash is designed to work on 16-bit chunks at a time. But since the normal case
206   # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
207   # were 16-bit chunks, which should give matching results
208
209   my $EXP2_32 = 4294967296;
210
211   my $hash = 0x9e3779b9;
212   my $l    = scalar @chars; #I wish this was in Ruby --- Maks
213   my $rem  = $l & 1;
214   $l = $l >> 1;
215
216   my $s = 0;
217
218   # Main loop
219   for (; $l > 0; $l--) {
220     $hash   += ord($chars[$s]);
221     my $tmp = leftShift(ord($chars[$s+1]), 11) ^ $hash;
222     $hash   = (leftShift($hash, 16)% $EXP2_32) ^ $tmp;
223     $s += 2;
224     $hash += $hash >> 11;
225     $hash %= $EXP2_32;
226   }
227
228   # Handle end case
229   if ($rem != 0) {
230     $hash += ord($chars[$s]);
231     $hash ^= (leftShift($hash, 11)% $EXP2_32);
232     $hash += $hash >> 17;
233   }
234
235   # Force "avalanching" of final 127 bits
236   $hash ^= leftShift($hash, 3);
237   $hash += ($hash >> 5);
238   $hash = ($hash% $EXP2_32);
239   $hash ^= (leftShift($hash, 2)% $EXP2_32);
240   $hash += ($hash >> 15);
241   $hash = $hash% $EXP2_32;
242   $hash ^= (leftShift($hash, 10)% $EXP2_32);
243
244   # Save 8 bits for StringImpl to use as flags.
245   $hash &= 0xffffff;
246
247   # This avoids ever returning a hash code of 0, since that is used to
248   # signal "hash not computed yet". Setting the high bit maintains
249   # reasonable fidelity to a hash code of 0 because it is likely to yield
250   # exactly 0 when hash lookup masks out the high bits.
251   $hash = (0x80000000 >> 8) if ($hash == 0);
252
253   return $hash;
254 }
255
256 sub output() {
257     if (!$banner) {
258         $banner = 1;
259         print "// Automatically generated from $file using $0. DO NOT EDIT!\n";
260     }
261
262     my $nameEntries = "${name}Values";
263     $nameEntries =~ s/:/_/g;
264     my $nameIndex = "${name}Index";
265     $nameIndex =~ s/:/_/g;
266
267     print "\n";
268     print "#include \"JSCBuiltins.h\"\n" if ($includeBuiltin);
269     print "#include \"Lookup.h\"\n";
270     print "\n";
271     print "namespace JSC {\n";
272     print "\n";
273     print "static const struct CompactHashIndex ${nameIndex}\[$compactSize\] = {\n";
274     for (my $i = 0; $i < $compactSize; $i++) {
275         my $T = -1;
276         if (defined($table[$i])) { $T = $table[$i]; }
277         my $L = -1;
278         if (defined($links[$i])) { $L = $links[$i]; }
279         print "    { $T, $L },\n";
280     }
281     print "};\n";
282     print "\n";
283
284     my $packedSize = scalar @keys;
285     print "static const struct HashTableValue ${nameEntries}\[$packedSize\] = {\n";
286     my $i = 0;
287     foreach my $key (@keys) {
288         my $firstValue = "";
289         my $secondValue = "";
290         my $firstCastStr = "";
291         my $secondCastStr = "";
292
293         if ($values[$i]{"type"} eq "Function") {
294             $firstCastStr = "static_cast<NativeFunction>";
295             $firstValue = $values[$i]{"function"};
296             $secondValue = $values[$i]{"params"};
297         } elsif ($values[$i]{"type"} eq "Accessor") {
298             $firstCastStr = "static_cast<NativeFunction>";
299             $secondCastStr = "static_cast<NativeFunction>";
300             $firstValue = $values[$i]{"get"};
301             $secondValue = $values[$i]{"put"};
302         } elsif ($values[$i]{"type"} eq "Property") {
303             $firstCastStr = "static_cast<PropertySlot::GetValueFunc>";
304             $secondCastStr = "static_cast<PutPropertySlot::PutValueFunc>";
305             $firstValue = $values[$i]{"get"};
306             $secondValue = $values[$i]{"put"};
307         } elsif ($values[$i]{"type"} eq "Lexer") {
308             $firstValue = $values[$i]{"value"};
309             $secondValue = "0";
310         } elsif ($values[$i]{"type"} eq "CellProperty" || $values[$i]{"type"} eq "ClassStructure") {
311             $values[$i]{"property"} =~ /\A([a-zA-Z0-9_]+)::(.*)\Z/ or die;
312             $firstValue = "OBJECT_OFFSETOF($1, $2)";
313             $secondValue = "0";
314         } elsif ($values[$i]{"type"} eq "PropertyCallback") {
315             $firstCastStr = "static_cast<LazyPropertyCallback>";
316             $firstValue = $values[$i]{"cback"};
317             $secondValue = "0";
318         }
319
320         my $intrinsic = "NoIntrinsic";
321         $intrinsic = "FromCharCodeIntrinsic" if ($key eq "fromCharCode");
322         if ($name eq "arrayPrototypeTable") {
323             $intrinsic = "ArrayPushIntrinsic" if ($key eq "push");
324             $intrinsic = "ArrayPopIntrinsic" if ($key eq "pop");
325         }
326
327         if ($values[$i]{"type"} eq "Function" && $firstValue eq "JSBuiltin")  {
328             my $tableHead = $name;
329             $tableHead =~ s/Table$//;
330             print "   { \"$key\", (($attrs[$i]) & ~Function) | Builtin, $intrinsic, { (intptr_t)static_cast<BuiltinGenerator>(" . $tableHead . ucfirst($key) . "CodeGenerator), (intptr_t)$secondValue } },\n";
331         }
332         else {
333             print "   { \"$key\", $attrs[$i], $intrinsic, { (intptr_t)" . $firstCastStr . "($firstValue), (intptr_t)" . $secondCastStr . "($secondValue) } },\n";
334         }
335         $i++;
336     }
337     print "};\n";
338     print "\n";
339     print "static const struct HashTable $name =\n";
340     print "    \{ $packedSize, $compactHashSizeMask, $hasSetter, $nameEntries, $nameIndex \};\n";
341     print "\n";
342     print "} // namespace JSC\n";
343 }