--- a/js/src/frontend/BinaryAST.cpp
+++ b/js/src/frontend/BinaryAST.cpp
@@ -1,23 +1,27 @@
// ---- Ongoing experiment: binary ast serializer/parser
#include <iostream>
#include <istream>
#include <sstream>
+#include <strstream>
#include "mozilla/Attributes.h"
#include "frontend/BinaryAST.h"
#include "frontend/ParseNode.h"
#include "jsatom.h"
#include "jsopcode.h"
namespace js {
namespace frontend {
+// #define DEBUG_HEADER 1
+
+using VariantKind = StringTree::VariantKind;
/**
* A marker for presence/absence.
*/
enum OptionValue {
OptionIsHere = -1,
OptionIsAbsent = -2,
};
@@ -30,35 +34,16 @@ const char FOOTER[] = "Behold the footer
// List of names of ParseNodeKind, to simplify logging.
const char* NAMES[] = {
#define EMIT_SLOT(name) "PNK_" #name,
FOR_EACH_PARSE_NODE_KIND(EMIT_SLOT)
#undef EMIT_SLOT
"PNK_LIMIT"
};
-size_t totalByteLength(const StringTree::Concat* concat) {
- size_t total = sizeof concat->children.length()
- + (sizeof StringTree::variantKind);
- for (const UniquePtr<StringTree>& item: concat->children) {
- total
- += sizeof HEADER
- + sizeof item->kind
- + sizeof item->byteLength
- + item->byteLength
- + sizeof FOOTER;
- }
- return total;
-}
-
-size_t totalByteLength(const StringTree::Leaf* leaf) {
- return leaf->data.length()
- + sizeof StringTree::variantKind;
-}
-
// FIXME: We should rather have a StringTreeWriter.
StringTree::~StringTree()
{
switch (variantKind) {
case VariantKind::IsLeaf:
delete data.leaf;
return;
case VariantKind::IsConcat:
@@ -66,17 +51,16 @@ StringTree::~StringTree()
return;
}
MOZ_CRASH();
}
StringTree::StringTree(ParseNodeKind k, Leaf* leaf)
: variantKind(VariantKind::IsLeaf)
, data(leaf)
- , byteLength(totalByteLength(leaf))
, kind(k)
{}
StringTree::Leaf::Leaf()
: data("")
{ }
StringTree::Leaf::Leaf(const std::string&& data_)
@@ -105,17 +89,16 @@ const StringTree::Leaf&
StringTree::asLeaf() const {
MOZ_ASSERT(isLeaf());
return *data.leaf;
}
StringTree::StringTree(ParseNodeKind k, Concat* concat)
: variantKind(VariantKind::IsConcat)
, data(concat)
- , byteLength(totalByteLength(concat))
, kind(k)
{}
StringTree::Concat::Concat(mozilla::Vector<UniquePtr<StringTree>>&& children_)
: children(Move(children_))
{}
/*static*/ StringTree*
@@ -142,157 +125,124 @@ StringTree::asConcat() const {
return *data.concat;
}
const mozilla::Vector<UniquePtr<StringTree>>&
StringTree::children() const {
return asConcat().children;
}
-/*static*/ StringTree*
-StringTree::read(JSContext* cx, std::istringstream& in) {
- char header[sizeof HEADER + 1];
- in.read(header, sizeof HEADER);
- if (strncmp(header, HEADER, sizeof HEADER) != 0) {
- MOZ_CRASH("Bad header");
- }
+void
+StringTree::write(std::ostringstream& out) const {
+ // std::cerr << "StringTree::write at " << out.tellp() << "\n";
+#if DEBUG_HEADER
+ // std::cerr << "StringTree::write HEADER at " << out.tellp() << "\n";
+ out.write(HEADER, sizeof HEADER - 1);
+#endif // DEBUG_HEADER
+
+ // std::cerr << "StringTree::write kind at " << out.tellp() << "\n";
+ out.write((const char*)&kind, sizeof kind);
+
+ // std::cerr << "StringTree::write " << NAMES[kind] << "\n";
+ if (kind != PNK_LIMIT) {
+
+#if DEBUG_HEADER
+ // std::cerr << "StringTree::write variantKind at " << out.tellp() << "\n";
+ const unsigned char char_variant = variantKind;
+ out.write((const char*)&char_variant, sizeof char_variant);
+ MOZ_ASSERT(variantKind == VariantKind::IsLeaf || variantKind == VariantKind::IsConcat);
+#endif // DEBUG_HEADER
+
+ std::ostringstream sub_out;
+ if (isLeaf()) {
+ const Leaf& leaf = asLeaf();
+
+ const size_t byteLength = leaf.data.length();
+
+ jit::CompactBufferWriter lengthWriter;
+ lengthWriter.writeUnsigned((uint32_t)byteLength);
+ out.write((const char*)lengthWriter.buffer(), lengthWriter.length());
- ParseNodeKind kind;
- in.read((char*)&kind, sizeof kind);
- if (kind >= mozilla::ArrayLength(NAMES)) {
- MOZ_CRASH("Bad kind");
+ const size_t byteStart = out.tellp();
+ out << leaf.data;
+ const size_t byteStop = out.tellp();
+ MOZ_ASSERT(byteLength == byteStop - byteStart);
+
+ } else {
+ const Concat& concat = asConcat();
+
+ {
+ jit::CompactBufferWriter lengthWriter;
+ lengthWriter.writeUnsigned((uint32_t)concat.children.length());
+ sub_out.write((const char*)lengthWriter.buffer(), lengthWriter.length());
+ for (const UniquePtr<StringTree>& tree: concat.children) {
+ tree->write(sub_out);
+ }
+ }
+
+ const std::string sub_str = sub_out.str();
+ const size_t byteLength = sub_str.length();
+ {
+ jit::CompactBufferWriter lengthWriter;
+ lengthWriter.writeUnsigned((uint32_t)byteLength);
+
+ // std::cerr << "StringTree::write byteLength at " << out.tellp() << "\n";
+ out.write((const char*)lengthWriter.buffer(), lengthWriter.length());
+
+ // std::cerr << "StringTree::write concat byteLength " << byteLength << "\n";
+ // std::cerr << "StringTree::write concat length " << concat.children.length() << "\n";
+ }
+
+
+ const size_t byteStart = out.tellp();
+ out << sub_str;
+ const size_t byteStop = out.tellp();
+ // std::cerr << "StringTree::write length at " << byteStart << "\n";
+ MOZ_ASSERT(byteLength == byteStop - byteStart);
+ }
}
- size_t byteLength;
- in.read((char*)&byteLength, sizeof byteLength);
- VariantKind variant;
- in.read((char*)&variant, sizeof variant);
-
- MOZ_ASSERT(variant == VariantKind::IsLeaf || variant == VariantKind::IsConcat);
-
- const size_t byteStart = in.tellg();
-
- UniquePtr<StringTree> result;
-
- if (variant == VariantKind::IsLeaf) {
- char* buf = new char[byteLength];
- in.read(buf, byteLength);
- std::string data(buf, byteLength);
- delete[] buf;
- result = UniquePtr<StringTree>(StringTree::makeLeaf(cx, kind, Move(data)));
- } else {
- size_t length = 0;
- in.read((char*)&length, sizeof length);
-
- mozilla::Vector<UniquePtr<StringTree>> children;
- // FIXME: Prealloc.
- for (size_t i = 0; i < length; ++i) {
- if (!children.append(UniquePtr<StringTree>(StringTree::read(cx, in)))) {
- MOZ_CRASH();
- return nullptr;
- }
- }
- result = UniquePtr<StringTree>(StringTree::makeConcat(cx, kind, Move(children)));
- }
- const size_t byteStop = in.tellg();
-
- MOZ_ASSERT(byteStop - byteStart == byteLength + sizeof byteLength);
-
- char footer[sizeof FOOTER + 1];
- in.read(footer, sizeof FOOTER);
- if (strncmp(footer, FOOTER, sizeof FOOTER) != 0) {
- MOZ_CRASH("Bad footer");
- }
-
- return result.release();
-}
-
-void
-StringTree::write(std::ostringstream& out) const {
- out.write(HEADER, sizeof HEADER);
- out.write((const char*)&kind, sizeof kind);
-
- out.write((const char*)&byteLength, sizeof byteLength);
- const size_t byteStart = out.tellp();
-
- out.write((const char*)&variantKind, sizeof variantKind);
-
- if (isLeaf()) {
- const Leaf& leaf = asLeaf();
- out << leaf.data;
-// std::cerr << "writeLeaf() (" << byteLength << ") => " << leaf.data << "\n";
- } else {
- const Concat& concat = asConcat();
- const size_t length = concat.children.length();
- out.write((const char*)&length, sizeof length);
- for (const UniquePtr<StringTree>& tree: concat.children) {
- tree->write(out);
- }
- }
- const size_t byteStop = out.tellp();
- MOZ_ASSERT(byteLength == byteStop - byteStart);
-
- out.write(FOOTER, sizeof(FOOTER));
+#if DEBUG_HEADER
+ out.write(FOOTER, sizeof FOOTER - 1);
+#endif // DEBUG_HEADER
}
using Leaf = StringTree::Leaf;
using Concat = StringTree::Concat;
void serializeAtom(JSContext* cx, JSAtom* atom, std::string& result)
{
std::ostringstream out;
if (atom) {
- OptionValue kind(OptionIsHere);
- out.write((const char*)&kind, sizeof kind);
-
RootedString string(cx, atom);
JSAutoByteString bs;
- if (!bs.encodeUtf8(cx, string)) {
+ if (!bs.encodeUtf8(cx, string)) { // 0 terminated, right?
MOZ_CRASH();
}
- const size_t size = strlen(bs.ptr());
- out.write((const char*)&size, sizeof size);
- out.write(bs.ptr(), size);
+ out.write(bs.ptr(), bs.length());
} else {
- OptionValue kind(OptionIsAbsent);
- out.write((const char*)&kind, sizeof kind);
+ const char zero[2] = { 0, 0 };
+ out.write((const char*)&zero, sizeof zero);
}
result = Move(out.str());
}
JSAtom* deserializeAtom(JSContext* cx, const std::string& data)
{
- std::istringstream in(data); // FIXME: Useless copy.
-
- OptionValue op;
- in.read((char*)&op, sizeof(op));
-
- if (op == OptionIsHere) {
- size_t size;
- in.read((char*)&size, sizeof(size));
-
- char* buf(new char[size + 1]);
- in.read(buf, size);
+ // Special constant '\0\0' for empty atoms.
+ if (data.length() == 2) {
+ if (data[0] == 0 && data[1] == 0) {
+ return nullptr;
+ }
+ }
- {
- buf[size] = '\0';
- // fprintf(stderr, "binParseAtom: \"%s\" (%zu)\n", buf, size);
- }
-
- // FIXME: We don't need copy.
- JSAtom* result = js::Atomize(cx, buf, size);
- delete[] buf;
- return result;
- } else if (op == OptionIsAbsent) {
- return nullptr;
- }
- MOZ_CRASH("Invalid variant");
+ return js::Atomize(cx, &data[0], data.length());
}
MOZ_MUST_USE
bool deserializePropertyName(JSContext* cx, const std::string& data, MutableHandle<PropertyName*> label) {
RootedAtom atom(cx, deserializeAtom(cx, data));
if (atom) {
label.set(atom->asPropertyName());
} else {
@@ -300,17 +250,17 @@ bool deserializePropertyName(JSContext*
}
return true;
}
MOZ_MUST_USE StringTree*
treeSerialize(JSContext* cx, const ParseNode* node, std::ostringstream& debug)
{
const ParseNodeKind kind = node ? node->getKind() : PNK_LIMIT;
-// std::cerr << "treeSerialize " << NAMES[kind] << "\n";
+// // std::cerr << "treeSerialize " << NAMES[kind] << "\n";
debug << NAMES[kind] << " ";
switch (kind) {
// Empty tree
case PNK_LIMIT: {
return StringTree::makeLeaf(cx, PNK_LIMIT);
}
// Body
@@ -574,135 +524,225 @@ treeSerialize(JSContext* cx, const Parse
class TreeParser MOZ_RAII {
public:
TreeParser(JSContext* cx_, ParseNodeAllocator& alloc, std::istringstream& in_, std::ostringstream& debug_)
: cx(cx_)
, in(in_)
, debug(debug_)
, functionDepth(0)
+ , numberOfNodes(0)
, allocator(alloc)
- { }
+ {
+ // std::cerr << "TreeParser starts with offset " << in.tellg() << "\n";
+ }
~TreeParser() {
MOZ_ASSERT(in.peek() == std::char_traits<char>::eof());
MOZ_ASSERT(functionDepth == 0);
+ // std::cerr << "TreeParser complete after " << numberOfNodes << " nodes\n";
}
// Parse a subtree as a string. The subtree must have been serialized as a string.
// FIXME: Crappy documentation suggests crappy concepts. Clean this up.
void parseBuf(ParseNodeKind& kind, std::string& buf)
{
- size_t byteLength;
- readHeader(kind, byteLength);
+ // std::cerr << "parseBuf\n";
- const size_t byteStart = in.tellg();
+ const size_t previousByteLength = currentByteLength;
+ const size_t previousByteStart = currentByteStart;
+ const ParseNodeKind previousKind = currentKind;
+#if DEBUG_HEADER
+ const VariantKind previousVariant = currentVariant;
+#endif // DEBUG_HEADER
+ handleHeader();
+#if DEBUG_HEADER
+ MOZ_ASSERT(currentVariant == VariantKind::IsLeaf);
+#endif
+ kind = currentKind;
+ MOZ_ASSERT(currentKind != PNK_LIMIT);
+
readNodeAsLeaf(buf);
- readFooter(byteStart, byteLength);
+ handleFooter();
+
+ currentByteLength = previousByteLength;
+ currentByteStart = previousByteStart;
+ currentKind = previousKind;
+#if DEBUG_HEADER
+ currentVariant = previousVariant;
+#endif // DEBUG_HEADER
}
// Parse a subtree as a ParseNode.
MOZ_MUST_USE ParseNode* parseNode()
{
- ParseNodeKind kind;
- size_t byteLength;
- readHeader(kind, byteLength);
+ // std::cerr << "parseNode " << in.tellg() << "\n";
- const size_t byteStart = in.tellg();
+ const size_t previousByteLength = currentByteLength;
+ const size_t previousByteStart = currentByteStart;
+ const ParseNodeKind previousKind = currentKind;
+#if DEBUG_HEADER
+ const VariantKind previousVariant = currentVariant;
+#endif // DEBUG_HEADER
+
+ handleHeader();
// Actually parse subtree.
- UniquePtr<ParseNode> result(parseNode(kind));
+ UniquePtr<ParseNode> result(parseNode(currentKind));
+
+ handleFooter();
- readFooter(byteStart, byteLength);
+ currentByteLength = previousByteLength;
+ currentByteStart = previousByteStart;
+ currentKind = previousKind;
+#if DEBUG_HEADER
+ currentVariant = previousVariant;
+#endif // DEBUG_HEADER
+
return result.release();
}
+ // Note: This should NOT be called if the kind is PNK_LIMIT.
void readNodeAsLeaf(std::string& buf)
{
- size_t byteLength;
- in.read((char*)&byteLength, sizeof byteLength);
+ // std::cerr << "readNodeAsLeaf\n";
+#if DEBUG_HEADER
+ MOZ_ASSERT(currentVariant == VariantKind::IsLeaf);
+#endif
- StringTree::VariantKind variant;
- in.read((char*)&variant, sizeof variant);
- MOZ_ASSERT(variant == StringTree::VariantKind::IsLeaf);
-
- const size_t bufLength = byteLength - sizeof variant;
- buf.resize(bufLength);
- in.read(&buf[0], bufLength);
+ buf.resize(currentByteLength);
+ in.read(&buf[0], currentByteLength);
+ }
-// std::cerr << "readNodeAsLeaf: (" << bufLength << ")" << buf << "\n";
- }
size_t readNodeAsConcat() {
- size_t byteLength;
- in.read((char*)&byteLength, sizeof byteLength);
+#if DEBUG_HEADER
+ MOZ_ASSERT(currentVariant == VariantKind::IsConcat);
+#endif
- StringTree::VariantKind variant;
- in.read((char*)&variant, sizeof variant);
- MOZ_ASSERT(variant == StringTree::VariantKind::IsConcat);
+ // std::cerr << "readNodeAsConcat length at " << in.tellg() << "\n";
+ const size_t length = readVariableLength();
- size_t length;
- in.read((char*)&length, sizeof length);
-
+ // std::cerr << "readNodeAsConcat: length " << length << "\n";
return length;
}
- ParseNode* freeTree(ParseNode* pn) { return allocator.freeTree(pn); }
+ ParseNode* freeTree(ParseNode* pn) {
+ return allocator.freeTree(pn);
+ }
+
private:
JSContext* cx;
std::istringstream& in;
std::ostringstream& debug;
size_t functionDepth;
+ size_t numberOfNodes;
+ size_t currentByteLength;
+ size_t currentByteStart;
+ ParseNodeKind currentKind;
+#if DEBUG_HEADER
+ VariantKind currentVariant;
+#endif // DEBUG_HEADER
+
JS_DECLARE_NEW_METHODS(new_, allocParseNode, inline)
ParseNodeAllocator& allocator;
ParseNode* allocParseNode(size_t size) {
MOZ_ASSERT(size == sizeof(ParseNode));
return static_cast<ParseNode*>(allocator.allocNode());
}
- void readHeader(ParseNodeKind& kind, size_t& byteLength)
+ void handleHeader()
{
- std::string header(sizeof HEADER, '\0');
- in.read(&header[0], sizeof HEADER);
+ ++numberOfNodes;
+#if DEBUG_HEADER
+ // std::cerr << "handleHeader HEADER at " << in.tellg() << "\n";
+ std::string header(sizeof HEADER - 1, '\0');
+ in.read(&header[0], sizeof HEADER - 1);
if (header.compare(0, sizeof HEADER - 1, HEADER) != 0) {
MOZ_CRASH("Bad header");
}
+#endif // DEBUG_HEADER
- in.read((char*)&kind, sizeof kind);
- if (kind >= mozilla::ArrayLength(NAMES)) {
+ // std::cerr << "handleHeader kind at " << in.tellg() << "\n";
+ unsigned char char_kind;
+ in.read((char*)&char_kind, sizeof char_kind);
+ if (char_kind >= mozilla::ArrayLength(NAMES)) {
MOZ_CRASH("Bad kind");
}
+ currentKind = (ParseNodeKind)char_kind;
+
+ if (currentKind == PNK_LIMIT) {
+ currentByteLength = 0;
+#if DEBUG_HEADER
+ currentVariant = VariantKind::IsLeaf;
+#endif // DEBUG_HEADER
+ } else {
+#if DEBUG_HEADER
+ // std::cerr << "handleHeader variantKind at " << in.tellg() << "\n";
+ unsigned char char_variant;
+ in.read((char*)&char_variant, sizeof char_variant);
+ currentVariant = (VariantKind)char_variant;
+ // std::cerr << "handleHeader reading variant: " << currentVariant << "\n";
+ MOZ_ASSERT(currentVariant == VariantKind::IsLeaf || currentVariant == VariantKind::IsConcat);
+#endif // DEBUG_HEADER
+
+ // std::cerr << "handleHeader byteLength at " << in.tellg() << "\n";
+
+ currentByteLength = readVariableLength();
+ }
- // Lookahead bytelength
- in.read((char*)&byteLength, sizeof byteLength);
- in.seekg(-sizeof byteLength, std::ios_base::seekdir::cur);
+ currentByteStart = in.tellg();
}
- void readFooter(const size_t byteStart, const size_t byteLength) {
+ void handleFooter() {
+ // std::cerr << "handleFooter " << in.tellg() << "\n";
+
// Check byteLength, footer
const size_t byteStop = in.tellg();
- MOZ_ASSERT(byteStop - byteStart == byteLength + sizeof byteLength);
+ MOZ_ASSERT(byteStop - currentByteStart == currentByteLength);
- std::string footer(sizeof FOOTER, '\0');
- in.read(&footer[0], sizeof FOOTER);
+#if DEBUG_HEADER
+ std::string footer(sizeof FOOTER - 1, '\0');
+ in.read(&footer[0], sizeof FOOTER - 1);
if (footer.compare(0, sizeof FOOTER - 1, FOOTER) != 0) {
MOZ_CRASH("Bad footer");
}
+#endif // DEBUG_HEADER
+
+ // std::cerr << "handleFooter done " << in.tellg() << "\n";
+ }
+
+ uint32_t readVariableLength() {
+ uint32_t val = 0;
+ uint32_t shift = 0;
+ while (true) {
+ // std::cerr << "readVariableLength at " << in.tellg() << "\n";
+ MOZ_ASSERT(shift < 32);
+ int get = in.get();
+ // FIXME: BIG HACK because istringstream doesn't like embedded \0.
+ if (get < 0) {
+ get = 0;
+ in.clear();
+ }
+ const uint8_t byte = (uint8_t)get;
+ val |= (uint32_t(byte) >> 1) << shift;
+ shift += 7;
+ if (!(byte & 1))
+ return val;
+ }
}
MOZ_MUST_USE ParseNode* parseNode(ParseNodeKind kind)
{
-// std::cerr << "treeParse " << NAMES[kind] << "\n";
debug << NAMES[kind] << " ";
+ // std::cerr << "parseNode " << NAMES[kind] << "\n";
switch (kind) {
// Empty subtree.
case PNK_LIMIT: {
std::string leaf;
- readNodeAsLeaf(leaf);
- MOZ_ASSERT(leaf.length() == 0);
return nullptr;
}
case PNK_LEXICALSCOPE: {
const size_t length = readNodeAsConcat();
MOZ_ASSERT(length == 1);
UniquePtr<ParseNode> body(parseNode());
@@ -1004,17 +1044,17 @@ private:
MOZ_MUST_USE bool binSerialize(JSContext* cx, const ParseNode* node, std::ostringstream& out, std::ostringstream& debug) {
const UniquePtr<StringTree> tree(treeSerialize(cx, node, debug));
if (!tree) {
return false;
}
tree->write(out);
- std::cerr << "binSerialize produced " << out.tellp() << " bytes\n";
+ // std::cerr << "binSerialize produced " << out.tellp() << " bytes\n";
return true;
}
MOZ_MUST_USE ParseNode* binParse(JSContext* cx, ParseNodeAllocator& alloc, std::istringstream& in, std::ostringstream& debug) {
TreeParser parser(cx, alloc, in, debug);
return parser.parseNode();
}
} // namespace frontend