libgo, compiler: Upgrade libgo to Go 1.4, except for runtime.

This upgrades all of libgo other than the runtime package to
the Go 1.4 release.  In Go 1.4 much of the runtime was
rewritten into Go.  Merging that code will take more time and
will not change the API, so I'm putting it off for now.

There are a few runtime changes anyhow, to accomodate other
packages that rely on minor modifications to the runtime
support.

The compiler changes slightly to add a one-bit flag to each
type descriptor kind that is stored directly in an interface,
which for gccgo is currently only pointer types.  Another
one-bit flag (gcprog) is reserved because it is used by the gc
compiler, but gccgo does not currently use it.

There is another error check in the compiler since I ran
across it during testing.

gotools/:
	* Makefile.am (go_cmd_go_files): Sort entries.  Add generate.go.
	* Makefile.in: Rebuild.

From-SVN: r219627

1 files changed, 40 insertions, 1 deletions

diff --git a/libgo/go/regexp/syntax/parse.go b/libgo/go/regexp/syntax/parse.go
index cb25dca3956..d579a4069b1 100644
--- a/libgo/go/regexp/syntax/parse.go
+++ b/libgo/go/regexp/syntax/parse.go
@@ -244,6 +244,7 @@ func (p *parser) repeat(op Op, min, max int, before, after, lastRepeat string) (
 	if sub.Op >= opPseudo {
 		return "", &Error{ErrMissingRepeatArgument, before[:len(before)-len(after)]}
 	}
+
 	re := p.newRegexp(op)
 	re.Min = min
 	re.Max = max
@@ -251,9 +252,47 @@ func (p *parser) repeat(op Op, min, max int, before, after, lastRepeat string) (
 	re.Sub = re.Sub0[:1]
 	re.Sub[0] = sub
 	p.stack[n-1] = re
+
+	if op == OpRepeat && (min >= 2 || max >= 2) && !repeatIsValid(re, 1000) {
+		return "", &Error{ErrInvalidRepeatSize, before[:len(before)-len(after)]}
+	}
+
 	return after, nil
 }
 
+// repeatIsValid reports whether the repetition re is valid.
+// Valid means that the combination of the top-level repetition
+// and any inner repetitions does not exceed n copies of the
+// innermost thing.
+// This function rewalks the regexp tree and is called for every repetition,
+// so we have to worry about inducing quadratic behavior in the parser.
+// We avoid this by only calling repeatIsValid when min or max >= 2.
+// In that case the depth of any >= 2 nesting can only get to 9 without
+// triggering a parse error, so each subtree can only be rewalked 9 times.
+func repeatIsValid(re *Regexp, n int) bool {
+	if re.Op == OpRepeat {
+		m := re.Max
+		if m == 0 {
+			return true
+		}
+		if m < 0 {
+			m = re.Min
+		}
+		if m > n {
+			return false
+		}
+		if m > 0 {
+			n /= m
+		}
+	}
+	for _, sub := range re.Sub {
+		if !repeatIsValid(sub, n) {
+			return false
+		}
+	}
+	return true
+}
+
 // concat replaces the top of the stack (above the topmost '|' or '(') with its concatenation.
 func (p *parser) concat() *Regexp {
 	p.maybeConcat(-1, 0)
@@ -1639,7 +1678,7 @@ const (
 	// minimum and maximum runes involved in folding.
 	// checked during test.
 	minFold = 0x0041
-	maxFold = 0x1044f
+	maxFold = 0x118df
 )
 
 // appendFoldedRange returns the result of appending the range lo-hi