diff options
| -rw-r--r-- | Blueprints | 1 | ||||
| -rw-r--r-- | context.go | 80 | ||||
| -rw-r--r-- | parser/ast.go | 27 | ||||
| -rw-r--r-- | parser/modify.go | 70 | ||||
| -rw-r--r-- | parser/modify_test.go | 65 | ||||
| -rw-r--r-- | parser/parser.go | 3 | ||||
| -rw-r--r-- | parser/parser_test.go | 160 | ||||
| -rw-r--r-- | proptools/proptools.go | 26 |
8 files changed, 360 insertions, 72 deletions
@@ -43,6 +43,7 @@ bootstrap_go_package { "parser/sort.go", ], testSrcs: [ + "parser/modify_test.go", "parser/parser_test.go", "parser/printer_test.go", ], @@ -1608,6 +1608,24 @@ type visitOrderer interface { 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 @@ func (c *Context) parallelVisit(order visitOrderer, visit func(group *moduleInfo 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 @@ func (c *Context) parallelVisit(order visitOrderer, visit func(group *moduleInfo } } - 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 @@ func (c *Context) parallelVisit(order visitOrderer, visit func(group *moduleInfo } } } - count-- } } } @@ -2119,20 +2150,27 @@ func (c *Context) cloneModules() { 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 @@ import ( ) 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 @@ type Variable struct { } 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 @@ type Map struct { } 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 @@ type List struct { } 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 @@ type String struct { } 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 @@ func (x *String) Type() Type { 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 @@ func (x *Int64) Type() Type { 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) Pos() scanner.Position { 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 @@ func (c Comment) Text() string { 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 @@ func RemoveStringFromList(list *List, s string) (modified bool) { 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 @@ func (p *parser) evaluateOperator(value1, value2 Expression, operator rune, 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 @@ func (p *parser) parseVariable() Expression { value = &Bool{ LiteralPos: p.scanner.Position, Value: text == "true", + Token: text, } default: if p.eval { @@ -528,6 +530,7 @@ func (p *parser) parseIntValue() *Int64 { 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 @@ package parser import ( "bytes" "reflect" + "strconv" + "strings" "testing" "text/scanner" ) @@ -99,6 +101,7 @@ var validParseTestCases = []struct { Value: &Bool{ LiteralPos: mkpos(20, 3, 12), Value: true, + Token: "true", }, }, }, @@ -128,6 +131,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(17, 3, 9), Value: 4, + Token: "4", }, }, }, @@ -221,6 +225,7 @@ var validParseTestCases = []struct { Value: &Bool{ LiteralPos: mkpos(33, 4, 13), Value: true, + Token: "true", }, }, { @@ -239,6 +244,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(65, 6, 10), Value: 36, + Token: "36", }, }, }, @@ -273,6 +279,7 @@ var validParseTestCases = []struct { Value: &Bool{ LiteralPos: mkpos(60, 5, 12), Value: true, + Token: "true", }, }, }, @@ -350,6 +357,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(33, 4, 9), Value: 4, + Token: "4", }, }, }, @@ -378,6 +386,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(73, 9, 9), Value: -5, + Token: "-5", }, }, }, @@ -637,6 +646,7 @@ var validParseTestCases = []struct { &Int64{ LiteralPos: mkpos(9, 2, 9), Value: -4, + Token: "-4", }, &Operator{ OperatorPos: mkpos(17, 2, 17), @@ -649,10 +659,12 @@ var validParseTestCases = []struct { &Int64{ LiteralPos: mkpos(14, 2, 14), Value: -5, + Token: "-5", }, &Int64{ LiteralPos: mkpos(19, 2, 19), Value: 6, + Token: "6", }, }, }, @@ -669,6 +681,7 @@ var validParseTestCases = []struct { &Int64{ LiteralPos: mkpos(9, 2, 9), Value: -4, + Token: "-4", }, &Operator{ OperatorPos: mkpos(17, 2, 17), @@ -681,10 +694,12 @@ var validParseTestCases = []struct { &Int64{ LiteralPos: mkpos(14, 2, 14), Value: -5, + Token: "-5", }, &Int64{ LiteralPos: mkpos(19, 2, 19), Value: 6, + Token: "6", }, }, }, @@ -712,10 +727,12 @@ var validParseTestCases = []struct { 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 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, OrigValue: &Variable{ @@ -738,6 +756,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, Assigner: "=", @@ -761,6 +780,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, &Variable{ @@ -772,6 +792,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, }, @@ -791,6 +812,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, &Variable{ @@ -802,6 +824,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, }, @@ -833,6 +856,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, &Variable{ @@ -844,6 +868,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, }, @@ -856,6 +881,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, }, @@ -883,6 +909,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, &Variable{ @@ -894,6 +921,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, }, @@ -912,6 +940,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, OrigValue: &Variable{ @@ -920,6 +949,7 @@ var validParseTestCases = []struct { Value: &Int64{ LiteralPos: mkpos(9, 2, 9), Value: 1000000, + Token: "1000000", }, }, Assigner: "+=", @@ -985,48 +1015,110 @@ var validParseTestCases = []struct { } 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) + 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() } - 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]) + 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 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.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)) } - } 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 @@ func StringPtr(s string) *string { 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 an empty string. -func String(s *string) string { +// or def if the pointer is nil. +func StringDefault(s *string, def string) string { if s != nil { return *s } - return "" + 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 { + return StringDefault(s, "") } |