serialize.go

// Copyright 2015 Google Inc. All rights reserved
//
// 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.

package kati

import (
	"bytes"
	"crypto/sha1"
	"encoding/binary"
	"encoding/gob"
	"encoding/json"
	"fmt"
	"io"
	"io/ioutil"
	"net/url"
	"os"
	"sort"
	"strconv"
	"strings"
	"time"

	"github.com/golang/glog"
)

const (
	valueTypeRecursive = 'R'
	valueTypeSimple    = 'S'
	valueTypeTSV       = 'T'
	valueTypeUndefined = 'U'
	valueTypeAssign    = 'a'
	valueTypeExpr      = 'e'
	valueTypeFunc      = 'f'
	valueTypeLiteral   = 'l'
	valueTypeNop       = 'n'
	valueTypeParamref  = 'p'
	valueTypeVarref    = 'r'
	valueTypeVarsubst  = 's'
	valueTypeTmpval    = 't'
)

// JSON is a json loader/saver.
var JSON LoadSaver

// GOB is a gob loader/saver.
var GOB LoadSaver

func init() {
	JSON = jsonLoadSaver{}
	GOB = gobLoadSaver{}
}

type jsonLoadSaver struct{}
type gobLoadSaver struct{}

type dumpbuf struct {
	w   bytes.Buffer
	err error
}

func (d *dumpbuf) Int(i int) {
	if d.err != nil {
		return
	}
	v := int32(i)
	d.err = binary.Write(&d.w, binary.LittleEndian, &v)
}

func (d *dumpbuf) Str(s string) {
	if d.err != nil {
		return
	}
	d.Int(len(s))
	if d.err != nil {
		return
	}
	_, d.err = io.WriteString(&d.w, s)
}

func (d *dumpbuf) Bytes(b []byte) {
	if d.err != nil {
		return
	}
	d.Int(len(b))
	if d.err != nil {
		return
	}
	_, d.err = d.w.Write(b)
}

func (d *dumpbuf) Byte(b byte) {
	if d.err != nil {
		return
	}
	d.err = writeByte(&d.w, b)
}

type serializableVar struct {
	Type     string
	V        string
	Origin   string
	Children []serializableVar
}

type serializableDepNode struct {
	Output             int
	Cmds               []string
	Deps               []int
	OrderOnlys         []int
	Parents            []int
	HasRule            bool
	IsPhony            bool
	ActualInputs       []int
	TargetSpecificVars []int
	Filename           string
	Lineno             int
}

type serializableTargetSpecificVar struct {
	Name  string
	Value serializableVar
}

type serializableGraph struct {
	Nodes       []*serializableDepNode
	Vars        map[string]serializableVar
	Tsvs        []serializableTargetSpecificVar
	Targets     []string
	Roots       []string
	AccessedMks []*accessedMakefile
	Exports     map[string]bool
}

func encGob(v interface{}) (string, error) {
	var buf bytes.Buffer
	e := gob.NewEncoder(&buf)
	err := e.Encode(v)
	if err != nil {
		return "", err
	}
	return buf.String(), nil
}

func encVar(k string, v Var) (string, error) {
	var dump dumpbuf
	dump.Str(k)
	v.dump(&dump)
	return dump.w.String(), dump.err
}

type depNodesSerializer struct {
	nodes     []*serializableDepNode
	tsvs      []serializableTargetSpecificVar
	tsvMap    map[string]int
	targets   []string
	targetMap map[string]int
	done      map[string]bool
	err       error
}

func newDepNodesSerializer() *depNodesSerializer {
	return &depNodesSerializer{
		tsvMap:    make(map[string]int),
		targetMap: make(map[string]int),
		done:      make(map[string]bool),
	}
}

func (ns *depNodesSerializer) serializeTarget(t string) int {
	id, present := ns.targetMap[t]
	if present {
		return id
	}
	id = len(ns.targets)
	ns.targetMap[t] = id
	ns.targets = append(ns.targets, t)
	return id
}

