Typeinst

Typeinst is a tool to automate the creation of concrete types ("type instances") from generic/"template" types.

Typeinst uses the special fake struct declaration (DSL-struct, for brevity) as the description of what types should be generated:

import (
  "github.com/dlepex/genericlib/set"
  "github.com/dlepex/genericlib/slice"
  "some/thirparty/generic/package/redblack"
)
//go:generate typeinst
type _typeinst struct {
  StrSet        func(E string)  set.Set
  ints          func(E int)     (slice.Basic, slice.Pred)
  FloatTreeMap  func(K float64, V float64) redblack.TreeMap
}

Each field of DSL-struct defines the single concrete type.

For each field DSL-func describes the substitution of type variables and the result of DSL-func is the generic type where this substitution takes place. The substitution is done by name.

Usage

Typeinst is to be used with go generate, it has no command line options: it uses DSL-struct as its sole "option".

Install the tool first: go get github.com/dlepex/typeinst
Declare DSL-struct in some file of your package, together with go-generate comment, as in the example above.
- The DSL-struct name must start with _typeinst prefix, it is strongly recommended to have one DSL-struct per package, and to declare it in a separate file.
Run go generate on your package.
The result is <file>_ti.go, where <file> is a name of the file where DSL-struct is declared. The file is generated in the same package and it contains ALL concrete types described by DSL-struct.
This repo https://github.com/dlepex/genericlib contains some usefull generic types e.g. generic slice ops and generic set

Features

Selective type instantiation: Typeinst only generates the requested types, not the whole generic package at once: this tool is type-based, not package-based.
Constructor functions support
Type merging support
No mandatory magic comments, and no magic imports in generic code
Special support for empty singleton generic types.

Terminology

Type variable

Type variables (type-parameters of generic types) are declared within generic package, usually as an empty interface:

type E interface{}
type A = interface{} // Alias form is ok too

type C interface { // Non-empty interface type variables can be used as well.
	Less(C) bool     // Type variable C can only be substituted by types having `Less()` method.
}

The names of DSL-func parameters define what types will serve as type variables

As an implementor of a generic package you may optionally use the special "typevar"-comment:

type E = interface{} //typeinst: typevar

This comment provides error message, in case a user of your generic package omits the type variable in DSL-func.

Please note that, if the "typevar"-comment was used for one type variable, it MUST be used for the rest of them (in the same generic package).

Generic type

A type is considered generic if it depends on at least one type variable.

Generic type G consists of:

type declaration
methods (functions with receiver G or *G)
constructor functions

Root generic types are the types that are explicitly instantiated (i.e. the results of DSL-funcs)

Root types may depend on non-root generic types, non-root types are implicitly instantiated and implicitly named. For instance, hypothetical root type AVLTree depends on non-root type AVLTreeNode.

If you do not like the implicit ("mangled") names of non-root types, you can always name them on your own by making them root, i.e. by adding their explicit instantiation to DSL-struct.

Constructor function

Constructor function of generic type G is a function that returns:

G, *G, []G, [n]G
or their combination (e.g. **G, *[42]G,[][][]*G), max nesting depth is 16.
in case of multiple return values: only the first return var is checked.

Constructor functions usually have names started with New, but this is not enforced.

Type dependency relation

Type A directly depends on type B if type B occurs in:

type A declaration
signatures of type A methods or constructor functions

Type dependency is a transitive, non-symmetric relation.

Generic package

Generic package contains generic types and their type variables

Generic packages cannot contain non-generic code, move it to separate non-generic package if needed.

Non-generic code includes:

functions (w/o receiver), excluding constructors of generic types
non-generic types and their methods
var declarations

Const declarations are allowed in generic packages. Typeinst directly substitutes constants by their values.

Generic package may import other packages. Imported packages are never treated as generic themselves, i.e. a generic type from one package cannot depend on a generic type from another package.

Type merging

Type merging allows an instantiated type to be assembled from multiple orthogonal behavioral parts (or in other words: non-intersecting method sets).

"Behavioral parts" must have the same declared type after the substitution of type variables.

type T = interface{}
type SliceF T[] // this type has filtering methods
func (a SliceF) Filter(...) ... {...}

type SliceA T[] // and this - aggregation methods: it may be declared in another generic package, with another (differently named) type variable.
func (a SliceA) Reduce(...) ... {...}

The merged type IntSlice based on this 2 types may be created using multiple return types in DSL-func:

//go:generate typeinst
type _typeinst struct {
	IntSlice	func(T int) (somepkg.SliceA, somepkg.SliceF)
}

IntSlice will contain both filtering and aggregation methods.

Empty singleton generic types and generic functions

ESGT are declared as empty structs and serve as dummy receivers for their methods, and thus they can be used for generic function imitation. Typeinst is type-based and it is impossible to create generic functions directly.

Here is an example:

type E interface{} // E is a type var
type ChanMerge struct{} // ESGT which depends on E through its method Merge i.e. this type is generic

func (ChanMerge) Apply(cs ...<-chan E) <-chan E {...}

For ESGT Typeinst will not only generate a type-declaration, but also a var-declaration. If ESGT contains just a single method named Apply Typeinst will generate a function declaration instead.

//go:generate typeinst
type _typeinst struct {
	intChanMerge	func(E int) (somepkg.ChanMerge)
}

In this example Typeinst will generate func intChanMerge(cs ...<-chan int) <-chan int {...} .

As a side note, since ESGT are just named empty structs, they are potentially type-mergeable.

Limitations

Imports in generic packages:
- must have consistent import names across all files of the same generic package
- dot . import is not allowed
Type variables cannot be substituted by:
- "anonymous" non-empty struct [solution: use named types or type alias]
- "anonymous" non-empty interface [solution: the same]
Functions w/o receiver (except constructors) cannot be generic [solution: ESGT]
Read generic package section
Not all errors are checked during code generation, some of them will potentially result in uncompilable code:
- non-generic code in generic package
- merging unmergeable types
- identifier name clashes or shadowing
It is worth to remember that Typeinst is a code generator and not a typechecker, and that in many cases interface{} is ok.

Implementation notes

AST rewriting is not used. Identifier substitution happens simultaneously with printing AST to file. For that purpose, the standard "go/printer" package was slightly modified: extra field RenameFunc was added to the Config struct.
Typeinst has been used to generate a part of itself: gentypes.go

dlepex/typeinst