compiler

package
v1.2.23 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 22, 2026 License: Apache-2.0 Imports: 30 Imported by: 0

Documentation

Overview

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Copyright Consensys Software Inc.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0

Index

Constants

This section is empty.

Variables

View Source 
var DEFAULT_ALLOCATOR func(RegisterAllocation) = LegacyAllocator

DEFAULT_ALLOCATOR determines the register allocation algorithm to use by default.

View Source 
var INTRINSICS []IntrinsicDefinition = []IntrinsicDefinition{

	{"+", 1, intrinsicAdd},
	{"+", 2, intrinsicAdd},
	{"+", 3, intrinsicAdd},
	{"+", 4, intrinsicAdd},

	{"-", 1, intrinsicSub},
	{"-", 2, intrinsicSub},
	{"-", 3, intrinsicSub},
	{"-", 4, intrinsicSub},

	{"*", 1, intrinsicMul},
	{"*", 2, intrinsicMul},
	{"*", 3, intrinsicMul},
	{"*", 4, intrinsicMul},
}

INTRINSICS identifies all of the built-in functions used within the corset language, such as "+", "*", etc. This is needed for two reasons: firstly, so we can alias them; secondly, so they can be used in reductions.

View Source 
var NATIVE_SIGNATURES []NativeDefinition = []NativeDefinition{

	{"id", 1, nativeId},

	{"filter", 2, nativeFilter},

	{"map-if", 3, nativeMapIf},
	{"map-if", 4, nativeMapIf},
	{"map-if", 5, nativeMapIf},
	{"map-if", 6, nativeMapIf},
	{"map-if", 7, nativeMapIf},
	{"map-if", 8, nativeMapIf},
	{"map-if", 9, nativeMapIf},
	{"map-if", 10, nativeMapIf},
	{"map-if", 11, nativeMapIf},
	{"map-if", 12, nativeMapIf},
	{"map-if", 13, nativeMapIf},
	{"map-if", 14, nativeMapIf},
	{"map-if", 15, nativeMapIf},
	{"map-if", 16, nativeMapIf},

	{"fwd-changes-within", 2, nativeChangeWithin},
	{"fwd-changes-within", 3, nativeChangeWithin},
	{"fwd-changes-within", 4, nativeChangeWithin},
	{"fwd-changes-within", 5, nativeChangeWithin},
	{"fwd-changes-within", 6, nativeChangeWithin},
	{"fwd-changes-within", 7, nativeChangeWithin},
	{"fwd-changes-within", 8, nativeChangeWithin},
	{"fwd-changes-within", 9, nativeChangeWithin},
	{"fwd-changes-within", 10, nativeChangeWithin},
	{"fwd-changes-within", 11, nativeChangeWithin},
	{"fwd-changes-within", 12, nativeChangeWithin},
	{"fwd-changes-within", 13, nativeChangeWithin},
	{"fwd-changes-within", 14, nativeChangeWithin},
	{"fwd-changes-within", 15, nativeChangeWithin},
	{"fwd-changes-within", 16, nativeChangeWithin},

	{"fwd-unchanged-within", 2, nativeChangeWithin},
	{"fwd-unchanged-within", 3, nativeChangeWithin},
	{"fwd-unchanged-within", 4, nativeChangeWithin},
	{"fwd-unchanged-within", 5, nativeChangeWithin},
	{"fwd-unchanged-within", 6, nativeChangeWithin},
	{"fwd-unchanged-within", 7, nativeChangeWithin},
	{"fwd-unchanged-within", 8, nativeChangeWithin},
	{"fwd-unchanged-within", 9, nativeChangeWithin},
	{"fwd-unchanged-within", 10, nativeChangeWithin},
	{"fwd-unchanged-within", 11, nativeChangeWithin},
	{"fwd-unchanged-within", 12, nativeChangeWithin},
	{"fwd-unchanged-within", 13, nativeChangeWithin},
	{"fwd-unchanged-within", 14, nativeChangeWithin},
	{"fwd-unchanged-within", 15, nativeChangeWithin},
	{"fwd-unchanged-within", 16, nativeChangeWithin},

	{"bwd-changes-within", 2, nativeChangeWithin},
	{"bwd-changes-within", 3, nativeChangeWithin},
	{"bwd-changes-within", 4, nativeChangeWithin},
	{"bwd-changes-within", 5, nativeChangeWithin},
	{"bwd-changes-within", 6, nativeChangeWithin},
	{"bwd-changes-within", 7, nativeChangeWithin},
	{"bwd-changes-within", 8, nativeChangeWithin},
	{"bwd-changes-within", 9, nativeChangeWithin},
	{"bwd-changes-within", 10, nativeChangeWithin},
	{"bwd-changes-within", 11, nativeChangeWithin},
	{"bwd-changes-within", 12, nativeChangeWithin},
	{"bwd-changes-within", 13, nativeChangeWithin},
	{"bwd-changes-within", 14, nativeChangeWithin},
	{"bwd-changes-within", 15, nativeChangeWithin},
	{"bwd-changes-within", 16, nativeChangeWithin},

	{"fwd-fill-within", 3, nativeFillWithin},

	{"bwd-fill-within", 3, nativeFillWithin},
}

