Remove create_hash_table options and simplify build system
[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 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 print STDERR "Creating hashtable for $file\n";
31 open(IN, $file) or die "No such file $file";
32
33 my @keys = ();
34 my @attrs = ();
35 my @values = ();
36 my @hashes = ();
37 my @table = ();
38 my @links = ();
39
40 my $hasSetter = "false";
41
42 my $includeBuiltin = 0;
43 my $inside = 0;
44 my $name;
45 my $pefectHashSize;
46 my $compactSize;
47 my $compactHashSizeMask;
48 my $banner = 0;
49 sub calcPerfectHashSize();
50 sub calcCompactHashSize();
51 sub output();
52 sub jsc_ucfirst($);
53 sub hashValue($);
54
55 while (<IN>) {
56     chomp;
57     s/^\s+//;
58     next if /^\#|^$/; # Comment or blank line. Do nothing.
59     if (/^\@begin/ && !$inside) {
60         if (/^\@begin\s*([:_\w]+)\s*\d*\s*$/) {
61             $inside = 1;
62             $name = $1;
63         } else {
64             print STDERR "WARNING: \@begin without table name, skipping $_\n";
65         }
66     } elsif (/^\@end\s*$/ && $inside) {
67         calcPerfectHashSize();
68         calcCompactHashSize();
69         output();
70
71         @keys = ();
72         @attrs = ();
73         @values = ();
74         @hashes = ();
75         @table = ();
76         @links = ();
77         $includeBuiltin = 0;
78
79         $inside = 0;
80     } elsif (/^(\S+)\s*(\S+)\s*([\w\|]*)\s*(\w*)\s*$/ && $inside) {
81         my $key = $1;
82         my $val = $2;
83         my $att = $3;
84         my $param = $4;
85
86         push(@keys, $key);
87         push(@attrs, length($att) > 0 ? $att : "0");
88
89         if ($val eq "JSBuiltin") {
90             $includeBuiltin = 1;
91         }
92
93         if ($att =~ m/Function/) {
94             push(@values, { "type" => "Function", "function" => $val, "params" => (length($param) ? $param : "") });
95             #printf STDERR "WARNING: Number of arguments missing for $key/$val\n" if (length($param) == 0);
96         } elsif ($att =~ m/Accessor/) {
97             my $get = $val;
98             my $put = "nullptr";
99             $hasSetter = "true";
100             push(@values, { "type" => "Accessor", "get" => $get, "put" => $put });
101         } elsif (length($att)) {
102             my $get = $val;
103             my $put = "0";
104             if (!($att =~ m/ReadOnly/)) {
105                 $put = "set" . jsc_ucfirst($val);
106             }
107             $hasSetter = "true";
108             push(@values, { "type" => "Property", "get" => $get, "put" => $put });
109         } else {
110             push(@values, { "type" => "Lexer", "value" => $val });        
111         }
112         push(@hashes, hashValue($key));
113     } elsif ($inside) {
114         die "invalid data {" . $_ . "}";
115     }
116 }
117
118 die "missing closing \@end" if ($inside);
119
120 sub jsc_ucfirst($)
121 {
122     my ($value) = @_;
123
124     if ($value =~ /js/) {
125         $value =~ s/js/JS/;
126         return $value;
127     }
128
129     return ucfirst($value);
130 }
131
132
133 sub ceilingToPowerOf2
134 {
135     my ($pefectHashSize) = @_;
136
137     my $powerOf2 = 1;
138     while ($pefectHashSize > $powerOf2) {
139         $powerOf2 <<= 1;
140     }
141
142     return $powerOf2;
143 }
144
145 sub calcPerfectHashSize()
146 {
147 tableSizeLoop:
148     for ($pefectHashSize = ceilingToPowerOf2(scalar @keys); ; $pefectHashSize += $pefectHashSize) {
149         my @table = ();
150         foreach my $key (@keys) {
151             my $h = hashValue($key) % $pefectHashSize;
152             next tableSizeLoop if $table[$h];
153             $table[$h] = 1;
154         }
155         last;
156     }
157 }
158
159 sub leftShift($$) {
160     my ($value, $distance) = @_;
161     return (($value << $distance) & 0xFFFFFFFF);
162 }
163
164 sub calcCompactHashSize()
165 {
166     my $compactHashSize = ceilingToPowerOf2(2 * @keys);
167     $compactHashSizeMask = $compactHashSize - 1;
168     $compactSize = $compactHashSize;
169     my $collisions = 0;
170     my $maxdepth = 0;
171     my $i = 0;
172     foreach my $key (@keys) {
173         my $depth = 0;
174         my $h = hashValue($key) % $compactHashSize;
175         while (defined($table[$h])) {
176             if (defined($links[$h])) {
177                 $h = $links[$h];
178                 $depth++;
179             } else {
180                 $collisions++;
181                 $links[$h] = $compactSize;
182                 $h = $compactSize;
183                 $compactSize++;
184             }
185         }
186         $table[$h] = $i;
187         $i++;
188         $maxdepth = $depth if ( $depth > $maxdepth);
189     }
190 }
191
192 # Paul Hsieh's SuperFastHash
193 # http://www.azillionmonkeys.com/qed/hash.html
194 sub hashValue($) {
195   my @chars = split(/ */, $_[0]);
196
197   # This hash is designed to work on 16-bit chunks at a time. But since the normal case
198   # (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
199   # were 16-bit chunks, which should give matching results
200
201   my $EXP2_32 = 4294967296;
202
203   my $hash = 0x9e3779b9;
204   my $l    = scalar @chars; #I wish this was in Ruby --- Maks
205   my $rem  = $l & 1;
206   $l = $l >> 1;
207
208   my $s = 0;
209
210   # Main loop
211   for (; $l > 0; $l--) {
212     $hash   += ord($chars[$s]);
213     my $tmp = leftShift(ord($chars[$s+1]), 11) ^ $hash;
214     $hash   = (leftShift($hash, 16)% $EXP2_32) ^ $tmp;
215     $s += 2;
216     $hash += $hash >> 11;
217     $hash %= $EXP2_32;
218   }
219
220   # Handle end case
221   if ($rem != 0) {
222     $hash += ord($chars[$s]);
223     $hash ^= (leftShift($hash, 11)% $EXP2_32);
224     $hash += $hash >> 17;
225   }
226
227   # Force "avalanching" of final 127 bits
228   $hash ^= leftShift($hash, 3);
229   $hash += ($hash >> 5);
230   $hash = ($hash% $EXP2_32);
231   $hash ^= (leftShift($hash, 2)% $EXP2_32);
232   $hash += ($hash >> 15);
233   $hash = $hash% $EXP2_32;
234   $hash ^= (leftShift($hash, 10)% $EXP2_32);
235
236   # Save 8 bits for StringImpl to use as flags.
237   $hash &= 0xffffff;
238
239   # This avoids ever returning a hash code of 0, since that is used to
240   # signal "hash not computed yet". Setting the high bit maintains
241   # reasonable fidelity to a hash code of 0 because it is likely to yield
242   # exactly 0 when hash lookup masks out the high bits.
243   $hash = (0x80000000 >> 8) if ($hash == 0);
244
245   return $hash;
246 }
247
248 sub output() {
249     if (!$banner) {
250         $banner = 1;
251         print "// Automatically generated from $file using $0. DO NOT EDIT!\n";
252     }
253
254     my $nameEntries = "${name}Values";
255     $nameEntries =~ s/:/_/g;
256     my $nameIndex = "${name}Index";
257     $nameIndex =~ s/:/_/g;
258
259     print "\n";
260     print "#include \"JSCBuiltins.h\"\n" if ($includeBuiltin);
261     print "#include \"Lookup.h\"\n";
262     print "\n";
263     print "namespace JSC {\n";
264     print "\n";
265     print "static const struct CompactHashIndex ${nameIndex}\[$compactSize\] = {\n";
266     for (my $i = 0; $i < $compactSize; $i++) {
267         my $T = -1;
268         if (defined($table[$i])) { $T = $table[$i]; }
269         my $L = -1;
270         if (defined($links[$i])) { $L = $links[$i]; }
271         print "    { $T, $L },\n";
272     }
273     print "};\n";
274     print "\n";
275
276     my $packedSize = scalar @keys;
277     print "static const struct HashTableValue ${nameEntries}\[$packedSize\] = {\n";
278     my $i = 0;
279     foreach my $key (@keys) {
280         my $firstValue = "";
281         my $secondValue = "";
282         my $firstCastStr = "";
283         my $secondCastStr = "";
284
285         if ($values[$i]{"type"} eq "Function") {
286             $firstCastStr = "static_cast<NativeFunction>";
287             $firstValue = $values[$i]{"function"};
288             $secondValue = $values[$i]{"params"};
289         } elsif ($values[$i]{"type"} eq "Accessor") {
290             $firstCastStr = "static_cast<NativeFunction>";
291             $secondCastStr = "static_cast<NativeFunction>";
292             $firstValue = $values[$i]{"get"};
293             $secondValue = $values[$i]{"put"};
294         } elsif ($values[$i]{"type"} eq "Property") {
295             $firstCastStr = "static_cast<PropertySlot::GetValueFunc>";
296             $secondCastStr = "static_cast<PutPropertySlot::PutValueFunc>";
297             $firstValue = $values[$i]{"get"};
298             $secondValue = $values[$i]{"put"};
299         } elsif ($values[$i]{"type"} eq "Lexer") {
300             $firstValue = $values[$i]{"value"};
301             $secondValue = "0";
302         }
303
304         my $intrinsic = "NoIntrinsic";
305         $intrinsic = "FromCharCodeIntrinsic" if ($key eq "fromCharCode");
306         if ($name eq "arrayPrototypeTable") {
307             $intrinsic = "ArrayPushIntrinsic" if ($key eq "push");
308             $intrinsic = "ArrayPopIntrinsic" if ($key eq "pop");
309         }
310         if ($name eq "regExpPrototypeTable") {
311             $intrinsic = "RegExpExecIntrinsic" if ($key eq "exec");
312             $intrinsic = "RegExpTestIntrinsic" if ($key eq "test");
313         }
314
315         if ($values[$i]{"type"} eq "Function" && $firstValue eq "JSBuiltin")  {
316             my $tableHead = $name;
317             $tableHead =~ s/Table$//;
318             print "   { \"$key\", (($attrs[$i]) & ~Function) | Builtin, $intrinsic, { (intptr_t)static_cast<BuiltinGenerator>(" . $tableHead . ucfirst($key) . "CodeGenerator), (intptr_t)$secondValue } },\n";
319         }
320         else {
321             print "   { \"$key\", $attrs[$i], $intrinsic, { (intptr_t)" . $firstCastStr . "($firstValue), (intptr_t)" . $secondCastStr . "($secondValue) } },\n";
322         }
323         $i++;
324     }
325     print "};\n";
326     print "\n";
327     print "static const struct HashTable $name =\n";
328     print "    \{ $packedSize, $compactHashSizeMask, $hasSetter, $nameEntries, $nameIndex \};\n";
329     print "\n";
330     print "} // namespace JSC\n";
331 }