Repository: VKCOM/noverify
Pull request #680 (2020-08-14 10:56:10)

all: add basic constant folding
constfold package can fold some simple expressions
into meta.ConstantValue.

Currently, we only use that for named constant values
definitions and IR normalization, but it can be used
in other contexts as well.

Signed-off-by: Iskander Sharipov <quasilyte@gmail.com>


Patch:
diff --git a/src/cmd/php-guru/dupcode/fileindexer.go b/src/cmd/php-guru/dupcode/fileindexer.go
index d65dc3c..39cee8d 100644
--- a/src/cmd/php-guru/dupcode/fileindexer.go
+++ b/src/cmd/php-guru/dupcode/fileindexer.go
@@ -3,9 +3,11 @@ package dupcode
 import (
 	"github.com/VKCOM/noverify/src/ir"
 	"github.com/VKCOM/noverify/src/ir/normalize"
+	"github.com/VKCOM/noverify/src/meta"
 )
 
 type fileIndexer struct {
+	st           *meta.ClassParseState
 	funcs        funcSet
 	fileContents []byte
 	filename     string
@@ -69,10 +71,12 @@ func (indexer *fileIndexer) walkFunc(n *ir.FunctionStmt) {
 
 func (indexer *fileIndexer) collectFunc(n ir.Node, className, funcName string, params, stmts []ir.Node) {
 	if indexer.normLevel != normNone {
+		// TODO: indexer.st needs to have a proper CurrentClass.
+		// We can't use className param here as it won't be FQN.
 		conf := normalize.Config{
 			NormalizeMore: indexer.normLevel > normSafe,
 		}
-		stmts = normalize.FuncBody(conf, params, stmts)
+		stmts = normalize.FuncBody(indexer.st, conf, params, stmts)
 	}
 
 	pos := ir.GetPosition(n)
diff --git a/src/cmd/php-guru/dupcode/main.go b/src/cmd/php-guru/dupcode/main.go
index ca1d825..872859d 100644
--- a/src/cmd/php-guru/dupcode/main.go
+++ b/src/cmd/php-guru/dupcode/main.go
@@ -12,6 +12,7 @@ import (
 	"github.com/VKCOM/noverify/src/cmd"
 	"github.com/VKCOM/noverify/src/cmd/php-guru/guru"
 	"github.com/VKCOM/noverify/src/ir/irconv"
+	"github.com/VKCOM/noverify/src/meta"
 	"github.com/VKCOM/noverify/src/php/parseutil"
 	"github.com/VKCOM/noverify/src/workspace"
 )
@@ -110,6 +111,7 @@ func Main(ctx *guru.Context) (int, error) {
 				rootIR := irconv.ConvertRoot(root)
 
 				indexer := &fileIndexer{
+					st:           &meta.ClassParseState{},
 					funcs:        workerResult,
 					fileContents: data,
 					filename:     f.Filename,
diff --git a/src/constfold/binary_op.go b/src/constfold/binary_op.go
new file mode 100644
index 0000000..490bc1d
--- /dev/null
+++ b/src/constfold/binary_op.go
@@ -0,0 +1,39 @@
+package constfold
+
+import (
+	"github.com/VKCOM/noverify/src/meta"
+)
+
+// Plus performs arithmetic "+".
+func Plus(x, y meta.ConstantValue) meta.ConstantValue {
+	switch x.Type {
+	case meta.Integer:
+		if y.Type == meta.Integer {
+			v := x.Value.(int64) + y.Value.(int64)
+			return meta.ConstantValue{Type: meta.Integer, Value: v}
+		}
+	case meta.Float:
+		if y.Type == meta.Float {
+			v := x.Value.(float64) + y.Value.(float64)
+			return meta.ConstantValue{Type: meta.Float, Value: v}
+		}
+	}
+	return meta.UnknownValue
+}
+
+// Mul performs arithmetic "*".
+func Mul(x, y meta.ConstantValue) meta.ConstantValue {
+	switch x.Type {
+	case meta.Integer:
+		if y.Type == meta.Integer {
+			v := x.Value.(int64) * y.Value.(int64)
+			return meta.ConstantValue{Type: meta.Integer, Value: v}
+		}
+	case meta.Float:
+		if y.Type == meta.Float {
+			v := x.Value.(float64) * y.Value.(float64)
+			return meta.ConstantValue{Type: meta.Float, Value: v}
+		}
+	}
+	return meta.UnknownValue
+}
diff --git a/src/constfold/eval.go b/src/constfold/eval.go
new file mode 100644
index 0000000..21e6e05
--- /dev/null
+++ b/src/constfold/eval.go
@@ -0,0 +1,59 @@
+package constfold
+
+import (
+	"strconv"
+
+	"github.com/VKCOM/noverify/src/ir"
+	"github.com/VKCOM/noverify/src/ir/irutil"
+	"github.com/VKCOM/noverify/src/meta"
+	"github.com/VKCOM/noverify/src/solver"
+)
+
+// Eval tries to compute the e using the constant expressions folding.
+// In case of failure, meta.UnknownValue is returned.
+func Eval(st *meta.ClassParseState, e ir.Node) meta.ConstantValue {
+	// TODO: support more operators and some builtin PHP functions like strlen.
+
+	switch e := e.(type) {
+	case *ir.ParenExpr:
+		return Eval(st, e.Expr)
+
+	case *ir.ConstFetchExpr:
+		if !meta.IsIndexingComplete() {
+			return meta.UnknownValue
+		}
+		_, info, ok := solver.GetConstant(st, e.Constant)
+		if !ok {
+			return meta.UnknownValue
+		}
+		return info.Value
+
+	case *ir.UnaryMinusExpr:
+		return Neg(Eval(st, e.Expr))
+
+	case *ir.PlusExpr:
+		return Plus(Eval(st, e.Left), Eval(st, e.Right))
+	case *ir.MulExpr:
+		return Mul(Eval(st, e.Left), Eval(st, e.Right))
+
+	case *ir.Lnumber:
+		value, err := strconv.ParseInt(e.Value, 10, 64)
+		if err != nil {
+			return meta.UnknownValue
+		}
+		return meta.ConstantValue{Type: meta.Integer, Value: value}
+
+	case *ir.Dnumber:
+		value, err := strconv.ParseFloat(e.Value, 64)
+		if err != nil {
+			return meta.UnknownValue
+		}
+		return meta.ConstantValue{Type: meta.Float, Value: value}
+
+	case *ir.String:
+		v := irutil.Unquote(e.Value)
+		return meta.ConstantValue{Value: v, Type: meta.String}
+	}
+
+	return meta.UnknownValue
+}
diff --git a/src/constfold/unary_op.go b/src/constfold/unary_op.go
new file mode 100644
index 0000000..95548c8
--- /dev/null
+++ b/src/constfold/unary_op.go
@@ -0,0 +1,15 @@
+package constfold
+
+import (
+	"github.com/VKCOM/noverify/src/meta"
+)
+
+func Neg(x meta.ConstantValue) meta.ConstantValue {
+	switch x.Type {
+	case meta.Integer:
+		return meta.ConstantValue{Type: meta.Integer, Value: -x.Value.(int64)}
+	case meta.Float:
+		return meta.ConstantValue{Type: meta.Float, Value: -x.Value.(float64)}
+	}
+	return meta.UnknownValue
+}
diff --git a/src/ir/normalize/normalize.go b/src/ir/normalize/normalize.go
index 895cdd6..b530162 100644
--- a/src/ir/normalize/normalize.go
+++ b/src/ir/normalize/normalize.go
@@ -5,24 +5,22 @@ import (
 	"sort"
 	"strings"
 
+	"github.com/VKCOM/noverify/src/constfold"
 	"github.com/VKCOM/noverify/src/ir"
 	"github.com/VKCOM/noverify/src/ir/irfmt"
 	"github.com/VKCOM/noverify/src/ir/irutil"
 	"github.com/VKCOM/noverify/src/meta"
-	"github.com/VKCOM/noverify/src/solver"
 )
 
 type Config struct {
-	CurrentClass string
-	Namespace    string
-
 	NormalizeMore bool
 }
 
-func FuncBody(conf Config, params, statements []ir.Node) []ir.Node {
+func FuncBody(st *meta.ClassParseState, conf Config, params, statements []ir.Node) []ir.Node {
 	norm := normalizer{
 		out:     irutil.NodeSliceClone(statements),
 		conf:    conf,
+		st:      st,
 		globals: make(map[string]struct{}),
 	}
 
@@ -38,6 +36,7 @@ func FuncBody(conf Config, params, statements []ir.Node) []ir.Node {
 
 type normalizer struct {
 	conf     Config
+	st       *meta.ClassParseState
 	out      []ir.Node
 	varNames map[string]int
 	globals  map[string]struct{}
@@ -247,10 +246,17 @@ func (norm *normalizer) normalizedStmtExpr(e ir.Node) ir.Node {
 }
 
 func (norm *normalizer) normalizedExpr(e ir.Node) ir.Node {
+	constFolded := constfold.Eval(norm.st, e)
+	if constFolded.Type != meta.Undefined {
+		if e2 := constToIR(constFolded); e2 != nil {
+			return e2
+		}
+	}
+
 	switch e := e.(type) {
 	case *ir.Name:
 		if e.Value == "self" {
-			return &ir.Name{Value: norm.conf.CurrentClass}
+			return &ir.Name{Value: norm.st.CurrentClass}
 		}
 
 	case *ir.NewExpr:
@@ -332,23 +338,6 @@ func (norm *normalizer) normalizedExpr(e ir.Node) ir.Node {
 				e.Constant = &ir.Name{Value: `false`}
 			}
 		}
-		// Named const => its value
-		if !meta.IsIndexingComplete() {
-			return e
-		}
-		info, ok := norm.getConstant(e.Constant)
-		if !ok {
-			return e
-		}
-		value := info.Value.Value
-		switch info.Value.Type {
-		case meta.Integer:
-			return &ir.Lnumber{Value: fmt.Sprint(value)}
-		case meta.String:
-			return &ir.String{Value: value.(string)}
-		default:
-			return e
-		}
 
 	case *ir.FunctionCallExpr:
 		funcName, ok := e.Function.(*ir.Name)
@@ -438,13 +427,6 @@ func (norm *normalizer) renameVar(v *ir.SimpleVar) {
 	v.Name = fmt.Sprintf("v%d", id)
 }
 
-func (norm *normalizer) getConstant(n ir.Node) (meta.ConstantInfo, bool) {
-	var cs meta.ClassParseState
-	cs.Namespace = norm.conf.Namespace
-	_, info, ok := solver.GetConstant(&cs, n)
-	return info, ok
-}
-
 var (
 	nullConstNode   = &ir.ConstFetchExpr{Constant: &ir.Name{Value: "null"}}
 	emptyStringNode = &ir.String{}
@@ -492,3 +474,15 @@ func encapsedPartToConcatArg(n ir.Node) ir.Node {
 		return n
 	}
 }
+
+func constToIR(v meta.ConstantValue) ir.Node {
+	value := v.Value
+	switch v.Type {
+	case meta.Integer:
+		return &ir.Lnumber{Value: fmt.Sprint(value)}
+	case meta.String:
+		return &ir.String{Value: value.(string)}
+	default:
+		return nil
+	}
+}
diff --git a/src/linter/cache.go b/src/linter/cache.go
index 4bcae4a..9ff34a8 100644
--- a/src/linter/cache.go
+++ b/src/linter/cache.go
@@ -39,7 +39,8 @@ import (
 //          added mapPrecise flag to mark precise type maps.
 //     39 - added new field Value in ConstantInfo
 //     40 - changed string const value storage (no quotes)
-const cacheVersion = 40
+//     41 - const-folding affected const definition values
+const cacheVersion = 41
 
 var (
 	errWrongVersion = errors.New("Wrong cache version")
diff --git a/src/linter/root.go b/src/linter/root.go
index 6926ce0..75d889d 100644
--- a/src/linter/root.go
+++ b/src/linter/root.go
@@ -10,6 +10,7 @@ import (
 	"strings"
 
 	"github.com/VKCOM/noverify/src/baseline"
+	"github.com/VKCOM/noverify/src/constfold"
 	"github.com/VKCOM/noverify/src/git"
 	"github.com/VKCOM/noverify/src/ir"
 	"github.com/VKCOM/noverify/src/ir/irutil"
@@ -930,7 +931,7 @@ func (d *RootWalker) enterClassConstList(s *ir.ClassConstListStmt) bool {
 		d.checkCommentMisspellings(c, c.PhpDocComment)
 		typ := solver.ExprTypeLocal(d.scope(), d.ctx.st, c.Expr)
 
-		value, _ := solver.GetConstantValue(c)
+		value := constfold.Eval(d.ctx.st, c.Expr)
 
 		// TODO: handle duplicate constant
 		cl.Constants[nm] = meta.ConstantInfo{
@@ -1646,7 +1647,7 @@ func (d *RootWalker) enterConstList(lst *ir.ConstListStmt) bool {
 	for _, sNode := range lst.Consts {
 		s := sNode.(*ir.ConstantStmt)
 
-		value, _ := solver.GetConstantValue(s.Expr)
+		value := constfold.Eval(d.ctx.st, s.Expr)
 
 		id := s.ConstantName
 		nm := d.ctx.st.Namespace + `\` + id.Value
diff --git a/src/meta/const_value.go b/src/meta/const_value.go
index 6a61c81..54ce3f6 100644
--- a/src/meta/const_value.go
+++ b/src/meta/const_value.go
@@ -7,6 +7,9 @@ import (
 
 type ConstantValueType uint8
 
+// TODO: add bool const values?
+
+//go:generate stringer -type=ConstantValueType
 const (
 	Undefined ConstantValueType = iota
 	Integer
@@ -14,6 +17,8 @@ const (
 	String
 )
 
+var UnknownValue = ConstantValue{Type: Undefined}
+
 type ConstantValue struct {
 	Type  ConstantValueType
 	Value interface{}
@@ -82,7 +87,8 @@ func (c ConstantValue) String() string {
 	if c.Type == Undefined {
 		return "Undefined type"
 	}
-	return fmt.Sprintf("%d: %v", c.Type, c.Value)
+
+	return fmt.Sprintf("%s(%v)", c.Type, c.Value)
 }
 
 func (c ConstantValue) IsEqual(v ConstantValue) bool {
diff --git a/src/meta/constantvaluetype_string.go b/src/meta/constantvaluetype_string.go
new file mode 100644
index 0000000..d9fb5ef
--- /dev/null
+++ b/src/meta/constantvaluetype_string.go
@@ -0,0 +1,26 @@
+// Code generated by "stringer -type=ConstantValueType"; DO NOT EDIT.
+
+package meta
+
+import "strconv"
+
+func _() {
+	// An "invalid array index" compiler error signifies that the constant values have changed.
+	// Re-run the stringer command to generate them again.
+	var x [1]struct{}
+	_ = x[Undefined-0]
+	_ = x[Integer-1]
+	_ = x[Float-2]
+	_ = x[String-3]
+}
+
+const _ConstantValueType_name = "UndefinedIntegerFloatString"
+
+var _ConstantValueType_index = [...]uint8{0, 9, 16, 21, 27}
+
+func (i ConstantValueType) String() string {
+	if i >= ConstantValueType(len(_ConstantValueType_index)-1) {
+		return "ConstantValueType(" + strconv.FormatInt(int64(i), 10) + ")"
+	}
+	return _ConstantValueType_name[_ConstantValueType_index[i]:_ConstantValueType_index[i+1]]
+}
diff --git a/src/solver/const_value.go b/src/solver/const_value.go
deleted file mode 100644
index 2049cbd..0000000
--- a/src/solver/const_value.go
+++ /dev/null
@@ -1,41 +0,0 @@
-package solver
-
-import (
-	"strconv"
-
-	"github.com/VKCOM/noverify/src/ir"
-	"github.com/VKCOM/noverify/src/meta"
-)
-
-var undefinedValue = meta.ConstantValue{Type: meta.Undefined}
-
-func GetConstantValue(c ir.Node) (meta.ConstantValue, bool) {
-	switch c := c.(type) {
-	case *ir.Lnumber:
-		value, err := strconv.ParseInt(c.Value, 10, 64)
-		return meta.ConstantValue{Type: meta.Integer, Value: value}, err == nil
-
-	case *ir.Dnumber:
-		value, err := strconv.ParseFloat(c.Value, 64)
-		return meta.ConstantValue{Type: meta.Float, Value: value}, err == nil
-
-	case *ir.String:
-		return meta.ConstantValue{Value: c.Value, Type: meta.String}, true
-
-	case *ir.UnaryMinusExpr:
-		v, ok := GetConstantValue(c.Expr)
-		if !ok {
-			return undefinedValue, false
-		}
-		switch value := v.Value.(type) {
-		case int64:
-			return meta.ConstantValue{Type: meta.Integer, Value: -value}, true
-		case float64:
-			return meta.ConstantValue{Type: meta.Float, Value: -value}, true
-		}
-		return v, true
-
-	default:
-		return undefinedValue, false
-	}
-}


Test patch:
diff --git a/src/ir/normalize/normalize_test.go b/src/ir/normalize/normalize_test.go
index 4343152..2943618 100644
--- a/src/ir/normalize/normalize_test.go
+++ b/src/ir/normalize/normalize_test.go
@@ -73,7 +73,8 @@ func TestNormalizeStmtList(t *testing.T) {
 		},
 	}
 
-	conf := Config{CurrentClass: `Foo`}
+	conf := Config{}
+	st := &meta.ClassParseState{CurrentClass: `Foo`}
 	for _, test := range tests {
 
 		list, err := parseStmtList(test.orig)
@@ -81,7 +82,7 @@ func TestNormalizeStmtList(t *testing.T) {
 			t.Errorf("parse `%s`: %v", test.orig, err)
 			continue
 		}
-		normalized := FuncBody(conf, nil, list)
+		normalized := FuncBody(st, conf, nil, list)
 		have := strings.ReplaceAll(irfmt.Node(&ir.StmtList{Stmts: normalized}), "\n", "")
 		have = strings.ReplaceAll(have, "  ", " ")
 		want := `{ ` + test.want + `}`
@@ -101,7 +102,8 @@ type normalizationTest struct {
 func runNormalizeTests(t *testing.T, tests []normalizationTest) {
 	t.Helper()
 
-	conf := Config{CurrentClass: `Foo`}
+	conf := Config{}
+	st := &meta.ClassParseState{CurrentClass: `Foo`}
 	for _, test := range tests {
 		n, _, err := parseutil.ParseStmt([]byte(test.orig))
 		if err != nil {
@@ -109,7 +111,7 @@ func runNormalizeTests(t *testing.T, tests []normalizationTest) {
 			return
 		}
 		irNode := irconv.ConvertNode(n)
-		normalized := FuncBody(conf, nil, []ir.Node{irNode})
+		normalized := FuncBody(st, conf, nil, []ir.Node{irNode})
 		have := strings.TrimSuffix(irfmt.Node(normalized[0]), ";")
 		if have != test.want {
 			t.Errorf("normalize `%s`:\nhave: %s\nwant: %s",
@@ -122,7 +124,7 @@ func runNormalizeTests(t *testing.T, tests []normalizationTest) {
 			return
 		}
 		irNode2 := irconv.ConvertNode(n2)
-		normalized2 := FuncBody(conf, nil, []ir.Node{irNode2})
+		normalized2 := FuncBody(st, conf, nil, []ir.Node{irNode2})
 		have2 := strings.TrimSuffix(irfmt.Node(normalized2[0]), ";")
 		if have != have2 {
 			t.Errorf("second normalization of `%s`:\nhave: %s\nwant: %s",
@@ -166,6 +168,12 @@ func TestNormalizeExpr(t *testing.T) {
 
 		{`$x ? $x : $y`, `$v0 ?: $v1`},
 		{`f() ? f() : $y`, `f() ? f() : $v0`},
+
+		// Const-folded.
+		{`1 + 5`, `6`},
+		{`(1 + 5) + 1`, `7`},
+		{`1 + 2 * 4`, `9`},
+		{`(1 + 2) * 4`, `12`},
 	})
 }
 
diff --git a/src/linter/cache_test.go b/src/linter/cache_test.go
index 9703b22..ea9faea 100644
--- a/src/linter/cache_test.go
+++ b/src/linter/cache_test.go
@@ -30,6 +30,7 @@ func TestCache(t *testing.T) {
 const GLOBAL_CONST = 1;
 const FLOAT_CONST = 153.5;
 const NEGATIVE_INT_CONST = -43;
+const WITH_CONST_FOLD = 10 + 15;
 
 $globalIntVar = 10;
 $globalStringVar = 'string';
@@ -113,7 +114,7 @@ main();
 		//
 		// If cache encoding changes, there is a very high chance that
 		// encoded data lengh will change as well.
-		wantLen := 4296
+		wantLen := 4413
 		haveLen := buf.Len()
 		if haveLen != wantLen {
 			t.Errorf("cache len mismatch:\nhave: %d\nwant: %d", haveLen, wantLen)
@@ -122,7 +123,7 @@ main();
 		// 2. Check cache "strings" hash.
 		//
 		// It catches new fields in cached types, field renames and encoding of additional named attributes.
-		wantStrings := "10dbc28ec87d69246d9b65c17638491e5463ae05a589b11753df79ecbe6ce1f61810a4243a90cc53254c9cea280b22f9fd5b34ee468a299e258bdc2b878982b0"
+		wantStrings := "266ae111001785053b77fc003fe4566dcfb16e1d5674c08cb867c87531f2882a8c2157b2b737adb4da7f62d2e038e289ae2dd8ea92381607768c5e8ac4496744"
 		haveStrings := collectCacheStrings(buf.String())
 		if haveStrings != wantStrings {
 			t.Errorf("cache strings mismatch:\nhave: %q\nwant: %q", haveStrings, wantStrings)
diff --git a/src/tests/checkers/basic_test.go b/src/tests/checkers/basic_test.go
index d5d2e53..c3f9c99 100644
--- a/src/tests/checkers/basic_test.go
+++ b/src/tests/checkers/basic_test.go
@@ -1326,7 +1326,7 @@ func TestDuplicateArrayKeyWithConstants(t *testing.T) {
 	test := linttest.NewSuite(t)
 	test.AddFile(`<?php
 const MAX_VALUE = 1;
-const MIN_VALUE = 1;
+const MIN_VALUE = 0+1; // Const-folded to 1
 $a = [
   MAX_VALUE => 'something',
   MIN_VALUE => 'other_thing',
@@ -1345,7 +1345,6 @@ $c = [
   END_PERCENT => 45,
 ];
 
-
 const START_PERCENT_REVERT = -1;
 const END_PERCENT_REVERT = -1.51;