func (ns *depNodesSerializer) serializeDepNodes(nodes []*DepNode) {
	if ns.err != nil {
		return
	}
	for _, n := range nodes {
		if ns.done[n.Output] {
			continue
		}
		ns.done[n.Output] = true

		var deps []int
		for _, d := range n.Deps {
			deps = append(deps, ns.serializeTarget(d.Output))
		}
		var orderonlys []int
		for _, d := range n.OrderOnlys {
			orderonlys = append(orderonlys, ns.serializeTarget(d.Output))
		}
		var parents []int
		for _, d := range n.Parents {
			parents = append(parents, ns.serializeTarget(d.Output))
		}
		var actualInputs []int
		for _, i := range n.ActualInputs {
			actualInputs = append(actualInputs, ns.serializeTarget(i))
		}

		// Sort keys for consistent serialization.
		var tsvKeys []string
		for k := range n.TargetSpecificVars {
			tsvKeys = append(tsvKeys, k)
		}
		sort.Strings(tsvKeys)

		var vars []int
		for _, k := range tsvKeys {
			v := n.TargetSpecificVars[k]
			sv := serializableTargetSpecificVar{Name: k, Value: v.serialize()}
			//gob := encGob(sv)
			gob, err := encVar(k, v)
			if err != nil {
				ns.err = err
				return
			}
			id, present := ns.tsvMap[gob]
			if !present {
				id = len(ns.tsvs)
				ns.tsvMap[gob] = id
				ns.tsvs = append(ns.tsvs, sv)
			}
			vars = append(vars, id)
		}

		ns.nodes = append(ns.nodes, &serializableDepNode{
			Output:             ns.serializeTarget(n.Output),
			Cmds:               n.Cmds,
			Deps:               deps,
			OrderOnlys:         orderonlys,
			Parents:            parents,
			HasRule:            n.HasRule,
			IsPhony:            n.IsPhony,
			ActualInputs:       actualInputs,
			TargetSpecificVars: vars,
			Filename:           n.Filename,
			Lineno:             n.Lineno,
		})
		ns.serializeDepNodes(n.Deps)
		if ns.err != nil {
			return
		}
		ns.serializeDepNodes(n.OrderOnlys)
		if ns.err != nil {
			return
		}
	}
}

func makeSerializableVars(vars Vars) (r map[string]serializableVar) {
	r = make(map[string]serializableVar)
	for k, v := range vars {
		r[k] = v.serialize()
	}
	return r
}

func makeSerializableGraph(g *DepGraph, roots []string) (serializableGraph, error) {
	ns := newDepNodesSerializer()
	ns.serializeDepNodes(g.nodes)
	v := makeSerializableVars(g.vars)
	return serializableGraph{
		Nodes:       ns.nodes,
		Vars:        v,
		Tsvs:        ns.tsvs,
		Targets:     ns.targets,
		Roots:       roots,
		AccessedMks: g.accessedMks,
		Exports:     g.exports,
	}, ns.err
}

func (jsonLoadSaver) Save(g *DepGraph, filename string, roots []string) error {
	startTime := time.Now()
	sg, err := makeSerializableGraph(g, roots)
	if err != nil {
		return err
	}
	o, err := json.MarshalIndent(sg, " ", " ")
	if err != nil {
		return err
	}
	f, err := os.Create(filename)
	if err != nil {
		return err
	}
	_, err = f.Write(o)
	if err != nil {
		f.Close()
		return err
	}
	err = f.Close()
	if err != nil {
		return err
	}
	logStats("json serialize time: %q", time.Since(startTime))
	return nil
}

func (gobLoadSaver) Save(g *DepGraph, filename string, roots []string) error {
	startTime := time.Now()
	f, err := os.Create(filename)
	if err != nil {
		return err
	}
	e := gob.NewEncoder(f)
	var sg serializableGraph
	{
		startTime := time.Now()
		sg, err = makeSerializableGraph(g, roots)
		if err != nil {
			return err
		}
		logStats("gob serialize prepare time: %q", time.Since(startTime))
	}
	{
		startTime := time.Now()
		err = e.Encode(sg)
		if err != nil {
			return err
		}
		logStats("gob serialize output time: %q", time.Since(startTime))
	}
	err = f.Close()
	if err != nil {
		return err
	}
	logStats("gob serialize time: %q", time.Since(startTime))
	return nil
}

func cacheFilename(mk string, roots []string) string {
	filename := ".kati_cache." + mk
	for _, r := range roots {
		filename += "." + r
	}
	return url.QueryEscape(filename)
}

