From 50344fa24a4a708ae90030af107afb15366f883f Mon Sep 17 00:00:00 2001 From: Greg Hysen Date: Sun, 25 Nov 2018 21:19:11 -0800 Subject: Added inline documentation for Calldata class --- .../abi_encoder/abstract_data_types/data_type.ts | 4 +- .../utils/src/abi_encoder/calldata/calldata.ts | 227 +++++++++++++-------- 2 files changed, 147 insertions(+), 84 deletions(-) (limited to 'packages/utils/src') diff --git a/packages/utils/src/abi_encoder/abstract_data_types/data_type.ts b/packages/utils/src/abi_encoder/abstract_data_types/data_type.ts index 450080353..ab7df6ecc 100644 --- a/packages/utils/src/abi_encoder/abstract_data_types/data_type.ts +++ b/packages/utils/src/abi_encoder/abstract_data_types/data_type.ts @@ -32,8 +32,8 @@ export abstract class DataType { } const block = this.generateCalldataBlock(value); calldata.setRoot(block); - const calldataHex = calldata.toHexString(); - return calldataHex; + const encodedCalldata = calldata.toString(); + return encodedCalldata; } public decode(calldata: string, rules?: DecodingRules, selector?: string): any { diff --git a/packages/utils/src/abi_encoder/calldata/calldata.ts b/packages/utils/src/abi_encoder/calldata/calldata.ts index 50f0f0fad..da61b2256 100644 --- a/packages/utils/src/abi_encoder/calldata/calldata.ts +++ b/packages/utils/src/abi_encoder/calldata/calldata.ts @@ -11,27 +11,107 @@ import { CalldataIterator, ReverseCalldataIterator } from './iterator'; export class Calldata { private readonly _rules: EncodingRules; private _selector: string; - private _sizeInBytes: number; private _root: CalldataBlock | undefined; public constructor(rules: EncodingRules) { this._rules = rules; this._selector = ''; - this._sizeInBytes = 0; this._root = undefined; } - - public optimize(): void { + /** + * Sets the root calldata block. This block usually corresponds to a Method. + */ + public setRoot(block: CalldataBlock): void { + this._root = block; + } + /** + * Sets the selector to be prepended onto the calldata. + * If the root block was created by a Method then a selector will likely be set. + */ + public setSelector(selector: string): void { + if (!selector.startsWith('0x')) { + throw new Error(`Expected selector to be hex. Missing prefix '0x'`); + } else if (selector.length !== Constants.HEX_SELECTOR_LENGTH_IN_CHARS) { + throw new Error(`Invalid selector '${selector}'`); + } + this._selector = selector; + } + /** + * Iterates through the calldata blocks, starting from the root block, to construct calldata as a hex string. + * If the `optimize` flag is set then this calldata will be condensed, to save gas. + * If the `annotate` flag is set then this will return human-readable calldata. + * If the `annotate` flag is *not* set then this will return EVM-compatible calldata. + */ + public toString(): string { + // Sanity check: root block must be set + if (this._root === undefined) { + throw new Error('expected root'); + } + // Optimize, if flag set + if (this._rules.optimize) { + this._optimize(); + } + // Set offsets + const iterator = new CalldataIterator(this._root); + let offset = 0; + for (const block of iterator) { + block.setOffset(offset); + offset += block.getSizeInBytes(); + } + // Generate hex string + const hexString = this._rules.annotate ? this._toAnnotatedString() : this._toCondensedString(); + return hexString; + } + /** + * There are three types of calldata blocks: Blob, Set and Pointer. + * Scenarios arise where distinct pointers resolve to identical values. + * We optimize by keeping only one such instance of the identical value, and redirecting all pointers here. + * We keep the last such duplicate value because pointers can only be positive (they cannot point backwards). + * + * Example #1: + * function f(string[], string[]) + * f(["foo", "bar", "blitz"], ["foo", "bar", "blitz"]) + * The array ["foo", "bar", "blitz"] will only be included in the calldata once. + * + * Example #2: + * function f(string[], string) + * f(["foo", "bar", "blitz"], "foo") + * The string "foo" will only be included in the calldata once. + * + * Example #3: + * function f((string, uint, bytes), string, uint, bytes) + * f(("foo", 5, "0x05"), "foo", 5, "0x05") + * The string "foo" and bytes "0x05" will only be included in the calldata once. + * The duplicate `uint 5` values cannot be optimized out because they are static values (no pointer points to them). + * + * @TODO #1: + * This optimization strategy handles blocks that are exact duplicates of one another. + * But what if some block is a combination of two other blocks? Or a subset of another block? + * This optimization problem is not much different from the current implemetation. + * Instead of tracking "observed" hashes, at each node we would simply do pattern-matching on the calldata. + * This strategy would be applied after assigning offsets to the tree, rather than before (as in this strategy). + * Note that one consequence of this strategy is pointers may resolve to offsets that are not word-aligned. + * This shouldn't be a problem but further investigation should be done. + * + * @TODO #2: + * To be done as a follow-up to @TODO #1. + * Since we optimize from the bottom-up, we could be affecting the outcome of a later potential optimization. + * For example, what if by removing one duplicate value we miss out on optimizing another block higher in the tree. + * To handle this case, at each node we can store a candidate optimization in a priority queue (sorted by calldata size). + * At the end of traversing the tree, the candidate at the front of the queue will be the most optimal output. + * + */ + private _optimize(): void { + // Step 1/1 Create a reverse iterator (starts from the end of the calldata to the beginning) if (this._root === undefined) { throw new Error('expected root'); } - - const blocksByHash: { [key: string]: CalldataBlock } = {}; - - // 1. Create a queue of subtrees by hash - // Note that they are ordered the same as const iterator = new ReverseCalldataIterator(this._root); + // Step 2/2 Iterate over each block, keeping track of which blocks have been seen and pruning redundant blocks. + const blocksByHash: { [key: string]: CalldataBlock } = {}; for (const block of iterator) { + // If a block is a pointer and its value has already been observed, then update + // the pointer to resolve to the existing value. if (block instanceof CalldataBlocks.Pointer) { const dependencyBlockHashBuf = block.getDependency().computeHash(); const dependencyBlockHash = ethUtil.bufferToHex(dependencyBlockHashBuf); @@ -43,7 +123,7 @@ export class Calldata { } continue; } - + // This block has not been seen. Record its hash. const blockHashBuf = block.computeHash(); const blockHash = ethUtil.bufferToHex(blockHashBuf); if (!(blockHash in blocksByHash)) { @@ -51,84 +131,85 @@ export class Calldata { } } } - - public toHexString(): string { + /** + * Returns EVM-compatible calldata as a Hex string. + */ + private _toCondensedString(): string { + // Sanity check: must have a root block. if (this._root === undefined) { throw new Error('expected root'); } - - if (this._rules.optimize) { - this.optimize(); - } - + // Construct an array of buffers (one buffer for each block). + const selectorBuffer = ethUtil.toBuffer(this._selector); + const valueBufs: Buffer[] = [selectorBuffer]; const iterator = new CalldataIterator(this._root); - let offset = 0; for (const block of iterator) { - block.setOffset(offset); - offset += block.getSizeInBytes(); + valueBufs.push(block.toBuffer()); } - - const hexValue = this._rules.annotate ? this._generateAnnotatedHexString() : this._generateCondensedHexString(); + // Create hex from buffer array. + const combinedBuffers = Buffer.concat(valueBufs); + const hexValue = ethUtil.bufferToHex(combinedBuffers); return hexValue; } - - public getSelectorHex(): string { - return this._selector; - } - - public getSizeInBytes(): number { - return this._sizeInBytes; - } - - public setRoot(block: CalldataBlock): void { - this._root = block; - this._sizeInBytes += block.getSizeInBytes(); - } - - public setSelector(selector: string): void { - this._selector = selector.startsWith('0x') ? selector : `$0x${selector}`; - if (this._selector.length !== Constants.HEX_SELECTOR_LENGTH_IN_CHARS) { - throw new Error(`Invalid selector '${this._selector}'`); - } - this._sizeInBytes += Constants.HEX_SELECTOR_LENGTH_IN_BYTES; // @TODO: Used to be += 8. Bad? - } - - private _generateAnnotatedHexString(): string { - let hexValue = `${this._selector}`; + /** + * Returns human-redable calldata. + * + * Example: + * simpleFunction(string[], string[]) + * strings = ["Hello", "World"] + * simpleFunction(strings, strings) + * + * Output: + * 0xbb4f12e3 + * ### simpleFunction + * 0x0 0000000000000000000000000000000000000000000000000000000000000040 ptr (alias for array2) + * 0x20 0000000000000000000000000000000000000000000000000000000000000040 ptr + * + * 0x40 0000000000000000000000000000000000000000000000000000000000000002 ### array2 + * 0x60 0000000000000000000000000000000000000000000000000000000000000040 ptr + * 0x80 0000000000000000000000000000000000000000000000000000000000000080 ptr + * 0xa0 0000000000000000000000000000000000000000000000000000000000000005 array2[0] + * 0xc0 48656c6c6f000000000000000000000000000000000000000000000000000000 + * 0xe0 0000000000000000000000000000000000000000000000000000000000000005 array2[1] + * 0x100 576f726c64000000000000000000000000000000000000000000000000000000 + */ + private _toAnnotatedString(): string { + // Sanity check: must have a root block. if (this._root === undefined) { throw new Error('expected root'); } - - const iterator = new CalldataIterator(this._root); + // Construct annotated calldata + let hexValue = `${this._selector}`; let offset = 0; const functionName: string = this._root.getName(); + const iterator = new CalldataIterator(this._root); for (const block of iterator) { // Process each block 1 word at a time const size = block.getSizeInBytes(); const name = block.getName(); const parentName = block.getParentName(); const prettyName = name.replace(`${parentName}.`, '').replace(`${functionName}.`, ''); - - // Current offset - let offsetStr = ''; - - // If this block is empty then it's a newline const offsetPadding = 10; const valuePadding = 74; const namePadding = 80; const evmWordStartIndex = 0; const emptySize = 0; - let value = ''; + // Resulting line will be + let offsetStr = ''; + let valueStr = ''; let nameStr = ''; - let line = ''; + let lineStr = ''; if (size === emptySize) { + // This is a Set block with no header. + // For example, a tuple or an array with a defined length. offsetStr = ' '.repeat(offsetPadding); - value = ' '.repeat(valuePadding); + valueStr = ' '.repeat(valuePadding); nameStr = `### ${prettyName.padEnd(namePadding)}`; - line = `\n${offsetStr}${value}${nameStr}`; + lineStr = `\n${offsetStr}${valueStr}${nameStr}`; } else { + // This block has at least one word of value. offsetStr = `0x${offset.toString(Constants.HEX_BASE)}`.padEnd(offsetPadding); - value = ethUtil + valueStr = ethUtil .stripHexPrefix( ethUtil.bufferToHex( block.toBuffer().slice(evmWordStartIndex, Constants.EVM_WORD_WIDTH_IN_BYTES), @@ -137,46 +218,28 @@ export class Calldata { .padEnd(valuePadding); if (block instanceof CalldataBlocks.Set) { nameStr = `### ${prettyName.padEnd(namePadding)}`; - line = `\n${offsetStr}${value}${nameStr}`; + lineStr = `\n${offsetStr}${valueStr}${nameStr}`; } else { nameStr = ` ${prettyName.padEnd(namePadding)}`; - line = `${offsetStr}${value}${nameStr}`; + lineStr = `${offsetStr}${valueStr}${nameStr}`; } } - + // This block has a value that is more than 1 word. for (let j = Constants.EVM_WORD_WIDTH_IN_BYTES; j < size; j += Constants.EVM_WORD_WIDTH_IN_BYTES) { offsetStr = `0x${(offset + j).toString(Constants.HEX_BASE)}`.padEnd(offsetPadding); - value = ethUtil + valueStr = ethUtil .stripHexPrefix( ethUtil.bufferToHex(block.toBuffer().slice(j, j + Constants.EVM_WORD_WIDTH_IN_BYTES)), ) .padEnd(valuePadding); nameStr = ' '.repeat(namePadding); - line = `${line}\n${offsetStr}${value}${nameStr}`; + lineStr = `${lineStr}\n${offsetStr}${valueStr}${nameStr}`; } - // Append to hex value - hexValue = `${hexValue}\n${line}`; + hexValue = `${hexValue}\n${lineStr}`; offset += size; } return hexValue; } - - private _generateCondensedHexString(): string { - const selectorBuffer = ethUtil.toBuffer(this._selector); - if (this._root === undefined) { - throw new Error('expected root'); - } - - const iterator = new CalldataIterator(this._root); - const valueBufs: Buffer[] = [selectorBuffer]; - for (const block of iterator) { - valueBufs.push(block.toBuffer()); - } - - const combinedBuffers = Buffer.concat(valueBufs); - const hexValue = ethUtil.bufferToHex(combinedBuffers); - return hexValue; - } } -- cgit