NATIVE_SIGNATURES identifies all built-in native computations which can be used in defcomputed assignments.

Functions

func ImprovedAllocator 

func ImprovedAllocator(allocation RegisterAllocation)

ImprovedAllocator provides an improved register allocation algorithm over the legacy allocator. However, it is not safe to use at this time.

func LegacyAllocator 

func LegacyAllocator(allocation RegisterAllocation)

LegacyAllocator is the original register allocation algorithm used in Corset. This is retained for backwards compatibility reasons, but should eventually be dropped.

func RegisterAccessOf 

func RegisterAccessOf(module register.Map, name string, shift int) *hir.RegisterAccess

RegisterAccessOf returns a register accessor for the register with the given name.

func ResolveCircuit 

func ResolveCircuit(srcmap *source.Maps[ast.Node], circuit *ast.Circuit) (*ModuleScope, []SyntaxError)

ResolveCircuit resolves all symbols declared and used within a circuit, producing an environment which can subsequently be used to look up the relevant module or column identifiers. This process can fail, of course, if a symbol (e.g. a column) is referred to which doesn't exist. Likewise, if two modules or columns with identical names are declared in the same scope, etc.

Types

type AllocationComparator 

type AllocationComparator = func(*RegisterGroup, *RegisterGroup) bool

AllocationComparator is a binary predicate over register groups used to determine when two groups can be merged.

type BindingId 

type BindingId struct {
	// contains filtered or unexported fields
}

BindingId is an identifier is used to distinguish different forms of binding, as some forms are known from their use. Specifically, at the current time, only functions are distinguished from other categories (e.g. columns, parameters, etc).

func (BindingId) IsFunction 

func (b BindingId) IsFunction() bool

IsFunction checks whether or not this binding identifier refers to a function definition or not.

func (BindingId) String 

func (b BindingId) String() string

type Config 

type Config struct {
	// Enable standard library
	Stdlib bool
	// Enable debug constraints
	Debug bool
	// Enable legacy register allocator
	Legacy bool
	// Enforce all types by default
	EnforceTypes bool
	// Enforce types for all limbs arising from splitting registers
	EnforceLimbTypes bool
	// Target field configuration.  This is only used to assist in reporting
	// errors which are specific to the given field configuration.
	Field field.Config
}

Config encapsulates various options which can affect compilation.

type DeclPredicate 

type DeclPredicate = array.Predicate[ast.Declaration]

DeclPredicate is a shorthand notation.

type Environment 

type Environment interface {
	// Register returns the name of the given module.
	Module(index uint) string
	// Module returns information about a given module, such as its module
	// identifier.
	ModuleOf(module string) uint
	// Register returns information about a given register, based on its index
	// (i.e. underlying HIR column identifier).
	Register(index uint) *Register
	// RegisterOf identifies the register (i.e. underlying (HIR) column) to
	// which a given source-level (i.e. corset) column is allocated.  This
	// expects an absolute path.
	RegisterOf(path *file.Path) uint
	// RegistersOf identifies the set of registers (i.e. underlying (HIR)
	// columns) associated with a given module.
	RegistersOf(module string) []uint
}

Environment provides an interface into the global scope which can be used for simply resolving column identifiers.

type GlobalEnvironment 

type GlobalEnvironment struct {
	// contains filtered or unexported fields
}

GlobalEnvironment is a wrapper around a global scope. The point, really, is to signal the change between a global scope whose columns have yet to be allocated, from an environment whose columns are allocated.

func NewGlobalEnvironment 

func NewGlobalEnvironment(root *ModuleScope, allocator func(RegisterAllocation)) GlobalEnvironment