func saveCache(g *DepGraph, roots []string) error {
	if len(g.accessedMks) == 0 {
		return fmt.Errorf("no Makefile is read")
	}
	cacheFile := cacheFilename(g.accessedMks[0].Filename, roots)
	for _, mk := range g.accessedMks {
		// Inconsistent, do not dump this result.
		if mk.State == fileInconsistent {
			if exists(cacheFile) {
				os.Remove(cacheFile)
			}
			return nil
		}
	}
	return GOB.Save(g, cacheFile, roots)
}

func deserializeSingleChild(sv serializableVar) (Value, error) {
	if len(sv.Children) != 1 {
		return nil, fmt.Errorf("unexpected number of children: %q", sv)
	}
	return deserializeVar(sv.Children[0])
}

func deserializeVar(sv serializableVar) (r Value, err error) {
	switch sv.Type {
	case "literal":
		return literal(sv.V), nil
	case "tmpval":
		return tmpval([]byte(sv.V)), nil
	case "expr":
		var e expr
		for _, v := range sv.Children {
			dv, err := deserializeVar(v)
			if err != nil {
				return nil, err
			}
			e = append(e, dv)
		}
		return e, nil
	case "varref":
		dv, err := deserializeSingleChild(sv)
		if err != nil {
			return nil, err
		}
		return &varref{varname: dv, paren: sv.V[0]}, nil
	case "paramref":
		v, err := strconv.Atoi(sv.V)
		if err != nil {
			return nil, err
		}
		return paramref(v), nil
	case "varsubst":
		varname, err := deserializeVar(sv.Children[0])
		if err != nil {
			return nil, err
		}
		pat, err := deserializeVar(sv.Children[1])
		if err != nil {
			return nil, err
		}
		subst, err := deserializeVar(sv.Children[2])
		if err != nil {
			return nil, err
		}
		return varsubst{
			varname: varname,
			pat:     pat,
			subst:   subst,
			paren:   sv.V[0],
		}, nil

	case "func":
		dv, err := deserializeVar(sv.Children[0])
		if err != nil {
			return nil, err
		}
		name, ok := dv.(literal)
		if !ok {
			return nil, fmt.Errorf("func name is not literal %s: %T", dv, dv)
		}
		f := funcMap[string(name[1:])]()
		f.AddArg(name)
		for _, a := range sv.Children[1:] {
			dv, err := deserializeVar(a)
			if err != nil {
				return nil, err
			}
			f.AddArg(dv)
		}
		return f, nil
	case "funcEvalAssign":
		rhs, err := deserializeVar(sv.Children[2])
		if err != nil {
			return nil, err
		}
		return &funcEvalAssign{
			lhs: sv.Children[0].V,
			op:  sv.Children[1].V,
			rhs: rhs,
		}, nil
	case "funcNop":
		return &funcNop{expr: sv.V}, nil

	case "simple":
		return &simpleVar{
			value:  strings.Split(sv.V, " "),
			origin: sv.Origin,
		}, nil
	case "recursive":
		expr, err := deserializeSingleChild(sv)
		if err != nil {
			return nil, err
		}
		return &recursiveVar{
			expr:   expr,
			origin: sv.Origin,
		}, nil

	case ":=", "=", "+=", "?=":
		dv, err := deserializeSingleChild(sv)
		if err != nil {
			return nil, err
		}
		v, ok := dv.(Var)
		if !ok {
			return nil, fmt.Errorf("not var: target specific var %s %T", dv, dv)
		}
		return &targetSpecificVar{
			v:  v,
			op: sv.Type,
		}, nil

	default:
		return nil, fmt.Errorf("unknown serialized variable type: %q", sv)
	}
}

func deserializeVars(vars map[string]serializableVar) (Vars, error) {
	r := make(Vars)
	for k, v := range vars {
		dv, err := deserializeVar(v)
		if err != nil {
			return nil, err
		}
		vv, ok := dv.(Var)
		if !ok {
			return nil, fmt.Errorf("not var: %s: %T", dv, dv)
		}
		r[k] = vv
	}
	return r, nil
}

