Merge "Merge remote-tracking branch 'aosp/upstream' into master" into pi-dev
diff --git a/Blueprints b/Blueprints
index c892b46..93357fa 100644
--- a/Blueprints
+++ b/Blueprints
@@ -43,6 +43,7 @@
"parser/sort.go",
],
testSrcs: [
+ "parser/modify_test.go",
"parser/parser_test.go",
"parser/printer_test.go",
],
diff --git a/context.go b/context.go
index f131024..f96306b 100644
--- a/context.go
+++ b/context.go
@@ -1608,6 +1608,24 @@
visit(modules []*moduleInfo, visit func(*moduleInfo) bool)
}
+type unorderedVisitorImpl struct{}
+
+func (unorderedVisitorImpl) waitCount(module *moduleInfo) int {
+ return 0
+}
+
+func (unorderedVisitorImpl) propagate(module *moduleInfo) []*moduleInfo {
+ return nil
+}
+
+func (unorderedVisitorImpl) visit(modules []*moduleInfo, visit func(*moduleInfo) bool) {
+ for _, module := range modules {
+ if visit(module) {
+ return
+ }
+ }
+}
+
type bottomUpVisitorImpl struct{}
func (bottomUpVisitorImpl) waitCount(module *moduleInfo) int {
@@ -1657,20 +1675,26 @@
cancelCh := make(chan bool)
count := 0
cancel := false
+ var backlog []*moduleInfo
+ const limit = 1000
for _, module := range c.modulesSorted {
module.waitingCount = order.waitCount(module)
}
visitOne := func(module *moduleInfo) {
- count++
- go func() {
- ret := visit(module)
- if ret {
- cancelCh <- true
- }
- doneCh <- module
- }()
+ if count < limit {
+ count++
+ go func() {
+ ret := visit(module)
+ if ret {
+ cancelCh <- true
+ }
+ doneCh <- module
+ }()
+ } else {
+ backlog = append(backlog, module)
+ }
}
for _, module := range c.modulesSorted {
@@ -1679,11 +1703,19 @@
}
}
- for count > 0 {
+ for count > 0 || len(backlog) > 0 {
select {
- case cancel = <-cancelCh:
+ case <-cancelCh:
+ cancel = true
+ backlog = nil
case doneModule := <-doneCh:
+ count--
if !cancel {
+ for count < limit && len(backlog) > 0 {
+ toVisit := backlog[0]
+ backlog = backlog[1:]
+ visitOne(toVisit)
+ }
for _, module := range order.propagate(doneModule) {
module.waitingCount--
if module.waitingCount == 0 {
@@ -1691,7 +1723,6 @@
}
}
}
- count--
}
}
}
@@ -2119,20 +2150,27 @@
orig Module
clone *moduleInfo
}
- ch := make(chan update, 100)
-
- for _, m := range c.modulesSorted {
- go func(m *moduleInfo) {
+ ch := make(chan update)
+ doneCh := make(chan bool)
+ go func() {
+ c.parallelVisit(unorderedVisitorImpl{}, func(m *moduleInfo) bool {
origLogicModule := m.logicModule
m.logicModule, m.properties = c.cloneLogicModule(m)
ch <- update{origLogicModule, m}
- }(m)
- }
+ return false
+ })
+ doneCh <- true
+ }()
- for i := 0; i < len(c.modulesSorted); i++ {
- update := <-ch
- delete(c.moduleInfo, update.orig)
- c.moduleInfo[update.clone.logicModule] = update.clone
+ done := false
+ for !done {
+ select {
+ case <-doneCh:
+ done = true
+ case update := <-ch:
+ delete(c.moduleInfo, update.orig)
+ c.moduleInfo[update.clone.logicModule] = update.clone
+ }
}
}
diff --git a/parser/ast.go b/parser/ast.go
index 7f94efb..b5053bb 100644
--- a/parser/ast.go
+++ b/parser/ast.go
@@ -21,9 +21,9 @@
)
type Node interface {
- // Pos returns the position of the first token in the Expression
+ // Pos returns the position of the first token in the Node
Pos() scanner.Position
- // End returns the position of the beginning of the last token in the Expression
+ // End returns the position of the character after the last token in the Node
End() scanner.Position
}
@@ -220,7 +220,7 @@
}
func (x *Variable) Pos() scanner.Position { return x.NamePos }
-func (x *Variable) End() scanner.Position { return x.NamePos }
+func (x *Variable) End() scanner.Position { return endPos(x.NamePos, len(x.Name)) }
func (x *Variable) Copy() Expression {
ret := *x
@@ -244,7 +244,7 @@
}
func (x *Map) Pos() scanner.Position { return x.LBracePos }
-func (x *Map) End() scanner.Position { return x.RBracePos }
+func (x *Map) End() scanner.Position { return endPos(x.RBracePos, 1) }
func (x *Map) Copy() Expression {
ret := *x
@@ -302,7 +302,7 @@
}
func (x *List) Pos() scanner.Position { return x.LBracePos }
-func (x *List) End() scanner.Position { return x.RBracePos }
+func (x *List) End() scanner.Position { return endPos(x.RBracePos, 1) }
func (x *List) Copy() Expression {
ret := *x
@@ -334,7 +334,7 @@
}
func (x *String) Pos() scanner.Position { return x.LiteralPos }
-func (x *String) End() scanner.Position { return x.LiteralPos }
+func (x *String) End() scanner.Position { return endPos(x.LiteralPos, len(x.Value)+2) }
func (x *String) Copy() Expression {
ret := *x
@@ -356,10 +356,11 @@
type Int64 struct {
LiteralPos scanner.Position
Value int64
+ Token string
}
func (x *Int64) Pos() scanner.Position { return x.LiteralPos }
-func (x *Int64) End() scanner.Position { return x.LiteralPos }
+func (x *Int64) End() scanner.Position { return endPos(x.LiteralPos, len(x.Token)) }
func (x *Int64) Copy() Expression {
ret := *x
@@ -381,10 +382,11 @@
type Bool struct {
LiteralPos scanner.Position
Value bool
+ Token string
}
func (x *Bool) Pos() scanner.Position { return x.LiteralPos }
-func (x *Bool) End() scanner.Position { return x.LiteralPos }
+func (x *Bool) End() scanner.Position { return endPos(x.LiteralPos, len(x.Token)) }
func (x *Bool) Copy() Expression {
ret := *x
@@ -422,7 +424,8 @@
func (c Comment) End() scanner.Position {
pos := c.Slash
for _, comment := range c.Comment {
- pos.Offset += len(comment)
+ pos.Offset += len(comment) + 1
+ pos.Column = len(comment) + 1
}
pos.Line += len(c.Comment) - 1
return pos
@@ -472,3 +475,9 @@
return string(buf)
}
+
+func endPos(pos scanner.Position, n int) scanner.Position {
+ pos.Offset += n
+ pos.Column += n
+ return pos
+}
diff --git a/parser/modify.go b/parser/modify.go
index 08a3f3f..3051f66 100644
--- a/parser/modify.go
+++ b/parser/modify.go
@@ -14,7 +14,12 @@
package parser
-import "fmt"
+import (
+ "fmt"
+ "io"
+ "math"
+ "sort"
+)
func AddStringToList(list *List, s string) (modified bool) {
for _, v := range list.Values {
@@ -50,3 +55,66 @@
return false
}
+
+// A Patch represents a region of a text buffer to be replaced [Start, End) and its Replacement
+type Patch struct {
+ Start, End int
+ Replacement string
+}
+
+// A PatchList is a list of sorted, non-overlapping Patch objects
+type PatchList []Patch
+
+type PatchOverlapError error
+
+// Add adds a Patch to a PatchList. It returns a PatchOverlapError if the patch cannot be added.
+func (list *PatchList) Add(start, end int, replacement string) error {
+ patch := Patch{start, end, replacement}
+ if patch.Start > patch.End {
+ return fmt.Errorf("invalid patch, start %d is after end %d", patch.Start, patch.End)
+ }
+ for _, p := range *list {
+ if (patch.Start >= p.Start && patch.Start < p.End) ||
+ (patch.End >= p.Start && patch.End < p.End) ||
+ (p.Start >= patch.Start && p.Start < patch.End) ||
+ (p.Start == patch.Start && p.End == patch.End) {
+ return PatchOverlapError(fmt.Errorf("new patch %d-%d overlaps with existing patch %d-%d",
+ patch.Start, patch.End, p.Start, p.End))
+ }
+ }
+ *list = append(*list, patch)
+ list.sort()
+ return nil
+}
+
+func (list *PatchList) sort() {
+ sort.SliceStable(*list,
+ func(i, j int) bool {
+ return (*list)[i].Start < (*list)[j].Start
+ })
+}
+
+// Apply applies all the Patch objects in PatchList to the data from an input ReaderAt to an output Writer.
+func (list *PatchList) Apply(in io.ReaderAt, out io.Writer) error {
+ var offset int64
+ for _, patch := range *list {
+ toWrite := int64(patch.Start) - offset
+ written, err := io.Copy(out, io.NewSectionReader(in, offset, toWrite))
+ if err != nil {
+ return err
+ }
+ offset += toWrite
+ if written != toWrite {
+ return fmt.Errorf("unexpected EOF at %d", offset)
+ }
+
+ _, err = io.WriteString(out, patch.Replacement)
+ if err != nil {
+ return err
+ }
+
+ offset += int64(patch.End - patch.Start)
+ }
+ _, err := io.Copy(out, io.NewSectionReader(in, offset, math.MaxInt64-offset))
+ return err
+}
diff --git a/parser/modify_test.go b/parser/modify_test.go
new file mode 100644
index 0000000..95fc293
--- /dev/null
+++ b/parser/modify_test.go
@@ -0,0 +1,65 @@
+// Copyright 2018 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 parser
+
+import (
+ "bytes"
+ "testing"
+)
+
+func TestPatchList(t *testing.T) {
+ expectOverlap := func(err error) {
+ t.Helper()
+ if _, ok := err.(PatchOverlapError); !ok {
+ t.Error("missing PatchOverlapError")
+ }
+ }
+
+ expectOk := func(err error) {
+ t.Helper()
+ if err != nil {
+ t.Error(err)
+ }
+ }
+
+ in := []byte("abcdefghijklmnopqrstuvwxyz")
+
+ patchlist := PatchList{}
+ expectOk(patchlist.Add(0, 3, "ABC"))
+ expectOk(patchlist.Add(12, 15, "MNO"))
+ expectOk(patchlist.Add(24, 26, "Z"))
+ expectOk(patchlist.Add(15, 15, "_"))
+
+ expectOverlap(patchlist.Add(0, 3, "x"))
+ expectOverlap(patchlist.Add(12, 13, "x"))
+ expectOverlap(patchlist.Add(13, 14, "x"))
+ expectOverlap(patchlist.Add(14, 15, "x"))
+ expectOverlap(patchlist.Add(11, 13, "x"))
+ expectOverlap(patchlist.Add(12, 15, "x"))
+ expectOverlap(patchlist.Add(11, 15, "x"))
+ expectOverlap(patchlist.Add(15, 15, "x"))
+
+ if t.Failed() {
+ return
+ }
+
+ buf := new(bytes.Buffer)
+ patchlist.Apply(bytes.NewReader(in), buf)
+ expected := "ABCdefghijklMNO_pqrstuvwxZ"
+ got := buf.String()
+ if got != expected {
+ t.Errorf("expected %q, got %q", expected, got)
+ }
+}
diff --git a/parser/parser.go b/parser/parser.go
index 728afbe..e832e1a 100644
--- a/parser/parser.go
+++ b/parser/parser.go
@@ -360,6 +360,7 @@
v.Value += e2.(*String).Value
case *Int64:
v.Value += e2.(*Int64).Value
+ v.Token = ""
case *List:
v.Values = append(v.Values, e2.(*List).Values...)
case *Map:
@@ -469,6 +470,7 @@
value = &Bool{
LiteralPos: p.scanner.Position,
Value: text == "true",
+ Token: text,
}
default:
if p.eval {
@@ -528,6 +530,7 @@
value := &Int64{
LiteralPos: literalPos,
Value: i,
+ Token: str,
}
p.accept(scanner.Int)
return value
diff --git a/parser/parser_test.go b/parser/parser_test.go
index d740184..6377dc1 100644
--- a/parser/parser_test.go
+++ b/parser/parser_test.go
@@ -17,6 +17,8 @@
import (
"bytes"
"reflect"
+ "strconv"
+ "strings"
"testing"
"text/scanner"
)
@@ -99,6 +101,7 @@
Value: &Bool{
LiteralPos: mkpos(20, 3, 12),
Value: true,
+ Token: "true",
},
},
},
@@ -128,6 +131,7 @@
Value: &Int64{
LiteralPos: mkpos(17, 3, 9),
Value: 4,
+ Token: "4",
},
},
},
@@ -221,6 +225,7 @@
Value: &Bool{
LiteralPos: mkpos(33, 4, 13),
Value: true,
+ Token: "true",
},
},
{
@@ -239,6 +244,7 @@
Value: &Int64{
LiteralPos: mkpos(65, 6, 10),
Value: 36,
+ Token: "36",
},
},
},
@@ -273,6 +279,7 @@
Value: &Bool{
LiteralPos: mkpos(60, 5, 12),
Value: true,
+ Token: "true",
},
},
},
@@ -350,6 +357,7 @@
Value: &Int64{
LiteralPos: mkpos(33, 4, 9),
Value: 4,
+ Token: "4",
},
},
},
@@ -378,6 +386,7 @@
Value: &Int64{
LiteralPos: mkpos(73, 9, 9),
Value: -5,
+ Token: "-5",
},
},
},
@@ -637,6 +646,7 @@
&Int64{
LiteralPos: mkpos(9, 2, 9),
Value: -4,
+ Token: "-4",
},
&Operator{
OperatorPos: mkpos(17, 2, 17),
@@ -649,10 +659,12 @@
&Int64{
LiteralPos: mkpos(14, 2, 14),
Value: -5,
+ Token: "-5",
},
&Int64{
LiteralPos: mkpos(19, 2, 19),
Value: 6,
+ Token: "6",
},
},
},
@@ -669,6 +681,7 @@
&Int64{
LiteralPos: mkpos(9, 2, 9),
Value: -4,
+ Token: "-4",
},
&Operator{
OperatorPos: mkpos(17, 2, 17),
@@ -681,10 +694,12 @@
&Int64{
LiteralPos: mkpos(14, 2, 14),
Value: -5,
+ Token: "-5",
},
&Int64{
LiteralPos: mkpos(19, 2, 19),
Value: 6,
+ Token: "6",
},
},
},
@@ -712,10 +727,12 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
OrigValue: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
Assigner: "=",
Referenced: true,
@@ -730,6 +747,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
OrigValue: &Variable{
@@ -738,6 +756,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
Assigner: "=",
@@ -761,6 +780,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
&Variable{
@@ -772,6 +792,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
},
@@ -791,6 +812,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
&Variable{
@@ -802,6 +824,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
},
@@ -833,6 +856,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
&Variable{
@@ -844,6 +868,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
},
@@ -856,6 +881,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
},
@@ -883,6 +909,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
&Variable{
@@ -894,6 +921,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
},
@@ -912,6 +940,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
OrigValue: &Variable{
@@ -920,6 +949,7 @@
Value: &Int64{
LiteralPos: mkpos(9, 2, 9),
Value: 1000000,
+ Token: "1000000",
},
},
Assigner: "+=",
@@ -985,48 +1015,110 @@
}
func TestParseValidInput(t *testing.T) {
- for _, testCase := range validParseTestCases {
- r := bytes.NewBufferString(testCase.input)
- file, errs := ParseAndEval("", r, NewScope(nil))
- if len(errs) != 0 {
- t.Errorf("test case: %s", testCase.input)
- t.Errorf("unexpected errors:")
- for _, err := range errs {
- t.Errorf(" %s", err)
- }
- t.FailNow()
- }
-
- if len(file.Defs) == len(testCase.defs) {
- for i := range file.Defs {
- if !reflect.DeepEqual(file.Defs[i], testCase.defs[i]) {
- t.Errorf("test case: %s", testCase.input)
- t.Errorf("incorrect defintion %d:", i)
- t.Errorf(" expected: %s", testCase.defs[i])
- t.Errorf(" got: %s", file.Defs[i])
+ for i, testCase := range validParseTestCases {
+ t.Run(strconv.Itoa(i), func(t *testing.T) {
+ r := bytes.NewBufferString(testCase.input)
+ file, errs := ParseAndEval("", r, NewScope(nil))
+ if len(errs) != 0 {
+ t.Errorf("test case: %s", testCase.input)
+ t.Errorf("unexpected errors:")
+ for _, err := range errs {
+ t.Errorf(" %s", err)
}
+ t.FailNow()
}
- } else {
- t.Errorf("test case: %s", testCase.input)
- t.Errorf("length mismatch, expected %d definitions, got %d",
- len(testCase.defs), len(file.Defs))
- }
- if len(file.Comments) == len(testCase.comments) {
- for i := range file.Comments {
- if !reflect.DeepEqual(file.Comments[i], testCase.comments[i]) {
- t.Errorf("test case: %s", testCase.input)
- t.Errorf("incorrect comment %d:", i)
- t.Errorf(" expected: %s", testCase.comments[i])
- t.Errorf(" got: %s", file.Comments[i])
+ if len(file.Defs) == len(testCase.defs) {
+ for i := range file.Defs {
+ if !reflect.DeepEqual(file.Defs[i], testCase.defs[i]) {
+ t.Errorf("test case: %s", testCase.input)
+ t.Errorf("incorrect defintion %d:", i)
+ t.Errorf(" expected: %s", testCase.defs[i])
+ t.Errorf(" got: %s", file.Defs[i])
+ }
}
+ } else {
+ t.Errorf("test case: %s", testCase.input)
+ t.Errorf("length mismatch, expected %d definitions, got %d",
+ len(testCase.defs), len(file.Defs))
}
- } else {
- t.Errorf("test case: %s", testCase.input)
- t.Errorf("length mismatch, expected %d comments, got %d",
- len(testCase.comments), len(file.Comments))
- }
+
+ if len(file.Comments) == len(testCase.comments) {
+ for i := range file.Comments {
+ if !reflect.DeepEqual(file.Comments[i], testCase.comments[i]) {
+ t.Errorf("test case: %s", testCase.input)
+ t.Errorf("incorrect comment %d:", i)
+ t.Errorf(" expected: %s", testCase.comments[i])
+ t.Errorf(" got: %s", file.Comments[i])
+ }
+ }
+ } else {
+ t.Errorf("test case: %s", testCase.input)
+ t.Errorf("length mismatch, expected %d comments, got %d",
+ len(testCase.comments), len(file.Comments))
+ }
+ })
}
}
// TODO: Test error strings
+
+func TestParserEndPos(t *testing.T) {
+ in := `
+ module {
+ string: "string",
+ stringexp: "string1" + "string2",
+ int: -1,
+ intexp: -1 + 2,
+ list: ["a", "b"],
+ listexp: ["c"] + ["d"],
+ multilinelist: [
+ "e",
+ "f",
+ ],
+ map: {
+ prop: "abc",
+ },
+ }
+ `
+
+ // Strip each line to make it easier to compute the previous "," from each property
+ lines := strings.Split(in, "\n")
+ for i := range lines {
+ lines[i] = strings.TrimSpace(lines[i])
+ }
+ in = strings.Join(lines, "\n")
+
+ r := bytes.NewBufferString(in)
+
+ file, errs := ParseAndEval("", r, NewScope(nil))
+ if len(errs) != 0 {
+ t.Errorf("unexpected errors:")
+ for _, err := range errs {
+ t.Errorf(" %s", err)
+ }
+ t.FailNow()
+ }
+
+ mod := file.Defs[0].(*Module)
+ modEnd := mkpos(len(in)-1, len(lines)-1, 2)
+ if mod.End() != modEnd {
+ t.Errorf("expected mod.End() %s, got %s", modEnd, mod.End())
+ }
+
+ nextPos := make([]scanner.Position, len(mod.Properties))
+ for i := 0; i < len(mod.Properties)-1; i++ {
+ nextPos[i] = mod.Properties[i+1].Pos()
+ }
+ nextPos[len(mod.Properties)-1] = mod.RBracePos
+
+ for i, cur := range mod.Properties {
+ endOffset := nextPos[i].Offset - len(",\n")
+ endLine := nextPos[i].Line - 1
+ endColumn := len(lines[endLine-1]) // scanner.Position.Line is starts at 1
+ endPos := mkpos(endOffset, endLine, endColumn)
+ if cur.End() != endPos {
+ t.Errorf("expected property %s End() %s@%d, got %s@%d", cur.Name, endPos, endPos.Offset, cur.End(), cur.End().Offset)
+ }
+ }
+}
diff --git a/proptools/proptools.go b/proptools/proptools.go
index e071b3c..f4da29e 100644
--- a/proptools/proptools.go
+++ b/proptools/proptools.go
@@ -66,20 +66,32 @@
return &s
}
-// Bool takes a pointer to a bool and returns true iff the pointer is non-nil and points to a true
-// value.
-func Bool(b *bool) bool {
+// BoolDefault takes a pointer to a bool and returns the value pointed to by the pointer if it is non-nil,
+// or def if the pointer is nil.
+func BoolDefault(b *bool, def bool) bool {
if b != nil {
return *b
}
- return false
+ return def
+}
+
+// Bool takes a pointer to a bool and returns true iff the pointer is non-nil and points to a true
+// value.
+func Bool(b *bool) bool {
+ return BoolDefault(b, false)
+}
+
+// String takes a pointer to a string and returns the value of the string if the pointer is non-nil,
+// or def if the pointer is nil.
+func StringDefault(s *string, def string) string {
+ if s != nil {
+ return *s
+ }
+ return def
}
// String takes a pointer to a string and returns the value of the string if the pointer is non-nil,
// or an empty string.
func String(s *string) string {
- if s != nil {
- return *s
- }
- return ""
+ return StringDefault(s, "")
}