NewGlobalEnvironment constructs a new global environment from a global scope by allocating appropriate identifiers to all columns. This process is parameterised upon a given register allocator, thus enabling different allocation algorithms.

func (GlobalEnvironment) ColumnsOf 

func (p GlobalEnvironment) ColumnsOf(register uint) []string

ColumnsOf returns the set of registers allocated to a given column.

func (GlobalEnvironment) Module 

func (p GlobalEnvironment) Module(mid uint) string

Module returns information about a given module, such as its module identifier.

func (GlobalEnvironment) ModuleOf 

func (p GlobalEnvironment) ModuleOf(module string) uint

ModuleOf returns the internal index of the given module.

func (GlobalEnvironment) Register 

func (p GlobalEnvironment) Register(index uint) *Register

Register returns information about a given register, based on its index (i.e. underlying HIR column identifier).

func (GlobalEnvironment) RegisterOf 

func (p GlobalEnvironment) RegisterOf(column *file.Path) uint

RegisterOf identifies the register (i.e. underlying (HIR) column) to which a given source-level (i.e. corset) column is allocated.

func (GlobalEnvironment) RegistersOf 

func (p GlobalEnvironment) RegistersOf(module string) []uint

RegistersOf identifies the set of registers (i.e. underlying (HIR) columns) associated with a given module.

type GlobalResolution 

type GlobalResolution struct {
	// contains filtered or unexported fields
}

GlobalResolution maintains detailed state about the ongoing attempt to resolve all declarations in a given circuit.

func NewGlobalResolution 

func NewGlobalResolution(circuit *ast.Circuit, srcmap source.Maps[ast.Node]) GlobalResolution

NewGlobalResolution simply initialises an appropriate state object for the given circuit.

func (*GlobalResolution) BeginIteration 

func (p *GlobalResolution) BeginIteration()

BeginIteration signals that a new iteration is beginning.

func (*GlobalResolution) Continue 

func (p *GlobalResolution) Continue() bool

Continue determines whether or not to continue onto another iteration.

func (*GlobalResolution) Enter 

func (p *GlobalResolution) Enter(index int) ModuleResolution

Enter returns the state for a given module.

func (*GlobalResolution) Errors 

func (p *GlobalResolution) Errors() []SyntaxError

Errors simply returns any error messages arising.

type IntrinsicDefinition 

type IntrinsicDefinition struct {
	// contains filtered or unexported fields
}

IntrinsicDefinition is a SymbolDefinition for an intrinsic (i.e. built-in) operation, such as "+", "-", etc. These are needed for two reasons: firstly, so we can alias them; secondly, so they can be used in reductions.

func (*IntrinsicDefinition) Arity 

func (p *IntrinsicDefinition) Arity() util.Option[uint]

Arity indicates whether or not this is a function and, if so, what arity (i.e. how many arguments) the function has.

func (*IntrinsicDefinition) Binding 

func (p *IntrinsicDefinition) Binding() ast.Binding

Binding returns the binding associated with this intrinsic.

func (*IntrinsicDefinition) IsFinalised 

func (p *IntrinsicDefinition) IsFinalised() bool

IsFinalised checks whether this binding has been finalised yet or not.

func (*IntrinsicDefinition) IsNative 

func (p *IntrinsicDefinition) IsNative() bool

IsNative checks whether this function binding is native (or not).

func (*IntrinsicDefinition) IsPure 

func (p *IntrinsicDefinition) IsPure() bool

IsPure checks whether this pure (which intrinsics always are).

func (*IntrinsicDefinition) IsRecursive 

func (p *IntrinsicDefinition) IsRecursive() bool

IsRecursive implementation for Binding interface.

func (*IntrinsicDefinition) Lisp 

func (p *IntrinsicDefinition) Lisp() sexp.SExp

Lisp returns a lisp representation of this intrinsic.

func (*IntrinsicDefinition) Name 

func (p *IntrinsicDefinition) Name() string

Name returns the name of the intrinsic being defined.

func (*IntrinsicDefinition) Path 

func (p *IntrinsicDefinition) Path() *file.Path

Path returns the qualified name (i.e. absolute path) of this symbol. For example, "m1.X" for a column X defined in module m1.

func (*IntrinsicDefinition) Signature 

func (p *IntrinsicDefinition) Signature() *ast.FunctionSignature

Signature returns the function signature for this binding.

type LocalScope 

type LocalScope struct {
	// contains filtered or unexported fields
}

