diff options
Diffstat (limited to 'packages/utils/src/abi_encoder/calldata')
7 files changed, 646 insertions, 0 deletions
diff --git a/packages/utils/src/abi_encoder/calldata/blocks/blob.ts b/packages/utils/src/abi_encoder/calldata/blocks/blob.ts new file mode 100644 index 000000000..219ea6c61 --- /dev/null +++ b/packages/utils/src/abi_encoder/calldata/blocks/blob.ts @@ -0,0 +1,20 @@ +import { CalldataBlock } from '../calldata_block'; + +export class BlobCalldataBlock extends CalldataBlock { + private readonly _blob: Buffer; + + constructor(name: string, signature: string, parentName: string, blob: Buffer) { + const headerSizeInBytes = 0; + const bodySizeInBytes = blob.byteLength; + super(name, signature, parentName, headerSizeInBytes, bodySizeInBytes); + this._blob = blob; + } + + public toBuffer(): Buffer { + return this._blob; + } + + public getRawData(): Buffer { + return this._blob; + } +} diff --git a/packages/utils/src/abi_encoder/calldata/blocks/pointer.ts b/packages/utils/src/abi_encoder/calldata/blocks/pointer.ts new file mode 100644 index 000000000..72d6a3173 --- /dev/null +++ b/packages/utils/src/abi_encoder/calldata/blocks/pointer.ts @@ -0,0 +1,61 @@ +import * as ethUtil from 'ethereumjs-util'; +import * as _ from 'lodash'; + +import { constants } from '../../utils/constants'; + +import { CalldataBlock } from '../calldata_block'; + +export class PointerCalldataBlock extends CalldataBlock { + public static readonly RAW_DATA_START = new Buffer('<'); + public static readonly RAW_DATA_END = new Buffer('>'); + private static readonly _DEPENDENT_PAYLOAD_SIZE_IN_BYTES = 32; + private static readonly _EMPTY_HEADER_SIZE = 0; + private readonly _parent: CalldataBlock; + private readonly _dependency: CalldataBlock; + private _aliasFor: CalldataBlock | undefined; + + constructor(name: string, signature: string, parentName: string, dependency: CalldataBlock, parent: CalldataBlock) { + const headerSizeInBytes = PointerCalldataBlock._EMPTY_HEADER_SIZE; + const bodySizeInBytes = PointerCalldataBlock._DEPENDENT_PAYLOAD_SIZE_IN_BYTES; + super(name, signature, parentName, headerSizeInBytes, bodySizeInBytes); + this._parent = parent; + this._dependency = dependency; + this._aliasFor = undefined; + } + + public toBuffer(): Buffer { + const destinationOffset = !_.isUndefined(this._aliasFor) + ? this._aliasFor.getOffsetInBytes() + : this._dependency.getOffsetInBytes(); + const parentOffset = this._parent.getOffsetInBytes(); + const parentHeaderSize = this._parent.getHeaderSizeInBytes(); + const pointer: number = destinationOffset - (parentOffset + parentHeaderSize); + const pointerHex = `0x${pointer.toString(constants.HEX_BASE)}`; + const pointerBuf = ethUtil.toBuffer(pointerHex); + const pointerBufPadded = ethUtil.setLengthLeft(pointerBuf, constants.EVM_WORD_WIDTH_IN_BYTES); + return pointerBufPadded; + } + + public getDependency(): CalldataBlock { + return this._dependency; + } + + public setAlias(block: CalldataBlock): void { + this._aliasFor = block; + this._setName(`${this.getName()} (alias for ${block.getName()})`); + } + + public getAlias(): CalldataBlock | undefined { + return this._aliasFor; + } + + public getRawData(): Buffer { + const dependencyRawData = this._dependency.getRawData(); + const rawDataComponents: Buffer[] = []; + rawDataComponents.push(PointerCalldataBlock.RAW_DATA_START); + rawDataComponents.push(dependencyRawData); + rawDataComponents.push(PointerCalldataBlock.RAW_DATA_END); + const rawData = Buffer.concat(rawDataComponents); + return rawData; + } +} diff --git a/packages/utils/src/abi_encoder/calldata/blocks/set.ts b/packages/utils/src/abi_encoder/calldata/blocks/set.ts new file mode 100644 index 000000000..d1abc4986 --- /dev/null +++ b/packages/utils/src/abi_encoder/calldata/blocks/set.ts @@ -0,0 +1,47 @@ +import * as _ from 'lodash'; + +import { CalldataBlock } from '../calldata_block'; + +export class SetCalldataBlock extends CalldataBlock { + private _header: Buffer | undefined; + private _members: CalldataBlock[]; + + constructor(name: string, signature: string, parentName: string) { + super(name, signature, parentName, 0, 0); + this._members = []; + this._header = undefined; + } + + public getRawData(): Buffer { + const rawDataComponents: Buffer[] = []; + if (!_.isUndefined(this._header)) { + rawDataComponents.push(this._header); + } + _.each(this._members, (member: CalldataBlock) => { + const memberBuffer = member.getRawData(); + rawDataComponents.push(memberBuffer); + }); + const rawData = Buffer.concat(rawDataComponents); + return rawData; + } + + public setMembers(members: CalldataBlock[]): void { + this._members = members; + } + + public setHeader(header: Buffer): void { + this._setHeaderSize(header.byteLength); + this._header = header; + } + + public toBuffer(): Buffer { + if (!_.isUndefined(this._header)) { + return this._header; + } + return new Buffer(''); + } + + public getMembers(): CalldataBlock[] { + return this._members; + } +} diff --git a/packages/utils/src/abi_encoder/calldata/calldata.ts b/packages/utils/src/abi_encoder/calldata/calldata.ts new file mode 100644 index 000000000..b08fb71ce --- /dev/null +++ b/packages/utils/src/abi_encoder/calldata/calldata.ts @@ -0,0 +1,245 @@ +import * as ethUtil from 'ethereumjs-util'; +import * as _ from 'lodash'; + +import { constants } from '../utils/constants'; +import { EncodingRules } from '../utils/rules'; + +import { PointerCalldataBlock } from './blocks/pointer'; +import { SetCalldataBlock } from './blocks/set'; +import { CalldataBlock } from './calldata_block'; +import { CalldataIterator, ReverseCalldataIterator } from './iterator'; + +export class Calldata { + private readonly _rules: EncodingRules; + private _selector: string; + private _root: CalldataBlock | undefined; + + public constructor(rules: EncodingRules) { + this._rules = rules; + this._selector = ''; + this._root = undefined; + } + /** + * 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 (!_.startsWith(selector, '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 (_.isUndefined(this._root)) { + throw new Error('expected root'); + } + // Optimize, if flag set + if (this._rules.shouldOptimize) { + 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.shouldAnnotate + ? this._toHumanReadableCallData() + : this._toEvmCompatibeCallDataHex(); + 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 (_.isUndefined(this._root)) { + throw new Error('expected root'); + } + 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 PointerCalldataBlock) { + const dependencyBlockHashBuf = block.getDependency().computeHash(); + const dependencyBlockHash = ethUtil.bufferToHex(dependencyBlockHashBuf); + if (dependencyBlockHash in blocksByHash) { + const blockWithSameHash = blocksByHash[dependencyBlockHash]; + if (blockWithSameHash !== block.getDependency()) { + block.setAlias(blockWithSameHash); + } + } + continue; + } + // This block has not been seen. Record its hash. + const blockHashBuf = block.computeHash(); + const blockHash = ethUtil.bufferToHex(blockHashBuf); + if (!(blockHash in blocksByHash)) { + blocksByHash[blockHash] = block; + } + } + } + private _toEvmCompatibeCallDataHex(): string { + // Sanity check: must have a root block. + if (_.isUndefined(this._root)) { + throw new Error('expected root'); + } + // 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); + for (const block of iterator) { + valueBufs.push(block.toBuffer()); + } + // Create hex from buffer array. + const combinedBuffers = Buffer.concat(valueBufs); + const hexValue = ethUtil.bufferToHex(combinedBuffers); + return hexValue; + } + /** + * Returns human-readable calldata. + * + * Example: + * simpleFunction(string[], string[]) + * strings = ["Hello", "World"] + * simpleFunction(strings, strings) + * + * Output: + * 0xbb4f12e3 + * ### simpleFunction + * 0x0 0000000000000000000000000000000000000000000000000000000000000040 ptr<array1> (alias for array2) + * 0x20 0000000000000000000000000000000000000000000000000000000000000040 ptr<array2> + * + * 0x40 0000000000000000000000000000000000000000000000000000000000000002 ### array2 + * 0x60 0000000000000000000000000000000000000000000000000000000000000040 ptr<array2[0]> + * 0x80 0000000000000000000000000000000000000000000000000000000000000080 ptr<array2[1]> + * 0xa0 0000000000000000000000000000000000000000000000000000000000000005 array2[0] + * 0xc0 48656c6c6f000000000000000000000000000000000000000000000000000000 + * 0xe0 0000000000000000000000000000000000000000000000000000000000000005 array2[1] + * 0x100 576f726c64000000000000000000000000000000000000000000000000000000 + */ + private _toHumanReadableCallData(): string { + // Sanity check: must have a root block. + if (_.isUndefined(this._root)) { + throw new Error('expected root'); + } + // Constants for constructing annotated string + const offsetPadding = 10; + const valuePadding = 74; + const namePadding = 80; + const evmWordStartIndex = 0; + const emptySize = 0; + // 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}.`, ''); + // Resulting line will be <offsetStr><valueStr><nameStr> + let offsetStr = ''; + let valueStr = ''; + let nameStr = ''; + 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); + valueStr = ' '.repeat(valuePadding); + nameStr = `### ${prettyName.padEnd(namePadding)}`; + lineStr = `\n${offsetStr}${valueStr}${nameStr}`; + } else { + // This block has at least one word of value. + offsetStr = `0x${offset.toString(constants.HEX_BASE)}`.padEnd(offsetPadding); + valueStr = ethUtil + .stripHexPrefix( + ethUtil.bufferToHex( + block.toBuffer().slice(evmWordStartIndex, constants.EVM_WORD_WIDTH_IN_BYTES), + ), + ) + .padEnd(valuePadding); + if (block instanceof SetCalldataBlock) { + nameStr = `### ${prettyName.padEnd(namePadding)}`; + lineStr = `\n${offsetStr}${valueStr}${nameStr}`; + } else { + nameStr = ` ${prettyName.padEnd(namePadding)}`; + 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); + valueStr = ethUtil + .stripHexPrefix( + ethUtil.bufferToHex(block.toBuffer().slice(j, j + constants.EVM_WORD_WIDTH_IN_BYTES)), + ) + .padEnd(valuePadding); + nameStr = ' '.repeat(namePadding); + lineStr = `${lineStr}\n${offsetStr}${valueStr}${nameStr}`; + } + // Append to hex value + hexValue = `${hexValue}\n${lineStr}`; + offset += size; + } + return hexValue; + } +} diff --git a/packages/utils/src/abi_encoder/calldata/calldata_block.ts b/packages/utils/src/abi_encoder/calldata/calldata_block.ts new file mode 100644 index 000000000..35bd994e5 --- /dev/null +++ b/packages/utils/src/abi_encoder/calldata/calldata_block.ts @@ -0,0 +1,77 @@ +import * as ethUtil from 'ethereumjs-util'; + +export abstract class CalldataBlock { + private readonly _signature: string; + private readonly _parentName: string; + private _name: string; + private _offsetInBytes: number; + private _headerSizeInBytes: number; + private _bodySizeInBytes: number; + + constructor( + name: string, + signature: string, + parentName: string, + headerSizeInBytes: number, + bodySizeInBytes: number, + ) { + this._name = name; + this._signature = signature; + this._parentName = parentName; + this._offsetInBytes = 0; + this._headerSizeInBytes = headerSizeInBytes; + this._bodySizeInBytes = bodySizeInBytes; + } + + protected _setHeaderSize(headerSizeInBytes: number): void { + this._headerSizeInBytes = headerSizeInBytes; + } + + protected _setBodySize(bodySizeInBytes: number): void { + this._bodySizeInBytes = bodySizeInBytes; + } + + protected _setName(name: string): void { + this._name = name; + } + + public getName(): string { + return this._name; + } + + public getParentName(): string { + return this._parentName; + } + + public getSignature(): string { + return this._signature; + } + public getHeaderSizeInBytes(): number { + return this._headerSizeInBytes; + } + + public getBodySizeInBytes(): number { + return this._bodySizeInBytes; + } + + public getSizeInBytes(): number { + return this.getHeaderSizeInBytes() + this.getBodySizeInBytes(); + } + + public getOffsetInBytes(): number { + return this._offsetInBytes; + } + + public setOffset(offsetInBytes: number): void { + this._offsetInBytes = offsetInBytes; + } + + public computeHash(): Buffer { + const rawData = this.getRawData(); + const hash = ethUtil.sha3(rawData); + return hash; + } + + public abstract toBuffer(): Buffer; + public abstract getRawData(): Buffer; +} diff --git a/packages/utils/src/abi_encoder/calldata/iterator.ts b/packages/utils/src/abi_encoder/calldata/iterator.ts new file mode 100644 index 000000000..333b32b4f --- /dev/null +++ b/packages/utils/src/abi_encoder/calldata/iterator.ts @@ -0,0 +1,114 @@ +/* tslint:disable max-classes-per-file */ +import * as _ from 'lodash'; + +import { Queue } from '../utils/queue'; + +import { BlobCalldataBlock } from './blocks/blob'; +import { PointerCalldataBlock } from './blocks/pointer'; +import { SetCalldataBlock } from './blocks/set'; +import { CalldataBlock } from './calldata_block'; + +/** + * Iterator class for Calldata Blocks. Blocks follows the order + * they should be put into calldata that is passed to he EVM. + * + * Example #1: + * Let root = Set { + * Blob{} A, + * Pointer { + * Blob{} a + * } B, + * Blob{} C + * } + * It will iterate as follows: [A, B, C, B.a] + * + * Example #2: + * Let root = Set { + * Blob{} A, + * Pointer { + * Blob{} a + * Pointer { + * Blob{} b + * } + * } B, + * Pointer { + * Blob{} c + * } C + * } + * It will iterate as follows: [A, B, C, B.a, B.b, C.c] + */ +abstract class BaseIterator implements Iterable<CalldataBlock> { + protected readonly _root: CalldataBlock; + protected readonly _queue: Queue<CalldataBlock>; + + private static _createQueue(block: CalldataBlock): Queue<CalldataBlock> { + const queue = new Queue<CalldataBlock>(); + // Base case + if (!(block instanceof SetCalldataBlock)) { + queue.pushBack(block); + return queue; + } + // This is a set; add members + const set = block; + _.eachRight(set.getMembers(), (member: CalldataBlock) => { + queue.mergeFront(BaseIterator._createQueue(member)); + }); + // Add children + _.each(set.getMembers(), (member: CalldataBlock) => { + // Traverse child if it is a unique pointer. + // A pointer that is an alias for another pointer is ignored. + if (member instanceof PointerCalldataBlock && _.isUndefined(member.getAlias())) { + const dependency = member.getDependency(); + queue.mergeBack(BaseIterator._createQueue(dependency)); + } + }); + // Put set block at the front of the queue + queue.pushFront(set); + return queue; + } + + public constructor(root: CalldataBlock) { + this._root = root; + this._queue = BaseIterator._createQueue(root); + } + + public [Symbol.iterator](): { next: () => IteratorResult<CalldataBlock> } { + return { + next: () => { + const nextBlock = this.nextBlock(); + if (!_.isUndefined(nextBlock)) { + return { + value: nextBlock, + done: false, + }; + } + return { + done: true, + value: new BlobCalldataBlock('', '', '', new Buffer('')), + }; + }, + }; + } + + public abstract nextBlock(): CalldataBlock | undefined; +} + +export class CalldataIterator extends BaseIterator { + public constructor(root: CalldataBlock) { + super(root); + } + + public nextBlock(): CalldataBlock | undefined { + return this._queue.popFront(); + } +} + +export class ReverseCalldataIterator extends BaseIterator { + public constructor(root: CalldataBlock) { + super(root); + } + + public nextBlock(): CalldataBlock | undefined { + return this._queue.popBack(); + } +} diff --git a/packages/utils/src/abi_encoder/calldata/raw_calldata.ts b/packages/utils/src/abi_encoder/calldata/raw_calldata.ts new file mode 100644 index 000000000..189841989 --- /dev/null +++ b/packages/utils/src/abi_encoder/calldata/raw_calldata.ts @@ -0,0 +1,82 @@ +import * as ethUtil from 'ethereumjs-util'; +import * as _ from 'lodash'; + +import { constants } from '../utils/constants'; +import { Queue } from '../utils/queue'; + +export class RawCalldata { + private static readonly _INITIAL_OFFSET = 0; + private readonly _value: Buffer; + private readonly _selector: string; + private readonly _scopes: Queue<number>; + private _offset: number; + + public constructor(value: string | Buffer, hasSelector: boolean = true) { + // Sanity check + if (typeof value === 'string' && !_.startsWith(value, '0x')) { + throw new Error(`Expected raw calldata to start with '0x'`); + } + // Construct initial values + this._value = ethUtil.toBuffer(value); + this._selector = '0x'; + this._scopes = new Queue<number>(); + this._scopes.pushBack(RawCalldata._INITIAL_OFFSET); + this._offset = RawCalldata._INITIAL_OFFSET; + // If there's a selector then slice it + if (hasSelector) { + const selectorBuf = this._value.slice(constants.HEX_SELECTOR_LENGTH_IN_BYTES); + this._value = this._value.slice(constants.HEX_SELECTOR_LENGTH_IN_BYTES); + this._selector = ethUtil.bufferToHex(selectorBuf); + } + } + + public popBytes(lengthInBytes: number): Buffer { + const value = this._value.slice(this._offset, this._offset + lengthInBytes); + this.setOffset(this._offset + lengthInBytes); + return value; + } + + public popWord(): Buffer { + const wordInBytes = 32; + return this.popBytes(wordInBytes); + } + + public popWords(length: number): Buffer { + const wordInBytes = 32; + return this.popBytes(length * wordInBytes); + } + + public readBytes(from: number, to: number): Buffer { + const value = this._value.slice(from, to); + return value; + } + + public setOffset(offsetInBytes: number): void { + this._offset = offsetInBytes; + } + + public startScope(): void { + this._scopes.pushFront(this._offset); + } + + public endScope(): void { + this._scopes.popFront(); + } + + public getOffset(): number { + return this._offset; + } + + public toAbsoluteOffset(relativeOffset: number): number { + const scopeOffset = this._scopes.peekFront(); + if (_.isUndefined(scopeOffset)) { + throw new Error(`Tried to access undefined scope.`); + } + const absoluteOffset = relativeOffset + scopeOffset; + return absoluteOffset; + } + + public getSelector(): string { + return this._selector; + } +} |