Revert "Revert "Initial implementation of bpfix""

Bug: 38351765
Test: bpfix Android.bp

This reverts commit a8cc9c53fa5eb7004bc07c5c0ca8613761afd49b.

Change-Id: I60f02a8dd920346aa17b9044f834ffe94fa693c6

4 files changed, 530 insertions, 0 deletions

diff --git a/bpfix/Android.bp b/bpfix/Android.bp
new file mode 100644
index 00000000..90a453d7
--- /dev/null
+++ b/bpfix/Android.bp
@@ -0,0 +1,43 @@
+// Copyright 2017 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.
+
+//
+// androidmk Android.mk to Blueprints translator
+//
+
+blueprint_go_binary {
+    name: "bpfix",
+    srcs: [
+        "cmd/bpfix.go",
+    ],
+    deps: [
+        "bpfix-lib",
+    ],
+}
+
+bootstrap_go_package {
+    name: "bpfix-lib",
+    pkgPath: "android/soong/bpfix/bpfix",
+    srcs: [
+        "bpfix/bpfix.go",
+    ],
+    testSrcs: [
+      "bpfix/bpfix_test.go",
+    ],
+    deps: [
+        "blueprint-parser",
+    ],
+}
+
+
diff --git a/bpfix/bpfix/bpfix.go b/bpfix/bpfix/bpfix.go
new file mode 100644
index 00000000..12494943
--- /dev/null
+++ b/bpfix/bpfix/bpfix.go
@@ -0,0 +1,185 @@
+// Copyright 2017 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.
+
+// This file implements the logic of bpfix and also provides a programmatic interface
+
+package bpfix
+
+import (
+	"bytes"
+	"fmt"
+	"github.com/google/blueprint/parser"
+)
+
+// A FixRequest specifies the details of which fixes to apply to an individual file
+// A FixRequest doesn't specify whether to do a dry run or where to write the results; that's in cmd/bpfix.go
+type FixRequest struct {
+	simplifyKnownRedundantVariables bool
+	removeEmptyLists                bool
+}
+
+func NewFixRequest() FixRequest {
+	return FixRequest{}
+}
+
+func (r FixRequest) AddAll() (result FixRequest) {
+	result = r
+	result.simplifyKnownRedundantVariables = true
+	result.removeEmptyLists = true
+	return result
+}
+
+// FixTree repeatedly applies the fixes listed in the given FixRequest to the given File
+// until there is no fix that affects the tree
+func FixTree(tree *parser.File, config FixRequest) (fixed *parser.File, err error) {
+	prevIdentifier, err := fingerprint(tree)
+	if err != nil {
+		return nil, err
+	}
+
+	fixed = tree
+	maxNumIterations := 20
+	i := 0
+	for {
+		fixed, err = fixTreeOnce(fixed, config)
+		newIdentifier, err := fingerprint(tree)
+		if err != nil {
+			return nil, err
+		}
+		if bytes.Equal(newIdentifier, prevIdentifier) {
+			break
+		}
+		prevIdentifier = newIdentifier
+		// any errors from a previous iteration generally get thrown away and overwritten by errors on the next iteration
+
+		// detect infinite loop
+		i++
+		if i >= maxNumIterations {
+			return nil, fmt.Errorf("Applied fixes %s times and yet the tree continued to change. Is there an infinite loop?", i)
+			break
+		}
+	}
+	return fixed, err
+}
+
+// returns a unique identifier for the given tree that can be used to determine whether the tree changed
+func fingerprint(tree *parser.File) (fingerprint []byte, err error) {
+	bytes, err := parser.Print(tree)
+	if err != nil {
+		return nil, err
+	}
+	return bytes, nil
+}
+
+func fixTreeOnce(tree *parser.File, config FixRequest) (fixed *parser.File, err error) {
+	if config.simplifyKnownRedundantVariables {
+		tree, err = simplifyKnownPropertiesDuplicatingEachOther(tree)
+		if err != nil {
+			return nil, err
+		}
+	}
+	if config.removeEmptyLists {
+		tree, err = removePropertiesHavingTheirDefaultValues(tree)
+		if err != nil {
+			return nil, err
+		}
+	}
+	return tree, err
+}
+
+func simplifyKnownPropertiesDuplicatingEachOther(tree *parser.File) (fixed *parser.File, err error) {
+	// remove from local_include_dirs anything in export_include_dirs
+	fixed, err = removeMatchingModuleListProperties(tree, "export_include_dirs", "local_include_dirs")
+	return fixed, err
+}
+
+// removes from <items> every item present in <removals>
+func filterExpressionList(items *parser.List, removals *parser.List) {
+	writeIndex := 0
+	for _, item := range items.Values {
+		included := true
+		for _, removal := range removals.Values {
+			equal, err := parser.ExpressionsAreSame(item, removal)
+			if err != nil {
+				continue
+			}
+			if equal {
+				included = false
+				break
+			}
+		}
+		if included {
+			items.Values[writeIndex] = item
+			writeIndex++
+		}
+	}
+	items.Values = items.Values[:writeIndex]
+}
+
+// Remove each modules[i].Properties[<legacyName>][j] that matches a modules[i].Properties[<canonicalName>][k]
+func removeMatchingModuleListProperties(tree *parser.File, canonicalName string, legacyName string) (fixed *parser.File, err error) {
+	for _, def := range tree.Defs {
+		mod, ok := def.(*parser.Module)
+		if !ok {
+			continue
+		}
+		legacy, ok := mod.GetProperty(legacyName)
+		if !ok {
+			continue
+		}
+		legacyList, ok := legacy.Value.(*parser.List)
+		if !ok {
+			continue
+		}
+		canonical, ok := mod.GetProperty(canonicalName)
+		if !ok {
+			continue
+		}
+		canonicalList, ok := canonical.Value.(*parser.List)
+		if !ok {
+			continue
+		}
+		filterExpressionList(legacyList, canonicalList)
+	}
+	return tree, nil
+}
+
+func removePropertiesHavingTheirDefaultValues(tree *parser.File) (fixed *parser.File, err error) {
+	for _, def := range tree.Defs {
+		mod, ok := def.(*parser.Module)
+		if !ok {
+			continue
+		}
+		writeIndex := 0
+		for _, prop := range mod.Properties {
+			val := prop.Value
+			keep := true
+			switch val := val.(type) {
+			case *parser.List:
+				if len(val.Values) == 0 {
+					keep = false
+				}
+				break
+			default:
+				keep = true
+			}
+			if keep {
+				mod.Properties[writeIndex] = prop
+				writeIndex++
+			}
+		}
+		mod.Properties = mod.Properties[:writeIndex]
+	}
+	return tree, nil
+}
diff --git a/bpfix/bpfix/bpfix_test.go b/bpfix/bpfix/bpfix_test.go
new file mode 100644
index 00000000..06ae1399
--- /dev/null
+++ b/bpfix/bpfix/bpfix_test.go
@@ -0,0 +1,114 @@
+// Copyright 2017 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.
+
+// This file implements the logic of bpfix and also provides a programmatic interface
+
+package bpfix
+
+import (
+	"fmt"
+	"strings"
+	"testing"
+
+	"github.com/google/blueprint/parser"
+	"reflect"
+)
+
+// TODO(jeffrygaston) remove this when position is removed from ParseNode (in b/38325146) and we can directly do reflect.DeepEqual
+func printListOfStrings(items []string) (text string) {
+	if len(items) == 0 {
+		return "[]"
+	}
+	return fmt.Sprintf("[\"%s\"]", strings.Join(items, "\", \""))
+
+}
+
+func buildTree(local_include_dirs []string, export_include_dirs []string) (file *parser.File, errs []error) {
+	// TODO(jeffrygaston) use the builder class when b/38325146 is done
+	input := fmt.Sprintf(`cc_library_shared {
+	    name: "iAmAModule",
+	    local_include_dirs: %s,
+	    export_include_dirs: %s,
+	}
+	`,
+		printListOfStrings(local_include_dirs), printListOfStrings(export_include_dirs))
+	tree, errs := parser.Parse("", strings.NewReader(input), parser.NewScope(nil))
+	if len(errs) > 0 {
+		errs = append([]error{fmt.Errorf("failed to parse:\n%s", input)}, errs...)
+	}
+	return tree, errs
+}
+
+func implFilterListTest(t *testing.T, local_include_dirs []string, export_include_dirs []string, expectedResult []string) {
+	// build tree
+	tree, errs := buildTree(local_include_dirs, export_include_dirs)
+	if len(errs) > 0 {
+		t.Error("failed to build tree")
+		for _, err := range errs {
+			t.Error(err)
+		}
+		t.Fatalf("%d parse errors", len(errs))
+	}
+
+	// apply simplifications
+	tree, err := simplifyKnownPropertiesDuplicatingEachOther(tree)
+	if len(errs) > 0 {
+		t.Fatal(err)
+	}
+
+	// lookup legacy property
+	mod := tree.Defs[0].(*parser.Module)
+	_, found := mod.GetProperty("local_include_dirs")
+	if !found {
+		t.Fatalf("failed to include key local_include_dirs in parse tree")
+	}
+
+	// check that the value for the legacy property was updated to the correct value
+	errorHeader := fmt.Sprintf("\nFailed to correctly simplify key 'local_include_dirs' in the presence of 'export_include_dirs.'\n"+
+		"original local_include_dirs: %q\n"+
+		"original export_include_dirs: %q\n"+
+		"expected result: %q\n"+
+		"actual result: ",
+		local_include_dirs, export_include_dirs, expectedResult)
+	result, ok := mod.GetProperty("local_include_dirs")
+	if !ok {
+		t.Fatal(errorHeader + "property not found")
+	}
+
+	listResult, ok := result.Value.(*parser.List)
+	if !ok {
+		t.Fatalf("%sproperty is not a list: %v", errorHeader, listResult)
+	}
+
+	actualExpressions := listResult.Values
+	actualValues := make([]string, 0)
+	for _, expr := range actualExpressions {
+		str := expr.(*parser.String)
+		actualValues = append(actualValues, str.Value)
+	}
+
+	if !reflect.DeepEqual(actualValues, expectedResult) {
+		t.Fatalf("%s%q\nlists are different", errorHeader, actualValues)
+	}
+}
+
+func TestSimplifyKnownVariablesDuplicatingEachOther(t *testing.T) {
+	// TODO use []Expression{} once buildTree above can support it (which is after b/38325146 is done)
+	implFilterListTest(t, []string{"include"}, []string{"include"}, []string{})
+	implFilterListTest(t, []string{"include1"}, []string{"include2"}, []string{"include1"})
+	implFilterListTest(t, []string{"include1", "include2", "include3", "include4"}, []string{"include2"},
+		[]string{"include1", "include3", "include4"})
+	implFilterListTest(t, []string{}, []string{"include"}, []string{})
+	implFilterListTest(t, []string{}, []string{}, []string{})
+}
diff --git a/bpfix/cmd/bpfix.go b/bpfix/cmd/bpfix.go
new file mode 100644
index 00000000..f51c6f71
--- /dev/null
+++ b/bpfix/cmd/bpfix.go
@@ -0,0 +1,188 @@
+// Copyright 2017 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.
+
+// This file provides a command-line interface to bpfix
+
+// TODO(jeffrygaston) should this file be consolidated with bpfmt.go?
+
+package main
+
+import (
+	"bytes"
+	"flag"
+	"fmt"
+	"io"
+	"io/ioutil"
+	"os"
+	"os/exec"
+	"path/filepath"
+
+	"github.com/google/blueprint/parser"
+
+	"android/soong/bpfix/bpfix"
+)
+
+var (
+	// main operation modes
+	list   = flag.Bool("l", false, "list files whose formatting differs from bpfmt's")
+	write  = flag.Bool("w", false, "write result to (source) file instead of stdout")
+	doDiff = flag.Bool("d", false, "display diffs instead of rewriting files")
+)
+
+var (
+	exitCode = 0
+)
+
+func report(err error) {
+	fmt.Fprintln(os.Stderr, err)
+	exitCode = 2
+}
+
+func openAndProcess(filename string, out io.Writer, fixRequest bpfix.FixRequest) error {
+	f, err := os.Open(filename)
+	if err != nil {
+		return err
+	}
+	defer f.Close()
+	return processFile(filename, f, out, fixRequest)
+}
+
+// If in == nil, the source is the contents of the file with the given filename.
+func processFile(filename string, in io.Reader, out io.Writer, fixRequest bpfix.FixRequest) error {
+	// load the input file
+	src, err := ioutil.ReadAll(in)
+	if err != nil {
+		return err
+	}
+	r := bytes.NewBuffer(src)
+	file, errs := parser.Parse(filename, r, parser.NewScope(nil))
+	if len(errs) > 0 {
+		for _, err := range errs {
+			fmt.Fprintln(os.Stderr, err)
+		}
+		return fmt.Errorf("%d parsing errors", len(errs))
+	}
+
+	// compute and apply any requested fixes
+	fixed, err := bpfix.FixTree(file, fixRequest)
+	if err != nil {
+		return err
+	}
+
+	// output the results
+	res, err := parser.Print(fixed)
+	if err != nil {
+		return err
+	}
+	if !bytes.Equal(src, res) {
+		// contents have changed
+		if *list {
+			fmt.Fprintln(out, filename)
+		}
+		if *write {
+			err = ioutil.WriteFile(filename, res, 0644)
+			if err != nil {
+				return err
+			}
+		}
+		if *doDiff {
+			data, err := diff(src, res)
+			if err != nil {
+				return fmt.Errorf("computing diff: %s", err)
+			}
+			fmt.Printf("diff %s bpfix/%s\n", filename, filename)
+			out.Write(data)
+		}
+	}
+	if !*list && !*write && !*doDiff {
+		_, err = out.Write(res)
+	}
+	return err
+}
+
+func makeFileVisitor(fixRequest bpfix.FixRequest) func(string, os.FileInfo, error) error {
+	return func(path string, f os.FileInfo, err error) error {
+		if err == nil && (f.Name() == "Blueprints" || f.Name() == "Android.bp") {
+			err = openAndProcess(path, os.Stdout, fixRequest)
+		}
+		if err != nil {
+			report(err)
+		}
+		return nil
+	}
+}
+
+func walkDir(path string, fixRequest bpfix.FixRequest) {
+	filepath.Walk(path, makeFileVisitor(fixRequest))
+}
+
+func main() {
+	flag.Parse()
+
+	fixRequest := bpfix.NewFixRequest().AddAll()
+
+	if flag.NArg() == 0 {
+		if *write {
+			fmt.Fprintln(os.Stderr, "error: cannot use -w with standard input")
+			exitCode = 2
+			return
+		}
+		if err := processFile("<standard input>", os.Stdin, os.Stdout, fixRequest); err != nil {
+			report(err)
+		}
+		return
+	}
+
+	for i := 0; i < flag.NArg(); i++ {
+		path := flag.Arg(i)
+		switch dir, err := os.Stat(path); {
+		case err != nil:
+			report(err)
+		case dir.IsDir():
+			walkDir(path, fixRequest)
+		default:
+			if err := openAndProcess(path, os.Stdout, fixRequest); err != nil {
+				report(err)
+			}
+		}
+	}
+}
+
+func diff(b1, b2 []byte) (data []byte, err error) {
+	f1, err := ioutil.TempFile("", "bpfix")
+	if err != nil {
+		return
+	}
+	defer os.Remove(f1.Name())
+	defer f1.Close()
+
+	f2, err := ioutil.TempFile("", "bpfix")
+	if err != nil {
+		return
+	}
+	defer os.Remove(f2.Name())
+	defer f2.Close()
+
+	f1.Write(b1)
+	f2.Write(b2)
+
+	data, err = exec.Command("diff", "-u", f1.Name(), f2.Name()).CombinedOutput()
+	if len(data) > 0 {
+		// diff exits with a non-zero status when the files don't match.
+		// Ignore that failure as long as we get output.
+		err = nil
+	}
+	return
+
+}