LocalScope represents a simple implementation of scope in which local variables can be declared. A local scope must have a single context associated with it, and this will be inferred by resolving those expressions which must be evaluated within.

func NewLocalScope 

func NewLocalScope(enclosing Scope, global bool, pure bool, constant bool) LocalScope

NewLocalScope constructs a new local scope within a given enclosing scope. A local scope can have local variables declared within it. A local scope can also be "global" in the sense that accessing symbols from other modules is permitted.

func (LocalScope) Bind 

func (p LocalScope) Bind(symbol ast.Symbol) bool

Bind looks up a given variable or function being referenced either within the enclosing scope (module==nil) or within a specified module.

func (LocalScope) Bindings 

func (p LocalScope) Bindings(path file.Path) []BindingId

Bindings returns all binding identifiers within a given path.

func (*LocalScope) DeclareLocal 

func (p *LocalScope) DeclareLocal(name string, binding *ast.LocalVariableBinding) uint

DeclareLocal registers a new local variable (e.g. a parameter).

func (LocalScope) FixContext 

func (p LocalScope) FixContext(context ast.Context) bool

FixContext fixes the context for this scope. Since every scope requires exactly one context, this fails if we fix it to incompatible contexts.

func (LocalScope) IsConstant 

func (p LocalScope) IsConstant() bool

IsConstant determines whether or not this scope is defining a constant. This places some restrictions on what variables can be accessed, etc.

func (LocalScope) IsGlobal 

func (p LocalScope) IsGlobal() bool

IsGlobal determines whether symbols can be accessed in modules other than the enclosing module.

func (LocalScope) IsPure 

func (p LocalScope) IsPure() bool

IsPure determines whether or not this scope is pure. That is, whether or not expressions in this scope are permitted to access columns (either directly, or indirectly via impure invocations).

func (LocalScope) IsVisible 

func (p LocalScope) IsVisible(symbol ast.Symbol) bool

IsVisible implemention for Scope interface.

func (LocalScope) IsWithin 

func (p LocalScope) IsWithin(path file.Path) bool

IsWithin checks whether a given path is local to the enclosing module, or not.

func (LocalScope) NestedConstScope 

func (p LocalScope) NestedConstScope() LocalScope

NestedConstScope creates a nested scope within this local scope which, in addition, is always pure and expects a constant value.

func (LocalScope) NestedScope 

func (p LocalScope) NestedScope() LocalScope

NestedScope creates a nested scope within this local scope.

type ModuleBuilder 

type ModuleBuilder = ir.ModuleBuilder[word.BigEndian, hir.Constraint, hir.Term]

ModuleBuilder is used within this translator for building the various modules which are contained within the mixed HIR schema.

type ModuleResolution 

type ModuleResolution struct {
	// contains filtered or unexported fields
}

ModuleResolution provides a handy interface for resolving declarations within a given module. It is really just a wrapper around the global resolution state.

func (*ModuleResolution) AlreadyFailed 

func (p *ModuleResolution) AlreadyFailed(decl int) bool

AlreadyFailed can be used to determine whether a given declaration within the module already failed in a previous iteration. This is useful to prevent reattempts to resolve the declaration (which would lead to duplicate errors, etc).

func (*ModuleResolution) Completed 

func (p *ModuleResolution) Completed(decl int)

Completed indicates a given declaration within the module has been resolved.

func (*ModuleResolution) Failed 

func (p *ModuleResolution) Failed(decl int, errs []SyntaxError)

Failed indicates a given declaration within the module has failed resolution and generated one or more errors.

type ModuleScope 

type ModuleScope struct {
	// contains filtered or unexported fields
}

ModuleScope defines recursive tree of scopes where symbols can be resolved and bound. The primary goal is to handle the various ways in which a symbol's qualified name (i.e. path) can be expressed. For example, a symbol can be given an absolute name (which is resolved from the root of the scope tree), or it can be relative (in which case it is resolved relative to a given module).

func NewModuleScope 

func NewModuleScope(public bool) *ModuleScope

NewModuleScope constructs an initially empty top-level scope.

func (*ModuleScope) Alias 

func (p *ModuleScope) Alias(alias string, symbol ast.Symbol) bool

Alias constructs an alias for an existing symbol. If the symbol does not exist, then this returns false.

func (*ModuleScope) Bind 

func (p *ModuleScope) Bind(symbol ast.Symbol) bool

Bind looks up a given variable being referenced within a given module. For a root context, this is either a column, an alias or a function declaration.

func (*ModuleScope) Binding 

