diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2013-11-08 23:23:11 -0800 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2013-11-08 23:23:11 -0800 |
commit | bf512ae9165768ef6c1e4952d14b6b6e9a2f670d (patch) | |
tree | 1b256f5fae5307fd96f7071459ba9b0cf524dfd0 | |
parent | 0e7543e9e969354072ae29f9a091013880cc75e5 (diff) | |
parent | e1fdf86438a6771ff3735a977ca85ba16a99484c (diff) | |
download | scala-bf512ae9165768ef6c1e4952d14b6b6e9a2f670d.tar.gz scala-bf512ae9165768ef6c1e4952d14b6b6e9a2f670d.tar.bz2 scala-bf512ae9165768ef6c1e4952d14b6b6e9a2f670d.zip |
Merge pull request #3100 from som-snytt/paulp/reduction
Paulper stack reduction
-rw-r--r-- | src/compiler/scala/tools/nsc/ast/parser/Parsers.scala | 267 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/Precedence.scala | 38 | ||||
-rw-r--r-- | test/files/neg/t1878.check | 4 | ||||
-rw-r--r-- | test/files/neg/t3189.check | 2 | ||||
-rw-r--r-- | test/files/neg/t5702-neg-bad-and-wild.check | 14 | ||||
-rw-r--r-- | test/files/neg/t5702-neg-bad-xbrace.check | 4 | ||||
-rw-r--r-- | test/files/neg/t5702-neg-ugly-xbrace.check | 2 |
7 files changed, 188 insertions, 143 deletions
diff --git a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala index 07938ec3df..cfa60cabc3 100644 --- a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala +++ b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala @@ -11,7 +11,7 @@ package ast.parser import scala.collection.{ mutable, immutable } import mutable.{ ListBuffer, StringBuilder } -import scala.reflect.internal.{ ModifierFlags => Flags } +import scala.reflect.internal.{ Precedence, ModifierFlags => Flags } import scala.reflect.internal.Chars.{ isScalaLetter } import scala.reflect.internal.util.{ SourceFile, Position, FreshNameCreator } import Tokens._ @@ -133,7 +133,9 @@ self => val global: Global import global._ - case class OpInfo(operand: Tree, operator: Name, offset: Offset) + case class OpInfo(lhs: Tree, operator: TermName, offset: Offset) { + def precedence = Precedence(operator.toString) + } class SourceFileParser(val source: SourceFile) extends Parser { @@ -146,17 +148,6 @@ self => def newScanner(): Scanner = new SourceFileScanner(source) - /** Scoping operator used to temporarily look into the future. - * Backs up scanner data before evaluating a block and restores it after. - */ - def lookingAhead[T](body: => T): T = { - val snapshot = (new ScannerData{}).copyFrom(in) - in.nextToken() - val res = body - in copyFrom snapshot - res - } - val in = newScanner() in.init() @@ -284,6 +275,34 @@ self => def unit: CompilationUnit def source: SourceFile + /** Scoping operator used to temporarily look into the future. + * Backs up scanner data before evaluating a block and restores it after. + */ + @inline final def lookingAhead[T](body: => T): T = { + val saved = new ScannerData {} copyFrom in + in.nextToken() + try body finally in copyFrom saved + } + + /** Perform an operation while peeking ahead. + * Pushback if the operation yields an empty tree or blows to pieces. + */ + @inline def peekingAhead(tree: =>Tree): Tree = { + @inline def peekahead() = { + in.prev copyFrom in + in.nextToken() + } + @inline def pushback() = { + in.next copyFrom in + in copyFrom in.prev + } + peekahead() + // try it, in case it is recoverable + val res = try tree catch { case e: Exception => pushback() ; throw e } + if (res.isEmpty) pushback() + res + } + class ParserTreeBuilder extends TreeBuilder { val global: self.global.type = self.global def unit = parser.unit @@ -311,6 +330,7 @@ self => finally classContextBounds = saved } + /** Are we inside the Scala package? Set for files that start with package scala */ private var inScalaPackage = false @@ -642,6 +662,10 @@ self => case INTLIT | LONGLIT | FLOATLIT | DOUBLELIT => true case _ => false } + + def isIdentExcept(except: Name) = isIdent && in.name != except + def isIdentOf(name: Name) = isIdent && in.name == name + def isUnaryOp = isIdent && raw.isUnary(in.name) def isRawStar = isIdent && in.name == raw.STAR def isRawBar = isIdent && in.name == raw.BAR @@ -754,49 +778,60 @@ self => var opstack: List[OpInfo] = Nil - def precedence(operator: Name): Int = - if (operator eq nme.ERROR) -1 - else { - val firstCh = operator.startChar - if (isScalaLetter(firstCh)) 1 - else if (nme.isOpAssignmentName(operator)) 0 - else firstCh match { - case '|' => 2 - case '^' => 3 - case '&' => 4 - case '=' | '!' => 5 - case '<' | '>' => 6 - case ':' => 7 - case '+' | '-' => 8 - case '*' | '/' | '%' => 9 - case _ => 10 - } - } + @deprecated("Use `scala.reflect.internal.Precedence`", "2.11.0") + def precedence(operator: Name): Int = Precedence(operator.toString).level + + private def opHead = opstack.head + private def headPrecedence = opHead.precedence + private def popOpInfo(): OpInfo = try opHead finally opstack = opstack.tail + private def pushOpInfo(top: Tree) { + val opinfo = OpInfo(top, in.name, in.offset) + opstack ::= opinfo + ident() + } - def checkAssoc(offset: Offset, op: Name, leftAssoc: Boolean) = + def checkHeadAssoc(leftAssoc: Boolean) = checkAssoc(opHead.offset, opHead.operator, leftAssoc) + def checkAssoc(offset: Offset, op: Name, leftAssoc: Boolean) = ( if (treeInfo.isLeftAssoc(op) != leftAssoc) - syntaxError( - offset, "left- and right-associative operators with same precedence may not be mixed", skipIt = false) - - def reduceStack(isExpr: Boolean, base: List[OpInfo], top0: Tree, prec: Int, leftAssoc: Boolean): Tree = { - var top = top0 - if (opstack != base && precedence(opstack.head.operator) == prec) - checkAssoc(opstack.head.offset, opstack.head.operator, leftAssoc) - while (opstack != base && - (prec < precedence(opstack.head.operator) || - leftAssoc && prec == precedence(opstack.head.operator))) { - val opinfo = opstack.head - opstack = opstack.tail - val opPos = r2p(opinfo.offset, opinfo.offset, opinfo.offset+opinfo.operator.length) - val lPos = opinfo.operand.pos - val start = if (lPos.isDefined) lPos.start else opPos.start - val rPos = top.pos - val end = if (rPos.isDefined) rPos.end else opPos.end - top = atPos(start, opinfo.offset, end) { - makeBinop(isExpr, opinfo.operand, opinfo.operator.toTermName, top, opPos) - } - } - top + syntaxError(offset, "left- and right-associative operators with same precedence may not be mixed", skipIt = false) + ) + + def finishPostfixOp(start: Int, base: List[OpInfo], opinfo: OpInfo): Tree = { + val od = stripParens(reduceExprStack(base, opinfo.lhs)) + makePostfixSelect(start, opinfo.offset, od, opinfo.operator) + } + + def finishBinaryOp(isExpr: Boolean, opinfo: OpInfo, rhs: Tree): Tree = { + import opinfo._ + val operatorPos: Position = Position.range(rhs.pos.source, offset, offset, offset + operator.length) + val pos = lhs.pos union rhs.pos union operatorPos withPoint offset + + atPos(pos)(makeBinop(isExpr, lhs, operator, rhs, operatorPos)) + } + + def reduceExprStack(base: List[OpInfo], top: Tree): Tree = reduceStack(isExpr = true, base, top) + def reducePatternStack(base: List[OpInfo], top: Tree): Tree = reduceStack(isExpr = false, base, top) + + def reduceStack(isExpr: Boolean, base: List[OpInfo], top: Tree): Tree = { + val opPrecedence = if (isIdent) Precedence(in.name.toString) else Precedence(0) + val leftAssoc = !isIdent || (treeInfo isLeftAssoc in.name) + + reduceStack(isExpr, base, top, opPrecedence, leftAssoc) + } + + def reduceStack(isExpr: Boolean, base: List[OpInfo], top: Tree, opPrecedence: Precedence, leftAssoc: Boolean): Tree = { + def isDone = opstack == base + def lowerPrecedence = !isDone && (opPrecedence < headPrecedence) + def samePrecedence = !isDone && (opPrecedence == headPrecedence) + def canReduce = lowerPrecedence || leftAssoc && samePrecedence + + if (samePrecedence) + checkHeadAssoc(leftAssoc) + + def loop(top: Tree): Tree = + if (canReduce) loop(finishBinaryOp(isExpr, popOpInfo(), top)) else top + + loop(top) } /* -------- IDENTIFIERS AND LITERALS ------------------------------------------- */ @@ -1475,28 +1510,19 @@ self => def postfixExpr(): Tree = { val start = in.offset val base = opstack - var top = prefixExpr() - while (isIdent) { - top = reduceStack(isExpr = true, base, top, precedence(in.name), leftAssoc = treeInfo.isLeftAssoc(in.name)) - val op = in.name - opstack = OpInfo(top, op, in.offset) :: opstack - ident() + def loop(top: Tree): Tree = if (!isIdent) top else { + pushOpInfo(reduceExprStack(base, top)) newLineOptWhenFollowing(isExprIntroToken) - if (isExprIntro) { - val next = prefixExpr() - if (next == EmptyTree) - return reduceStack(isExpr = true, base, top, 0, leftAssoc = true) - top = next - } else { - // postfix expression - val topinfo = opstack.head - opstack = opstack.tail - val od = stripParens(reduceStack(isExpr = true, base, topinfo.operand, 0, leftAssoc = true)) - return makePostfixSelect(start, topinfo.offset, od, topinfo.operator) - } + if (isExprIntro) + prefixExpr() match { + case EmptyTree => reduceExprStack(base, top) + case next => loop(next) + } + else finishPostfixOp(start, base, popOpInfo()) } - reduceStack(isExpr = true, base, top, 0, leftAssoc = true) + + reduceExprStack(base, loop(prefixExpr())) } /** {{{ @@ -1815,69 +1841,50 @@ self => * }}} */ def pattern3(): Tree = { - var top = simplePattern(badPattern3) - // after peekahead - def acceptWildStar() = atPos(top.pos.start, in.prev.offset)(Star(stripParens(top))) - def peekahead() = { - in.prev copyFrom in - in.nextToken() - } - def pushback() = { - in.next copyFrom in - in copyFrom in.prev - } + val top = simplePattern(badPattern3) + val base = opstack // See SI-3189, SI-4832 for motivation. Cf SI-3480 for counter-motivation. - // TODO: dredge out the remnants of regexp patterns. - // /{/ peek for _*) or _*} (for xml escape) - if (isSequenceOK) { - top match { - case Ident(nme.WILDCARD) if (isRawStar) => - peekahead() - in.token match { - case RBRACE if (isXML) => return acceptWildStar() - case RPAREN if (!isXML) => return acceptWildStar() - case _ => pushback() - } - case _ => - } + def isCloseDelim = in.token match { + case RBRACE => isXML + case RPAREN => !isXML + case _ => false } - val base = opstack - while (isIdent && in.name != raw.BAR) { - top = reduceStack(isExpr = false, base, top, precedence(in.name), leftAssoc = treeInfo.isLeftAssoc(in.name)) - val op = in.name - opstack = OpInfo(top, op, in.offset) :: opstack - ident() - top = simplePattern(badPattern3) + def checkWildStar: Tree = top match { + case Ident(nme.WILDCARD) if isSequenceOK && isRawStar => peekingAhead ( + if (isCloseDelim) atPos(top.pos.start, in.prev.offset)(Star(stripParens(top))) + else EmptyTree + ) + case _ => EmptyTree } - stripParens(reduceStack(isExpr = false, base, top, 0, leftAssoc = true)) + def loop(top: Tree): Tree = reducePatternStack(base, top) match { + case next if isIdentExcept(raw.BAR) => pushOpInfo(next) ; loop(simplePattern(badPattern3)) + case next => next + } + checkWildStar orElse stripParens(loop(top)) } + def badPattern3(): Tree = { - def isComma = in.token == COMMA - def isAnyBrace = in.token == RPAREN || in.token == RBRACE - val badStart = "illegal start of simple pattern" + def isComma = in.token == COMMA + def isDelimiter = in.token == RPAREN || in.token == RBRACE + def isCommaOrDelimiter = isComma || isDelimiter + val (isUnderscore, isStar) = opstack match { + case OpInfo(Ident(nme.WILDCARD), nme.STAR, _) :: _ => (true, true) + case OpInfo(_, nme.STAR, _) :: _ => (false, true) + case _ => (false, false) + } + def isSeqPatternClose = isUnderscore && isStar && isSequenceOK && isDelimiter + val preamble = "bad simple pattern:" + val subtext = (isUnderscore, isStar, isSequenceOK) match { + case (true, true, true) if isComma => "bad use of _* (a sequence pattern must be the last pattern)" + case (true, true, true) if isDelimiter => "bad brace or paren after _*" + case (true, true, false) if isDelimiter => "bad use of _* (sequence pattern not allowed)" + case (false, true, true) if isDelimiter => "use _* to match a sequence" + case (false, true, _) if isCommaOrDelimiter => "trailing * is not a valid pattern" + case _ => null + } + val msg = if (subtext != null) s"$preamble $subtext" else "illegal start of simple pattern" // better recovery if don't skip delims of patterns - var skip = !(isComma || isAnyBrace) - val msg = if (!opstack.isEmpty && opstack.head.operator == nme.STAR) { - opstack.head.operand match { - case Ident(nme.WILDCARD) => - if (isSequenceOK && isComma) - "bad use of _* (a sequence pattern must be the last pattern)" - else if (isSequenceOK && isAnyBrace) { - skip = true // do skip bad paren; scanner may skip bad brace already - "bad brace or paren after _*" - } else if (!isSequenceOK && isAnyBrace) - "bad use of _* (sequence pattern not allowed)" - else badStart - case _ => - if (isSequenceOK && isAnyBrace) - "use _* to match a sequence" - else if (isComma || isAnyBrace) - "trailing * is not a valid pattern" - else badStart - } - } else { - badStart - } + val skip = !isCommaOrDelimiter || isSeqPatternClose syntaxErrorOrIncompleteAnd(msg, skip)(errorPatternTree) } diff --git a/src/reflect/scala/reflect/internal/Precedence.scala b/src/reflect/scala/reflect/internal/Precedence.scala new file mode 100644 index 0000000000..1430838b9d --- /dev/null +++ b/src/reflect/scala/reflect/internal/Precedence.scala @@ -0,0 +1,38 @@ +package scala +package reflect +package internal + +import scala.annotation.switch +import Chars._ + +final class Precedence private (val level: Int) extends AnyVal with Ordered[Precedence] { + def compare(that: Precedence): Int = level compare that.level + override def toString = s"Precedence($level)" +} + + +object Precedence extends (Int => Precedence) { + private val ErrorName = "<error>" + private def isAssignmentOp(name: String) = name match { + case "!=" | "<=" | ">=" | "" => false + case _ => name.last == '=' && name.head != '=' && isOperatorPart(name.head) + } + private def firstChar(ch: Char): Precedence = apply((ch: @switch) match { + case '|' => 2 + case '^' => 3 + case '&' => 4 + case '=' | '!' => 5 + case '<' | '>' => 6 + case ':' => 7 + case '+' | '-' => 8 + case '*' | '/' | '%' => 9 + case _ => if (isScalaLetter(ch)) 1 else 10 + }) + + def apply(level: Int): Precedence = new Precedence(level) + def apply(name: String): Precedence = name match { + case "" | ErrorName => this(-1) + case _ if isAssignmentOp(name) => this(0) + case _ => firstChar(name charAt 0) + } +} diff --git a/test/files/neg/t1878.check b/test/files/neg/t1878.check index ac2071c3d8..5814375515 100644 --- a/test/files/neg/t1878.check +++ b/test/files/neg/t1878.check @@ -1,7 +1,7 @@ -t1878.scala:3: error: bad use of _* (a sequence pattern must be the last pattern) +t1878.scala:3: error: bad simple pattern: bad use of _* (a sequence pattern must be the last pattern) val err1 = "" match { case Seq(f @ _*, ',') => f } ^ -t1878.scala:9: error: bad use of _* (a sequence pattern must be the last pattern) +t1878.scala:9: error: bad simple pattern: bad use of _* (a sequence pattern must be the last pattern) val List(List(_*, arg2), _) = List(List(1,2,3), List(4,5,6)) ^ two errors found diff --git a/test/files/neg/t3189.check b/test/files/neg/t3189.check index 3913c526a2..122af56474 100644 --- a/test/files/neg/t3189.check +++ b/test/files/neg/t3189.check @@ -1,4 +1,4 @@ -t3189.scala:2: error: use _* to match a sequence +t3189.scala:2: error: bad simple pattern: use _* to match a sequence val Array(a,b*) = ("": Any) ^ one error found diff --git a/test/files/neg/t5702-neg-bad-and-wild.check b/test/files/neg/t5702-neg-bad-and-wild.check index eae81ad5f2..ff9e5e5703 100644 --- a/test/files/neg/t5702-neg-bad-and-wild.check +++ b/test/files/neg/t5702-neg-bad-and-wild.check @@ -1,4 +1,4 @@ -t5702-neg-bad-and-wild.scala:10: error: bad use of _* (a sequence pattern must be the last pattern) +t5702-neg-bad-and-wild.scala:10: error: bad simple pattern: bad use of _* (a sequence pattern must be the last pattern) case List(1, _*,) => // bad use of _* (a sequence pattern must be the last pattern) ^ t5702-neg-bad-and-wild.scala:10: error: illegal start of simple pattern @@ -7,22 +7,22 @@ t5702-neg-bad-and-wild.scala:10: error: illegal start of simple pattern t5702-neg-bad-and-wild.scala:12: error: illegal start of simple pattern case List(1, _*3,) => // illegal start of simple pattern ^ -t5702-neg-bad-and-wild.scala:14: error: use _* to match a sequence +t5702-neg-bad-and-wild.scala:14: error: bad simple pattern: use _* to match a sequence case List(1, x*) => // use _* to match a sequence ^ -t5702-neg-bad-and-wild.scala:15: error: trailing * is not a valid pattern +t5702-neg-bad-and-wild.scala:15: error: bad simple pattern: trailing * is not a valid pattern case List(x*, 1) => // trailing * is not a valid pattern ^ -t5702-neg-bad-and-wild.scala:16: error: trailing * is not a valid pattern +t5702-neg-bad-and-wild.scala:16: error: bad simple pattern: trailing * is not a valid pattern case (1, x*) => // trailing * is not a valid pattern ^ -t5702-neg-bad-and-wild.scala:17: error: bad use of _* (sequence pattern not allowed) +t5702-neg-bad-and-wild.scala:17: error: bad simple pattern: bad use of _* (sequence pattern not allowed) case (1, x@_*) => // bad use of _* (sequence pattern not allowed) ^ -t5702-neg-bad-and-wild.scala:23: error: bad use of _* (a sequence pattern must be the last pattern) +t5702-neg-bad-and-wild.scala:23: error: bad simple pattern: bad use of _* (a sequence pattern must be the last pattern) val K(ns @ _*, x) = k // bad use of _* (a sequence pattern must be the last pattern) ^ -t5702-neg-bad-and-wild.scala:24: error: bad use of _* (sequence pattern not allowed) +t5702-neg-bad-and-wild.scala:24: error: bad simple pattern: bad use of _* (sequence pattern not allowed) val (b, _ * ) = Pair(5,6) // bad use of _* (sequence pattern not allowed) ^ 9 errors found diff --git a/test/files/neg/t5702-neg-bad-xbrace.check b/test/files/neg/t5702-neg-bad-xbrace.check index d88638aee9..9240abea44 100644 --- a/test/files/neg/t5702-neg-bad-xbrace.check +++ b/test/files/neg/t5702-neg-bad-xbrace.check @@ -1,7 +1,7 @@ -t5702-neg-bad-xbrace.scala:19: error: bad brace or paren after _* +t5702-neg-bad-xbrace.scala:19: error: bad simple pattern: bad brace or paren after _* case <year>{_*)}</year> => y ^ -t5702-neg-bad-xbrace.scala:28: error: bad brace or paren after _* +t5702-neg-bad-xbrace.scala:28: error: bad simple pattern: bad brace or paren after _* val <top>{a, z@_*)}</top> = xml ^ two errors found diff --git a/test/files/neg/t5702-neg-ugly-xbrace.check b/test/files/neg/t5702-neg-ugly-xbrace.check index 7d80bbf6be..cdd2438b0e 100644 --- a/test/files/neg/t5702-neg-ugly-xbrace.check +++ b/test/files/neg/t5702-neg-ugly-xbrace.check @@ -1,4 +1,4 @@ -t5702-neg-ugly-xbrace.scala:11: error: bad brace or paren after _* +t5702-neg-ugly-xbrace.scala:11: error: bad simple pattern: bad brace or paren after _* val <top>{a, z@_*)</top> = xml ^ t5702-neg-ugly-xbrace.scala:12: error: Missing closing brace `}' assumed here |