func deserializeNodes(g serializableGraph) (r []*DepNode, err error) {
	nodes := g.Nodes
	tsvs := g.Tsvs
	targets := g.Targets
	// Deserialize all TSVs first so that multiple rules can share memory.
	var tsvValues []Var
	for _, sv := range tsvs {
		dv, err := deserializeVar(sv.Value)
		if err != nil {
			return nil, err
		}
		vv, ok := dv.(Var)
		if !ok {
			return nil, fmt.Errorf("not var: %s %T", dv, dv)
		}
		tsvValues = append(tsvValues, vv)
	}

	nodeMap := make(map[string]*DepNode)
	for _, n := range nodes {
		var actualInputs []string
		for _, i := range n.ActualInputs {
			actualInputs = append(actualInputs, targets[i])
		}

		d := &DepNode{
			Output:             targets[n.Output],
			Cmds:               n.Cmds,
			HasRule:            n.HasRule,
			IsPhony:            n.IsPhony,
			ActualInputs:       actualInputs,
			Filename:           n.Filename,
			Lineno:             n.Lineno,
			TargetSpecificVars: make(Vars),
		}

		for _, id := range n.TargetSpecificVars {
			sv := tsvs[id]
			d.TargetSpecificVars[sv.Name] = tsvValues[id]
		}

		nodeMap[targets[n.Output]] = d
		r = append(r, d)
	}

	for _, n := range nodes {
		d := nodeMap[targets[n.Output]]
		for _, o := range n.Deps {
			c, present := nodeMap[targets[o]]
			if !present {
				return nil, fmt.Errorf("unknown target: %d (%s)", o, targets[o])
			}
			d.Deps = append(d.Deps, c)
		}
		for _, o := range n.OrderOnlys {
			c, present := nodeMap[targets[o]]
			if !present {
				return nil, fmt.Errorf("unknown target: %d (%s)", o, targets[o])
			}
			d.OrderOnlys = append(d.OrderOnlys, c)
		}
		for _, o := range n.Parents {
			c, present := nodeMap[targets[o]]
			if !present {
				return nil, fmt.Errorf("unknown target: %d (%s)", o, targets[o])
			}
			d.Parents = append(d.Parents, c)
		}
	}

	return r, nil
}

func human(n int) string {
	if n >= 10*1000*1000*1000 {
		return fmt.Sprintf("%.2fGB", float32(n)/1000/1000/1000)
	}
	if n >= 10*1000*1000 {
		return fmt.Sprintf("%.2fMB", float32(n)/1000/1000)
	}
	if n >= 10*1000 {
		return fmt.Sprintf("%.2fkB", float32(n)/1000)
	}
	return fmt.Sprintf("%dB", n)
}

func showSerializedNodesStats(nodes []*serializableDepNode) {
	outputSize := 0
	cmdSize := 0
	depsSize := 0
	orderOnlysSize := 0
	actualInputSize := 0
	tsvSize := 0
	filenameSize := 0
	linenoSize := 0
	for _, n := range nodes {
		outputSize += 4
		for _, c := range n.Cmds {
			cmdSize += len(c)
		}
		depsSize += 4 * len(n.Deps)
		orderOnlysSize += 4 * len(n.OrderOnlys)
		actualInputSize += 4 * len(n.ActualInputs)
		tsvSize += 4 * len(n.TargetSpecificVars)
		filenameSize += len(n.Filename)
		linenoSize += 4
	}
	size := outputSize + cmdSize + depsSize + orderOnlysSize + actualInputSize + tsvSize + filenameSize + linenoSize
	logStats("%d nodes %s", len(nodes), human(size))
	logStats(" output %s", human(outputSize))
	logStats(" command %s", human(cmdSize))
	logStats(" deps %s", human(depsSize))
	logStats(" orderonlys %s", human(orderOnlysSize))
	logStats(" inputs %s", human(actualInputSize))
	logStats(" tsv %s", human(tsvSize))
	logStats(" filename %s", human(filenameSize))
	logStats(" lineno %s", human(linenoSize))
}

func (v serializableVar) size() int {
	size := 0
	size += len(v.Type)
	size += len(v.V)
	size += len(v.Origin)
	for _, c := range v.Children {
		size += c.size()
	}
	return size
}

func showSerializedVarsStats(vars map[string]serializableVar) {
	nameSize := 0
	valueSize := 0
	for k, v := range vars {
		nameSize += len(k)
		valueSize += v.size()
	}
	size := nameSize + valueSize
	logStats("%d vars %s", len(vars), human(size))
	logStats(" name %s", human(nameSize))
	logStats(" value %s", human(valueSize))
}