func (p *ModuleScope) Binding(name string, arity util.Option[uint]) ast.Binding

Binding returns information about the binding of a particular symbol defined in this module.

func (*ModuleScope) Bindings 

func (p *ModuleScope) Bindings(path file.Path) []BindingId

Bindings returns all binding identifiers within a given path.

func (*ModuleScope) Children 

func (p *ModuleScope) Children() []*ModuleScope

Children returns the set of submodules defined within this module.

func (*ModuleScope) CloseDefinition 

func (p *ModuleScope) CloseDefinition(symbol ast.SymbolDefinition)

CloseDefinition indicates that the given symbol has now been defined.

func (*ModuleScope) Declare 

func (p *ModuleScope) Declare(submodule string, selector util.Option[string], public bool) bool

Declare a new submodule at the given (absolute) path within this tree scope. Submodules can be declared as "virtual" which indicates the submodule is simply a subset of rows of its enclosing module. A virtual module is indicated by a non-zero selector, which signals when the virtual module is active. This returns true if this succeeds, otherwise returns false (i.e. a matching submodule already exists).

func (*ModuleScope) Define 

func (p *ModuleScope) Define(symbol ast.SymbolDefinition) bool

Define a new symbol within this scope.

func (*ModuleScope) DestructuredColumns 

func (p *ModuleScope) DestructuredColumns() []RegisterSource

DestructuredColumns returns the set of (destructured) columns defined within this module scope. That is, source-level columns which are broken down into their atomic components.

func (*ModuleScope) DestructuredConstants 

func (p *ModuleScope) DestructuredConstants() []ast.ConstantBinding

DestructuredConstants returns the set of (destructured) constant definitions within this module scope.

func (*ModuleScope) Enter 

func (p *ModuleScope) Enter(submodule string) *ModuleScope

Enter returns a given submodule within this module.

func (*ModuleScope) Flatten 

func (p *ModuleScope) Flatten() []*ModuleScope

Flatten flattens the tree into a flat array of modules, such that a module always comes before its own submodules.

func (*ModuleScope) IsPublic 

func (p *ModuleScope) IsPublic() bool

IsPublic determines whether or not this is an externally visible module.

func (*ModuleScope) IsRoot 

func (p *ModuleScope) IsRoot() bool

IsRoot checks whether or not this is the root of the module tree.

func (*ModuleScope) IsVisible 

func (p *ModuleScope) IsVisible(symbol ast.Symbol) bool

IsVisible implemention for Scope interface.

func (*ModuleScope) IsWithin 

func (p *ModuleScope) IsWithin(path file.Path) bool

IsWithin checks whether a given path is local to the enclosing module, or not.

func (*ModuleScope) Name 

func (p *ModuleScope) Name() string

Name returns the name of the given module.

func (*ModuleScope) OpenDefinition 

func (p *ModuleScope) OpenDefinition(symbol ast.SymbolDefinition)

OpenDefinition indicates that the given symbol is in the process of being defined. This allows us to identify recursive uses of the given symbol (i.e. which arise during the period in which it being defined).

func (*ModuleScope) Owner 

func (p *ModuleScope) Owner() *ModuleScope

Owner returns the enclosing non-virtual module of this module. Observe that, if this is a non-virtual module, then it is returned.

func (*ModuleScope) Path 

func (p *ModuleScope) Path() *file.Path

Path returns the absolute path of this module.

func (*ModuleScope) Selector 

func (p *ModuleScope) Selector() util.Option[string]

Selector gets an MIR unit expression which evaluates to a non-zero value when this module is active. This can be nil if there is no selector (i.e. this is a non-virtual module).

func (*ModuleScope) Virtual 

func (p *ModuleScope) Virtual() bool

Virtual identifies whether or not this is a virtual module.

type NativeColumn 

type NativeColumn struct {
	// contains filtered or unexported fields
}

NativeColumn provides information about a column acting as a parameter or return in a given native function.

type NativeDefinition 

type NativeDefinition struct {
	// contains filtered or unexported fields
}

NativeDefinition describes a native function, such as specifying how many arguments it requires, etc.

func (*NativeDefinition) Apply 

func (p *NativeDefinition) Apply(args []NativeColumn) []NativeColumn

Apply returns the output columns given a set of input columns.

func (*NativeDefinition) Arity 

func (p *NativeDefinition) Arity() util.Option[uint]

Arity indicates whether or not this is a function and, if so, what arity (i.e. how many arguments) the function has.

