func SchemaDiff(old, new *DBSchema) ChangeSet {
	var cs ChangeSet
	for _, oldTable := range old.Tables {
		if t := new.Table(oldTable.Name); t == nil {
			cs = append(cs, &DropTable{Name: oldTable.Name})
		} else {
			cs = append(cs, TableSchemaDiff(oldTable, t)...)
		}
	}
	for _, newTable := range new.Tables {
		if t := old.Table(newTable.Name); t == nil {
			cs = append(cs, &CreateTable{newTable})
		}
	}
	return cs
}
SchemaDiff generates a change set with the diff between two schemas.
package generator
import (
	"bytes"
	"encoding"
	"encoding/json"
	"fmt"
	"strings"
)
type Migration struct {
	Up ChangeSet
	Down ChangeSet
	Lock *DBSchema
}
func NewMigration(old, new *DBSchema) (*Migration, error) {
	var (
		migration = &Migration{}
		err       error
		oldTables = old.index()
		newTables = new.index()
	)
	migration.Up, err = SchemaDiff(old, new).
		sorted(oldTables, newTables)
	if err != nil {
		return nil, err
	}
	migration.Down, err = migration.Up.
		ReverseChangeSet(old).
		sorted(newTables, oldTables)
	if err != nil {
		return nil, err
	}
	migration.Lock = new
	return migration, nil
}
type DBSchema struct {
	Tables []*TableSchema
}
func SchemaFromPackages(pkgs ...*Package) (*DBSchema, error) {
	t := newPackageTransformer()
	return t.transform(pkgs...)
}
func (s *DBSchema) MarshalText() ([]byte, error) {
	schema := struct {
		Tables []*TableSchema
	}{s.Tables}
	return json.MarshalIndent(schema, "", "  ")
}
func (s *DBSchema) Table(name string) *TableSchema {
	for _, t := range s.Tables {
		if t.Name == name {
			return t
		}
	}
	return nil
}
func (s *DBSchema) index() map[string]*TableSchema {
	var result = make(map[string]*TableSchema)
	for _, t := range s.Tables {
		result[t.Name] = t
	}
	return result
}
type TableSchema struct {
	Name string
	Columns []*ColumnSchema
}
type relationship struct {
	name    string
	inverse bool
}
func (s *TableSchema) relationships() []relationship {
	var rels = make(map[string]struct{})
	var result []relationship
	for _, c := range s.Columns {
		if c.Reference != nil {
			if _, ok := rels[c.Reference.Table]; !ok {
				result = append(result, relationship{c.Reference.Table, c.Reference.inverse})
				rels[c.Reference.Table] = struct{}{}
			}
		}
	}
	return result
}
func (s *TableSchema) String() string {
	var buf bytes.Buffer
	buf.WriteString(fmt.Sprintf("CREATE TABLE %s (\n", s.Name))
	for i, c := range s.Columns {
		buf.WriteRune('\t')
		buf.WriteString(c.String())
		if i < len(s.Columns)-1 {
			buf.WriteString(",\n")
		} else {
			buf.WriteRune('\n')
		}
	}
	buf.WriteString(");\n\n")
	return buf.String()
}
func (s *TableSchema) Column(name string) *ColumnSchema {
	for _, c := range s.Columns {
		if c.Name == name {
			return c
		}
	}
	return nil
}
func (s *TableSchema) Equals(s2 *TableSchema) bool {
	if s.Name != s2.Name || len(s.Columns) != len(s2.Columns) {
		return false
	}
	for i, c := range s.Columns {
		if !c.Equals(s2.Columns[i]) {
			return false
		}
	}
	return true
}
type ColumnSchema struct {
	Name string
	Type ColumnType
	PrimaryKey bool
	Reference *Reference
	NotNull bool
	Unique bool
}
func (s *ColumnSchema) Equals(s2 *ColumnSchema) bool {
	return s.Name == s2.Name &&
		s.Type == s2.Type &&
		s.PrimaryKey == s2.PrimaryKey &&
		s.NotNull == s2.NotNull &&
		s.Unique == s2.Unique &&
		s.Reference.Equals(s2.Reference)
}
func (s *ColumnSchema) String() string {
	var buf bytes.Buffer
	buf.WriteString(s.Name)
	buf.WriteRune(' ')
	buf.WriteString(string(s.Type))
	if s.NotNull {
		buf.WriteString(" NOT NULL")
	}
	if s.Unique {
		buf.WriteString(" UNIQUE")
	}
	if s.PrimaryKey {
		buf.WriteString(" PRIMARY KEY")
	}
	if s.Reference != nil {
		buf.WriteString(" REFERENCES ")
		buf.WriteString(s.Reference.String())
	}
	return buf.String()
}
type ColumnType string
const (
	ByteaColumn       ColumnType = "bytea"
	SmallIntColumn    ColumnType = "smallint"
	IntegerColumn     ColumnType = "integer"
	BigIntColumn      ColumnType = "bigint"
	RealColumn        ColumnType = "real"
	DoubleColumn      ColumnType = "double precision"
	SmallSerialColumn ColumnType = "smallserial"
	SerialColumn      ColumnType = "serial"
	BigSerialColumn   ColumnType = "bigserial"
	TimestamptzColumn ColumnType = "timestamptz"
	TextColumn        ColumnType = "text"
	JSONBColumn       ColumnType = "jsonb"
	BooleanColumn     ColumnType = "boolean"
	UUIDColumn        ColumnType = "uuid"
)
func NumericColumn(precision int) ColumnType {
	return ColumnType(fmt.Sprintf("numeric(%d)", precision))
}
func DecimalColumn(precision, scale int) ColumnType {
	return ColumnType(fmt.Sprintf("decimal(%d, %d)", precision, scale))
}
func ArrayColumn(typ ColumnType) ColumnType {
	if strings.HasSuffix(string(typ), "[]") {
		return typ
	}
	return typ + "[]"
}
type Reference struct {
	Table string
	Column  string
	inverse bool
}
func (r *Reference) Equals(r2 *Reference) bool {
	if r == nil && r2 == nil {
		return true
	} else if r == nil || r2 == nil {
		return false
	}
	return r.Table == r2.Table &&
		r.Column == r2.Column
}
func (r *Reference) String() string {
	return fmt.Sprintf("%s(%s)", r.Table, r.Column)
}
type ChangeSet []Change
func (cs ChangeSet) sorted(dropIndex, createIndex map[string]*TableSchema) (ChangeSet, error) {
	var (
		createTables = make(map[string]Change)
		dropTables   = make(map[string]Change)
		createGraph  = newGraph()
		dropGraph    = newGraph()
		others       ChangeSet
		result       ChangeSet
	)
	for _, c := range cs {
		switch c := c.(type) {
		case *CreateTable:
			createTables[c.Name] = c
			if rels := createIndex[c.Name].relationships(); len(rels) > 0 {
				for _, r := range rels {
					if r.name == c.Name {
						continue
					}
					createGraph.dependsOn(r.name, c.Name)
				}
			} else {
				createGraph.add(c.Name)
			}
		case *DropTable:
			dropTables[c.Name] = c
			if rels := dropIndex[c.Name].relationships(); len(rels) > 0 {
				for _, r := range rels {
					if r.name == c.Name {
						continue
					}
					dropGraph.dependsOn(r.name, c.Name)
				}
			} else {
				dropGraph.add(c.Name)
			}
		default:
			others = append(others, c)
		}
	}
	creates, err := createGraph.resolve()
	if err != nil {
		return nil, err
	}
	for _, c := range creates {
		if change, ok := createTables[c]; ok {
			result = append(result, change)
		}
	}
	drops, err := dropGraph.resolve()
	if err != nil {
		return nil, err
	}
	drops = reverse(drops)
	for _, d := range drops {
		if change, ok := dropTables[d]; ok {
			result = append(result, change)
		}
	}
	result = append(result, others...)
	return result, nil
}
func (cs ChangeSet) MarshalText() ([]byte, error) {
	var buf bytes.Buffer
	buf.WriteString("BEGIN;\n\n")
	for _, c := range cs {
		bytes, err := c.MarshalText()
		if err != nil {
			return nil, err
		}
		buf.Write(bytes)
		buf.WriteRune('\n')
	}
	buf.WriteString("COMMIT;\n")
	return buf.Bytes(), nil
}
func (cs ChangeSet) String() string {
	var buf bytes.Buffer
	for _, c := range cs {
		buf.WriteString(fmt.Sprintf("- %s", c))
	}
	return buf.String()
}
func (cs ChangeSet) Reverse(old *DBSchema) Change {
	var result = make(ChangeSet, len(cs))
	for i, c := range cs {
		result[i] = c.Reverse(old)
	}
	return result
}
func (cs ChangeSet) ReverseChangeSet(old *DBSchema) ChangeSet {
	return cs.Reverse(old).(ChangeSet)
}
type Change interface {
	encoding.TextMarshaler
	fmt.Stringer
	Reverse(old *DBSchema) Change
}
type CreateTable struct {
	*TableSchema
}
func (c *CreateTable) Reverse(old *DBSchema) Change {
	return &DropTable{Name: c.Name}
}
func (c *CreateTable) MarshalText() ([]byte, error) {
	return []byte(c.TableSchema.String()), nil
}
func (c *CreateTable) String() string {
	var cols = make([]string, len(c.Columns))
	for i, c := range c.Columns {
		cols[i] = c.Name
	}
	return fmt.Sprintf("A new table %q has been added with the following columns: %s.", c.Name, strings.Join(cols, ", "))
}
type DropTable struct {
	Name string
}
func (c *DropTable) Reverse(old *DBSchema) Change {
	return &CreateTable{old.Table(c.Name)}
}
func (c *DropTable) MarshalText() ([]byte, error) {
	return []byte(fmt.Sprintf("DROP TABLE %s;\n", c.Name)), nil
}
func (c *DropTable) String() string {
	return fmt.Sprintf("Table %q has been deleted, and it will be dropped.", c.Name)
}
type AddColumn struct {
	Column *ColumnSchema
	Table string
}
func (c *AddColumn) Reverse(old *DBSchema) Change {
	return &DropColumn{
		Table: c.Table,
		Name:  c.Column.Name,
	}
}
func (c *AddColumn) String() string {
	return fmt.Sprintf("A new column %q of type %q has been added to table %q.", c.Column.Name, c.Column.Type, c.Table)
}
func (c *AddColumn) MarshalText() ([]byte, error) {
	return []byte(fmt.Sprintf("ALTER TABLE %s ADD COLUMN %s;\n", c.Table, c.Column)), nil
}
type DropColumn struct {
	Name string
	Table string
}
func (c *DropColumn) Reverse(old *DBSchema) Change {
	return &AddColumn{
		Table:  c.Table,
		Column: old.Table(c.Table).Column(c.Name),
	}
}
func (c *DropColumn) String() string {
	return fmt.Sprintf("The column %q of table %q has been removed and it will be dropped.", c.Name, c.Table)
}
func (c *DropColumn) MarshalText() ([]byte, error) {
	return []byte(fmt.Sprintf("ALTER TABLE %s DROP COLUMN %s;\n", c.Table, c.Name)), nil
}
type CreateIndex struct {
	Table string
	Column string
	Kind string
}
func (c *CreateIndex) Reverse(old *DBSchema) Change {
	return &DropIndex{
		Table:  c.Table,
		Column: c.Column,
		Kind:   c.Kind,
	}
}
func (c *CreateIndex) String() string {
	return fmt.Sprintf("A manual change is required because a new %q index has been added at column %q of table %q.", c.Kind, c.Column, c.Table)
}
func (c *CreateIndex) MarshalText() ([]byte, error) {
	var unique string
	if c.Kind == "unique" {
		unique = "UNIQUE"
	}
	return []byte(fmt.Sprintf(`+++
THIS REQUIRES MANUAL MIGRATION:
Adding an index on a table that may not be empty.
If you're sure about this, here's the SQL for this operation.
+++
CREATE %s INDEX %s ON %s;
`, unique, indexName(c.Table, c.Column, c.Kind), c.Table)), nil
}
type DropIndex struct {
	Table string
	Column string
	Kind string
}
func (c *DropIndex) Reverse(old *DBSchema) Change {
	return &CreateIndex{
		Table:  c.Table,
		Column: c.Column,
		Kind:   c.Kind,
	}
}
func (c *DropIndex) String() string {
	return fmt.Sprintf("The %q index at column %q of table %q has been removed and it will be dropped.", c.Kind, c.Column, c.Table)
}
func (c *DropIndex) MarshalText() ([]byte, error) {
	return []byte(fmt.Sprintf("DROP INDEX %s;\n", indexName(c.Table, c.Column, c.Kind))), nil
}
type ManualChange struct {
	Msg string
}
func (c *ManualChange) Reverse(old *DBSchema) Change {
	return c
}
func (c *ManualChange) String() string {
	return fmt.Sprintf("A manual change is required: %s.", c.Msg)
}
func (c *ManualChange) MarshalText() ([]byte, error) {
	return []byte(fmt.Sprintf("+++ THIS REQUIRES MANUAL MIGRATION: %s +++\n", c.Msg)), nil
}
type graph struct {
	nodeList []string
	nodes    map[string]*node
}
type resolutionCtx struct {
	resolved   map[string]struct{}
	unresolved map[string]struct{}
	names      []string
}
func newGraph() *graph {
	return &graph{nil, make(map[string]*node)}
}
func (g *graph) add(name string) *graph {
	if _, ok := g.nodes[name]; !ok {
		g.nodeList = append(g.nodeList, name)
		g.nodes[name] = newNode(name)
	}
	return g
}
func (g *graph) dependsOn(dependant, dependency string) *graph {
	g.node(dependency).addDependant(g.node(dependant))
	g.node(dependant).addDependency(g.node(dependency))
	return g
}
func (g *graph) node(name string) *node {
	g.add(name)
	return g.nodes[name]
}
func (g *graph) resolve() ([]string, error) {
	ctx := &resolutionCtx{
		make(map[string]struct{}),
		make(map[string]struct{}),
		nil,
	}
	for _, n := range g.nodeList {
		node := g.nodes[n]
		if len(node.dependencies) == 0 {
			if err := g.nodes[n].resolve(ctx); err != nil {
				return nil, err
			}
		}
	}
	if len(g.nodes) != len(ctx.names) {
		return nil, fmt.Errorf("kallax: unable to resolve all the table dependencies. There is probably a circular dependency somewhere.")
	}
	return ctx.names, nil
}
type node struct {
	name         string
	dependants   []*node
	dependencies []*node
}
func newNode(name string) *node {
	return &node{name, nil, nil}
}
func (n *node) addDependant(node *node) {
	n.dependants = append(n.dependants, node)
}
func (n *node) addDependency(node *node) {
	n.dependencies = append(n.dependencies, node)
}
func (n *node) resolve(ctx *resolutionCtx) error {
	ctx.unresolved[n.name] = struct{}{}
	for _, dep := range n.dependants {
		if _, ok := ctx.resolved[dep.name]; !ok {
			if _, ok := ctx.unresolved[dep.name]; ok {
				return fmt.Errorf("kallax: there is a circular dependency between %s and %s", n.name, dep.name)
			}
			if err := dep.resolve(ctx); err != nil {
				return err
			}
		}
	}
	delete(ctx.unresolved, n.name)
	ctx.resolved[n.name] = struct{}{}
	ctx.names = append(ctx.names, n.name)
	return nil
}