func showSerializedTsvsStats(vars []serializableTargetSpecificVar) {
	nameSize := 0
	valueSize := 0
	for _, v := range vars {
		nameSize += len(v.Name)
		valueSize += v.Value.size()
	}
	size := nameSize + valueSize
	logStats("%d tsvs %s", len(vars), human(size))
	logStats(" name %s", human(nameSize))
	logStats(" value %s", human(valueSize))
}

func showSerializedTargetsStats(targets []string) {
	size := 0
	for _, t := range targets {
		size += len(t)
	}
	logStats("%d targets %s", len(targets), human(size))
}

func showSerializedAccessedMksStats(accessedMks []*accessedMakefile) {
	size := 0
	for _, rm := range accessedMks {
		size += len(rm.Filename) + len(rm.Hash) + 4
	}
	logStats("%d makefiles %s", len(accessedMks), human(size))
}

func showSerializedGraphStats(g serializableGraph) {
	showSerializedNodesStats(g.Nodes)
	showSerializedVarsStats(g.Vars)
	showSerializedTsvsStats(g.Tsvs)
	showSerializedTargetsStats(g.Targets)
	showSerializedAccessedMksStats(g.AccessedMks)
}

func deserializeGraph(g serializableGraph) (*DepGraph, error) {
	if StatsFlag {
		showSerializedGraphStats(g)
	}
	nodes, err := deserializeNodes(g)
	if err != nil {
		return nil, err
	}
	vars, err := deserializeVars(g.Vars)
	if err != nil {
		return nil, err
	}
	return &DepGraph{
		nodes:       nodes,
		vars:        vars,
		accessedMks: g.AccessedMks,
		exports:     g.Exports,
	}, nil
}

func (jsonLoadSaver) Load(filename string) (*DepGraph, error) {
	startTime := time.Now()
	f, err := os.Open(filename)
	if err != nil {
		return nil, err
	}
	defer f.Close()

	d := json.NewDecoder(f)
	g := serializableGraph{Vars: make(map[string]serializableVar)}
	err = d.Decode(&g)
	if err != nil {
		return nil, err
	}
	dg, err := deserializeGraph(g)
	if err != nil {
		return nil, err
	}
	logStats("gob deserialize time: %q", time.Since(startTime))
	return dg, nil
}

func (gobLoadSaver) Load(filename string) (*DepGraph, error) {
	startTime := time.Now()
	f, err := os.Open(filename)
	if err != nil {
		return nil, err
	}
	defer f.Close()

	d := gob.NewDecoder(f)
	g := serializableGraph{Vars: make(map[string]serializableVar)}
	err = d.Decode(&g)
	if err != nil {
		return nil, err
	}
	dg, err := deserializeGraph(g)
	if err != nil {
		return nil, err
	}
	logStats("json deserialize time: %q", time.Since(startTime))
	return dg, nil
}

func loadCache(makefile string, roots []string) (*DepGraph, error) {
	startTime := time.Now()
	defer func() {
		logStats("Cache lookup time: %q", time.Since(startTime))
	}()

	filename := cacheFilename(makefile, roots)
	if !exists(filename) {
		glog.Warningf("Cache not found %q", filename)
		return nil, fmt.Errorf("cache not found: %s", filename)
	}

	g, err := GOB.Load(filename)
	if err != nil {
		glog.Warning("Cache load error %q: %v", filename, err)
		return nil, err
	}
	for _, mk := range g.accessedMks {
		if mk.State != fileExists && mk.State != fileNotExists {
			return nil, fmt.Errorf("internal error: broken state: %d", mk.State)
		}
		if mk.State == fileNotExists {
			if exists(mk.Filename) {
				glog.Infof("Cache expired: %s", mk.Filename)
				return nil, fmt.Errorf("cache expired: %s", mk.Filename)
			}
		} else {
			c, err := ioutil.ReadFile(mk.Filename)
			if err != nil {
				glog.Infof("Cache expired: %s", mk.Filename)
				return nil, fmt.Errorf("cache expired: %s", mk.Filename)
			}
			h := sha1.Sum(c)
			if !bytes.Equal(h[:], mk.Hash[:]) {
				glog.Infof("Cache expired: %s", mk.Filename)
				return nil, fmt.Errorf("cache expired: %s", mk.Filename)
			}
		}
	}
	glog.Info("Cache found in %q", filename)
	return g, nil
}