func (*NativeDefinition) Binding 

func (p *NativeDefinition) Binding() ast.Binding

Binding returns the binding associated with this intrinsic.

func (*NativeDefinition) IsFinalised 

func (p *NativeDefinition) IsFinalised() bool

IsFinalised checks whether this binding has been finalised yet or not.

func (*NativeDefinition) IsNative 

func (p *NativeDefinition) IsNative() bool

IsNative checks whether this function binding is native (or not).

func (*NativeDefinition) IsPure 

func (p *NativeDefinition) IsPure() bool

IsPure checks whether this pure (which intrinsics always are).

func (*NativeDefinition) IsRecursive 

func (p *NativeDefinition) IsRecursive() bool

IsRecursive implementation for Binding interface.

func (*NativeDefinition) Lisp 

func (p *NativeDefinition) Lisp() sexp.SExp

Lisp returns a lisp representation of this intrinsic.

func (*NativeDefinition) Name 

func (p *NativeDefinition) Name() string

Name returns the name of the intrinsic being defined.

func (*NativeDefinition) Path 

func (p *NativeDefinition) Path() *file.Path

Path returns the qualified name (i.e. absolute path) of this symbol. For example, "m1.X" for a column X defined in module m1.

func (*NativeDefinition) Signature 

func (p *NativeDefinition) Signature() *ast.FunctionSignature

Signature returns the function signature for this binding.

type Parser 

type Parser struct {
	// contains filtered or unexported fields
}

Parser implements a simple parser for the Corset language. The parser itself is relatively simplistic and simply packages up the relevant lisp constructs into their corresponding AST forms. This can fail in various ways, such as e.g. a "defconstraint" not having exactly three arguments, etc. However, the parser does not attempt to perform more complex forms of validation (e.g. ensuring that expressions are well-typed, etc) --- that is left up to the compiler.

func NewParser 

func NewParser(srcfile source.File, srcmap *source.Map[sexp.SExp], config Config, handles map[string]bool,
) *Parser

NewParser constructs a new parser using a given mapping from S-Expressions to spans in the underlying source file.

func (*Parser) NodeMap 

func (p *Parser) NodeMap() *source.Map[ast.Node]

NodeMap extract the node map constructed by this parser. A key task here is to copy all mappings from the expression translator, which maintains its own map.

type Register 

type Register struct {
	// Context (i.e. module + multiplier) of this register.
	Context ast.Context
	// Underlying width of this register.
	Bitwidth uint
	// Common padding value
	Padding big.Int
	// Source columns of this register
	Sources []RegisterSource
	// contains filtered or unexported fields
}

Register encapsulates information about a "register" in the underlying constraint system. The rough analogy is that "register allocation" is applied to map Corset columns down to HIR columns (a.k.a. registers). The distinction between columns at the Corset level, and registers at the HIR level is necessary for two reasons: firstly, one corset column can expand to several HIR registers; secondly, register allocation is applied to columns in different perspectives of the same module.

func (*Register) Deactivate 

func (r *Register) Deactivate()

Deactivate marks a given register as no longer being required. This happens when one register is merged into another.

func (*Register) IsActive 

func (r *Register) IsActive() bool

IsActive determines whether or not this register is "active". Inactive registers should not generally be visible outside of register allocation.

func (*Register) IsInput 

func (r *Register) IsInput() bool

IsInput determines whether or not this register represents an input column, or not. NOTE: there is currently an implicit assumption that columns allocated to the same register always have the same "visibility" (i.e. are either all input, or all computed, etc).

func (*Register) Merge 

func (r *Register) Merge(other *Register)

Merge two registers together. This means the source-level columns will be allocated to the same underlying HIR column (i.e. register).

func (*Register) Name 

func (r *Register) Name() string

Name returns the given name for this register.

type RegisterAllocation 

type RegisterAllocation interface {
	// Access the set of registers being considered for allocation.
	Registers() iter.Iterator[uint]
	// Access information about a specific register.
	Register(uint) *Register
	// Merge one register (src) into another (dst).  This marks the source
	// register as inactive, but does not otherwise update the register
	// assignment.  Thus, existing register ids remain valid throughout register
	// allocation.  Once register allocation is complete, inactive registers are
	// then discarded.
	Merge(dst uint, src uint)
}

RegisterAllocation is a generic interface to support different "regsiter allocation" algorithms. More specifically, register allocation is the process of allocating columns to their underlying HIR columns (a.k.a registers). This is straightforward when there is a 1-1 mapping from a Corset column to an HIR column. However, this is not always the case. For example, array columns at the Corset level map to multiple columns at the HIR level. Likewise, perspectives allow columns to be reused, meaning that multiple columns at the Corset level can be mapped down to just a single column at the HIR level.

Notes:

* Arrays. These are allocated consecutive columns, as determined by their "width". That is, the size of the array.

* Perspectives. This is where the main challenge lies. Columns in different perspectives can be merged together, but this is only done when they have compatible underlying types.

type RegisterAllocationView 

type RegisterAllocationView struct {
	// contains filtered or unexported fields
}

RegisterAllocationView provides a view of an environment for the purposes of register allocation, such that only registers in this view will be considered for allocation. This is necessary because we must not attempt to allocate registers across different modules (indeed, contexts) together. Instead, we must allocate registers on a module-by-module basis, etc.

func (*RegisterAllocationView) Len 

func (p *RegisterAllocationView) Len() uint

Len returns the number of allocated registers.

func (*RegisterAllocationView) Merge 

func (p *RegisterAllocationView) Merge(dst uint, src uint)

Merge one register (src) into another (dst). This will remove the src register, and automatically update all column assignments. Therefore, any register identifier can be potenitally invalided by this operation. This will panic if the registers are incompatible (i.e. have different contexts).

func (*RegisterAllocationView) Register 

func (p *RegisterAllocationView) Register(index uint) *Register

Register accesses information about a specific register in this window.

func (*RegisterAllocationView) Registers 

func (p *RegisterAllocationView) Registers() iter.Iterator[uint]

Registers returns an iterator over the set of registers in this local allocation.

type RegisterAllocator 

type RegisterAllocator struct {
	// contains filtered or unexported fields
}

RegisterAllocator is a simple, but reasonably effective high-level approach to register allocation. Essentially, perspective columns are sorted by type and then allocated based on their "compatibility". Here, compatibility determines when two registers can be merged (i.e. when they are "compatible"_. This allocator is parameterised over the notion of compatibility in order to support different top-level allocation algorithms.

func NewRegisterAllocator 

func NewRegisterAllocator(allocation RegisterAllocation) *RegisterAllocator

NewRegisterAllocator initialises a new greedy sort allocator from an initial allocation with a given compatibility function.

func (*RegisterAllocator) CompactBy 

func (p *RegisterAllocator) CompactBy(predicate AllocationComparator)

CompactBy Greedily compact the given allocation using a given "compabitility" comparator.

func (*RegisterAllocator) Finalise 

func (p *RegisterAllocator) Finalise()

Finalise the register allocation by merging allocated registers in the same slot.

func (*RegisterAllocator) Width 

func (p *RegisterAllocator) Width() uint

Width returns the current number of non-empty groups.

type RegisterGroup 

type RegisterGroup struct {
	// contains filtered or unexported fields
}

RegisterGroup represents a group of registers which (eventually) will be allocated to the same column. The intuition is that, initially, we begin with a single group for each register. Then, groups are merged together according to the high-level allocation algorithm.

func NewRegisterGroup 

func NewRegisterGroup(bitwidth uint, mustProve bool) RegisterGroup

NewRegisterGroup constructs a new (and empty) register group.

func (*RegisterGroup) Assign 

func (p *RegisterGroup) Assign(slot uint, reg uint)

Assign a register to a given slot in this group. If the slot is already taken, then this will panic.

func (*RegisterGroup) Available 

func (p *RegisterGroup) Available(slot uint) bool

Available determines whether a given slot has been set already.

func (*RegisterGroup) Disjoint 

func (p *RegisterGroup) Disjoint(other *RegisterGroup) bool

Disjoint checks whether this allocation and another are disjoint. That is, they do not have registers allocated to the same slot.

func (*RegisterGroup) IsEmpty 

func (p *RegisterGroup) IsEmpty() bool

IsEmpty checks whether this group is empty or not. Groups can become empty when they are merged into others.

func (*RegisterGroup) Merge 

func (p *RegisterGroup) Merge(other *RegisterGroup)

Merge another allocation into this allocation. This leaves the other allocation in the unused state (i.e. it will be ignored from now on).

func (*RegisterGroup) String 

func (p *RegisterGroup) String() string

func (*RegisterGroup) Target 

func (p *RegisterGroup) Target() uint

Target returns the register with the least index within this allocation.

type RegisterSlot 

type RegisterSlot struct {
	// contains filtered or unexported fields
}

RegisterSlot represents a register in a given "slot". The intuition is that each perspective is allocated its own slot. Thus, the goal of register allocation is to group compatible registers in different perspectives (i.e. slots).

func (RegisterSlot) Cmp 

func (p RegisterSlot) Cmp(other RegisterSlot) int

Cmp implements the necessary comparator for register slots.

type RegisterSource 

type RegisterSource struct {
	// Context is a prefix of name which, when they differ, indicates a virtual
	// column (i.e. one which is subject to register allocation).
	Context file.Path
	// Fully qualified (i.e. absolute) Name of source-level column.
	Name file.Path
	// Length Multiplier of source-level column.
	Multiplier uint
	// Underlying bitwidth of the source-level column.
	Bitwidth uint
	// Provability requirement for source-level column.
	MustProve bool
	// Determines whether this is a Computed column.
	Computed bool
	// Determines value used for padding
	Padding big.Int
	// Display modifier
	Display string
}

RegisterSource provides necessary information about source-level columns allocated to a given register.

func (*RegisterSource) IsVirtual 

func (p *RegisterSource) IsVirtual() bool

IsVirtual indicates whether or not this is a "virtual" column. That is, something which is subject to register allocation (i.e. because it is declared in a perspective).

func (*RegisterSource) Perspective 

func (p *RegisterSource) Perspective() string

Perspective returns the name of the "virtual perspective" in which this column exists.

type SchemaBuilder 

type SchemaBuilder = ir.SchemaBuilder[word.BigEndian, hir.Constraint, hir.Term]

SchemaBuilder is used within this translator for building the final mixed HIR schema.

type Scope 

type Scope interface {
	// Attempt to bind a given symbol within this scope.  If successful, the
	// symbol is then resolved with the appropriate binding.  Return value
	// indicates whether successful or not.
	Bind(ast.Symbol) bool

	// Bindings returns all binding identifiers within a given path.
	Bindings(file.Path) []BindingId

	// Check whether a given path is within the enclosing module, or not.
	IsWithin(file.Path) bool

	// Check whether the given symbol is in the process of being defined in the
	// enclose scope.  Thus, if we encounter an this symbol within e.g. some
	// expression whilst it is being defined ... we know its a recursive access.
	// Depending on how the symbol is defined this may (or may not) result in an
	// error.
	IsVisible(ast.Symbol) bool
}

Scope represents a region of code in which an expression can be evaluated. The purpose of a scope is to assist with determining what, exactly, a given variable used within an expression refers to. For example, a variable can refer to a column, or a parameter, etc.

type SyntaxError 

type SyntaxError = source.SyntaxError

SyntaxError defines the kind of errors that can be reported by this compiler. Syntax errors are always associated with some line in one of the original source files. For simplicity, we reuse existing notion of syntax error from the S-Expression library.

func ParseSourceFiles 

func ParseSourceFiles(files []source.File, config Config) (ast.Circuit, *source.Maps[ast.Node], []SyntaxError)

ParseSourceFiles parses zero or more source files producing zero or more modules. Observe that, since a given module can be spread over multiple files, there can be far few modules created than there are source files. This function does more than just parse the individual files, because it additional combines all fragments of the same module together into one place. Thus, you should never expect to see duplicate module names in the returned array.

func PreprocessCircuit 

func PreprocessCircuit(debug bool, srcmap *source.Maps[ast.Node],
	circuit *ast.Circuit) []SyntaxError

PreprocessCircuit performs preprocessing prior to final translation. Specifically, it expands all invocations, reductions and for loops. Thus, final translation is greatly simplified after this step.

func TranslateCircuit 

func TranslateCircuit(
	env Environment,
	srcmap *source.Maps[ast.Node],
	circuit *ast.Circuit,
	config Config) (asm.MicroHirProgram, []SyntaxError)

TranslateCircuit translates the components of a Corset circuit and add them to the schema. By the time we get to this point, all malformed source files should have been rejected already and the translation should go through easily. Thus, whilst syntax errors can be returned here, this should never happen. The mechanism is supported, however, to simplify development of new features, etc.

func TypeCheckCircuit 

func TypeCheckCircuit(srcmap *source.Maps[ast.Node],
	circuit *ast.Circuit) []SyntaxError

TypeCheckCircuit performs a type checking pass over the circuit to ensure types are used correctly. Additionally, this resolves some ambiguities arising from the possibility of overloading function calls, etc.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.