From e7ea29cc0b3c55d7880b767f8c442d8bf3cd0dea Mon Sep 17 00:00:00 2001 From: Alex Cruise Date: Thu, 8 Mar 2012 23:41:58 -0800 Subject: SI-1118 WIP --- src/library/scala/xml/Elem.scala | 35 +++++++++--- src/library/scala/xml/Node.scala | 2 +- src/library/scala/xml/PrettyPrinter.scala | 2 +- src/library/scala/xml/Utility.scala | 66 ++++++++++++++++------ src/library/scala/xml/XML.scala | 19 ++++++- src/library/scala/xml/factory/Binder.scala | 10 ++-- .../scala/xml/parsing/ConstructingHandler.scala | 4 +- .../scala/xml/parsing/DefaultMarkupHandler.scala | 2 +- src/library/scala/xml/parsing/MarkupHandler.scala | 3 +- src/library/scala/xml/parsing/MarkupParser.scala | 2 +- src/library/scala/xml/pull/XMLEventReader.scala | 2 +- 11 files changed, 107 insertions(+), 40 deletions(-) mode change 100644 => 100755 src/library/scala/xml/Elem.scala mode change 100644 => 100755 src/library/scala/xml/Node.scala mode change 100644 => 100755 src/library/scala/xml/PrettyPrinter.scala mode change 100644 => 100755 src/library/scala/xml/Utility.scala mode change 100644 => 100755 src/library/scala/xml/XML.scala mode change 100644 => 100755 src/library/scala/xml/factory/Binder.scala mode change 100644 => 100755 src/library/scala/xml/parsing/ConstructingHandler.scala mode change 100644 => 100755 src/library/scala/xml/parsing/DefaultMarkupHandler.scala mode change 100644 => 100755 src/library/scala/xml/parsing/MarkupHandler.scala mode change 100644 => 100755 src/library/scala/xml/parsing/MarkupParser.scala (limited to 'src/library') diff --git a/src/library/scala/xml/Elem.scala b/src/library/scala/xml/Elem.scala old mode 100644 new mode 100755 index df52b34f87..605f3cb7fb --- a/src/library/scala/xml/Elem.scala +++ b/src/library/scala/xml/Elem.scala @@ -17,8 +17,18 @@ package scala.xml * @author Burak Emir */ object Elem { - def apply(prefix: String,label: String, attributes: MetaData, scope: NamespaceBinding, child: Node*) = - new Elem(prefix, label, attributes, scope, child:_*) + /** Build an Elem, setting its minimizeEmpty property to true if it has no children. Note that this + * default may not be exactly what you want, as some XML dialects don't permit some elements to be minimized. + * + * @deprecated This factory method is retained for backward compatibility; please use the other one, with which you + * can specify your own preference for minimizeEmpty. + */ + @deprecated + def apply(prefix: String,label: String, attributes: MetaData, scope: NamespaceBinding, child: Node*): Elem = + apply(prefix, label, attributes, scope, child.isEmpty, child: _*) + + def apply(prefix: String,label: String, attributes: MetaData, scope: NamespaceBinding, minimizeEmpty: Boolean, child: Node*): Elem = + new Elem(prefix,label,attributes,scope, minimizeEmpty, child:_*) def unapplySeq(n: Node) = n match { case _: SpecialNode | _: Group => None @@ -29,11 +39,13 @@ object Elem { /** The case class `Elem` extends the `Node` class, * providing an immutable data object representing an XML element. * - * @param prefix namespace prefix (may be null, but not the empty string) - * @param label the element name - * @param attribute the attribute map - * @param scope the scope containing the namespace bindings - * @param child the children of this node + * @param prefix namespace prefix (may be null, but not the empty string) + * @param label the element name + * @param attributes1 the attribute map + * @param scope the scope containing the namespace bindings + * @param minimizeEmpty `true` if this element should be serialized as minimized (i.e. "<el/>") when + * empty; `false` if it should be written out in long form. + * @param child the children of this node * * Copyright 2008 Google Inc. All Rights Reserved. * @author Burak Emir @@ -43,9 +55,15 @@ class Elem( val label: String, attributes1: MetaData, override val scope: NamespaceBinding, + val minimizeEmpty: Boolean, val child: Node*) extends Node with Serializable { + @deprecated(since="2.10", message="this constructor is retained for backward compatibility. Please use the primary constructor, which lets you specify your own preference for `minimizeEmpty`.") + def this(prefix: String, label: String, attributes: MetaData, scope: NamespaceBinding, child: Node*) = { + this(prefix, label, attributes, scope, child.isEmpty, child: _*) + } + final override def doCollectNamespaces = true final override def doTransform = true @@ -83,8 +101,9 @@ extends Node with Serializable label: String = this.label, attributes: MetaData = this.attributes, scope: NamespaceBinding = this.scope, + minimizeEmpty: Boolean = this.minimizeEmpty, child: Seq[Node] = this.child.toSeq - ): Elem = Elem(prefix, label, attributes, scope, child: _*) + ): Elem = Elem(prefix, label, attributes, scope, minimizeEmpty, child: _*) /** Returns concatenation of `text(n)` for each child `n`. */ diff --git a/src/library/scala/xml/Node.scala b/src/library/scala/xml/Node.scala old mode 100644 new mode 100755 index 2ead18fe08..02e34e1bdc --- a/src/library/scala/xml/Node.scala +++ b/src/library/scala/xml/Node.scala @@ -159,7 +159,7 @@ abstract class Node extends NodeSeq { * @return ... */ def buildString(stripComments: Boolean): String = - Utility.toXML(this, stripComments = stripComments).toString + Utility.serialize(this, stripComments = stripComments).toString /** * Same as `toString('''false''')`. diff --git a/src/library/scala/xml/PrettyPrinter.scala b/src/library/scala/xml/PrettyPrinter.scala old mode 100644 new mode 100755 index ea39b51352..64dbd00f2f --- a/src/library/scala/xml/PrettyPrinter.scala +++ b/src/library/scala/xml/PrettyPrinter.scala @@ -161,7 +161,7 @@ class PrettyPrinter(width: Int, step: Int) { case _ => val test = { val sb = new StringBuilder() - Utility.toXML(node, pscope, sb, false) + Utility.serialize(node, pscope, sb, false) if (doPreserve(node)) sb.toString else TextBuffer.fromString(sb.toString).toText(0).data } diff --git a/src/library/scala/xml/Utility.scala b/src/library/scala/xml/Utility.scala old mode 100644 new mode 100755 index fc20b892b9..e5644acac8 --- a/src/library/scala/xml/Utility.scala +++ b/src/library/scala/xml/Utility.scala @@ -181,6 +181,14 @@ object Utility extends AnyRef with parsing.TokenTests { // sb.toString() // } + /** + * Serialize the provided Node to the provided StringBuilder. + *

+ * Note that calling this source-compatible method will result in the same old, arguably almost universally unwanted, + * behaviour. + * @deprecated please use {@link #serialize} instead and specify a minimizeTags parameter. + */ + @deprecated def toXML( x: Node, pscope: NamespaceBinding = TopScope, @@ -189,30 +197,54 @@ object Utility extends AnyRef with parsing.TokenTests { decodeEntities: Boolean = true, preserveWhitespace: Boolean = false, minimizeTags: Boolean = false): StringBuilder = + { + serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, if (minimizeTags) MinimizeMode.Always else Mini + } + + /** + * Serialize an XML Node to a StringBuilder. + * + * This is essentially a minor rework of {@link #toXML} that can't have the same name due to an unfortunate + * combination of named/default arguments and overloading. + * + * @todo seriously consider just changing the default to {@link MinimizeMode#Default} so that the serialization is + * transparent by default + * @todo use a Writer instead + */ + def serialize( + x: Node, + pscope: NamespaceBinding = TopScope, + sb: StringBuilder = new StringBuilder, + stripComments: Boolean = false, + decodeEntities: Boolean = true, + preserveWhitespace: Boolean = false, + minimizeTags: MinimizeMode.Value = MinimizeMode.Default): StringBuilder = { x match { - case c: Comment => if (!stripComments) c buildString sb else sb - case x: SpecialNode => x buildString sb - case g: Group => - g.nodes foreach {toXML(_, x.scope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags)} - sb - case _ => + case c: Comment if !stripComments => c buildString sb + case s: SpecialNode => s buildString sb + case g: Group => for (c <- g.nodes) serialize(c, g.scope, sb, minimizeTags = minimizeTags) ; sb + case el: Elem => // print tag with namespace declarations sb.append('<') - x.nameToString(sb) - if (x.attributes ne null) x.attributes.buildString(sb) - x.scope.buildString(sb, pscope) - if (x.child.isEmpty && minimizeTags) { + el.nameToString(sb) + if (el.attributes ne null) el.attributes.buildString(sb) + el.scope.buildString(sb, pscope) + if (el.child.isEmpty && + (minimizeTags == MinimizeMode.Always || + (minimizeTags == MinimizeMode.Default && el.minimizeEmpty))) + { // no children, so use short form: - sb.append(" />") + sb.append("/>") } else { // children, so use long form: ... sb.append('>') - sequenceToXML(x.child, x.scope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + sequenceToXML(el.child, el.scope, sb, stripComments) sb.append("') } + case _ => throw new IllegalArgumentException("Don't know how to serialize a " + x.getClass.getName) } } @@ -223,20 +255,20 @@ object Utility extends AnyRef with parsing.TokenTests { stripComments: Boolean = false, decodeEntities: Boolean = true, preserveWhitespace: Boolean = false, - minimizeTags: Boolean = false): Unit = + minimizeTags: MinimizeMode.Value = MinimizeMode.Default): Unit = { if (children.isEmpty) return else if (children forall isAtomAndNotText) { // add space val it = children.iterator val f = it.next - toXML(f, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + serialize(f, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) while (it.hasNext) { val x = it.next sb.append(' ') - toXML(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) } } - else children foreach { toXML(_, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) } + else children foreach { serialize(_, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) } } /** diff --git a/src/library/scala/xml/XML.scala b/src/library/scala/xml/XML.scala old mode 100644 new mode 100755 index bc3033d081..dfdd71a9ae --- a/src/library/scala/xml/XML.scala +++ b/src/library/scala/xml/XML.scala @@ -26,6 +26,21 @@ object Source def fromSysId(sysID: String) = new InputSource(sysID) def fromString(string: String) = fromReader(new StringReader(string)) } + +/** + * Governs how empty elements (i.e. those without children) should be serialized. + */ +object MinimizeMode extends Enumeration { + /** Minimize empty tags if they were originally empty when parsed, or if they were constructed with {@link Elem#minimizeEmpty} == true */ + val Default = Value + + /** Always minimize empty tags. Note that this may be problematic for XHTML, in which case {@link Xhtml#toXhtml} should be used instead. */ + val Always = Value + + /** Never minimize empty tags. */ + val Never = Value +} + import Source._ /** The object `XML` provides constants, and functions to load @@ -83,10 +98,10 @@ object XML extends XMLLoader[Elem] * @param xmlDecl if true, write xml declaration * @param doctype if not null, write doctype declaration */ - final def write(w: java.io.Writer, node: Node, enc: String, xmlDecl: Boolean, doctype: dtd.DocType) { + final def write(w: java.io.Writer, node: Node, enc: String, xmlDecl: Boolean, doctype: dtd.DocType, minimizeTags: MinimizeMode.Value = MinimizeMode.Default) { /* TODO: optimize by giving writer parameter to toXML*/ if (xmlDecl) w.write("\n") if (doctype ne null) w.write( doctype.toString() + "\n") - w.write(Utility.toXML(node).toString) + w.write(Utility.serialize(node, minimizeTags = minimizeTags).toString) } } diff --git a/src/library/scala/xml/factory/Binder.scala b/src/library/scala/xml/factory/Binder.scala old mode 100644 new mode 100755 index a8b0ed585b..b4fe153bd8 --- a/src/library/scala/xml/factory/Binder.scala +++ b/src/library/scala/xml/factory/Binder.scala @@ -43,13 +43,13 @@ abstract class Binder(val preserveWS: Boolean) extends ValidatingMarkupHandler { result &+ text(0, x.data) case x:EntityRef => result &+ entityRef(0, x.entityName) - case _ => - elemStart(0, n.prefix, n.label, n.attributes, n.scope) + case x:Elem => + elemStart(0, x.prefix, x.label, x.attributes, x.scope) val old = result result = new NodeBuffer() - for (m <- n.child) traverse(m) - result = old &+ elem(0, n.prefix, n.label, n.attributes, n.scope, NodeSeq.fromSeq(result)).toList; - elemEnd(0, n.prefix, n.label) + for (m <- x.child) traverse(m) + result = old &+ elem(0, x.prefix, x.label, x.attributes, x.scope, x.minimizeEmpty, NodeSeq.fromSeq(result)).toList; + elemEnd(0, x.prefix, x.label) } final def validate(n: Node): Node = { diff --git a/src/library/scala/xml/parsing/ConstructingHandler.scala b/src/library/scala/xml/parsing/ConstructingHandler.scala old mode 100644 new mode 100755 index 60c19138c3..7e61674682 --- a/src/library/scala/xml/parsing/ConstructingHandler.scala +++ b/src/library/scala/xml/parsing/ConstructingHandler.scala @@ -21,8 +21,8 @@ abstract class ConstructingHandler extends MarkupHandler val preserveWS: Boolean def elem(pos: Int, pre: String, label: String, attrs: MetaData, - pscope: NamespaceBinding, nodes: NodeSeq): NodeSeq = - Elem(pre, label, attrs, pscope, nodes:_*) + pscope: NamespaceBinding, empty: Boolean, nodes: NodeSeq): NodeSeq = + Elem(pre, label, attrs, pscope, empty, nodes:_*) def procInstr(pos: Int, target: String, txt: String) = ProcInstr(target, txt) diff --git a/src/library/scala/xml/parsing/DefaultMarkupHandler.scala b/src/library/scala/xml/parsing/DefaultMarkupHandler.scala old mode 100644 new mode 100755 index 699c5b2b5f..e0258ba781 --- a/src/library/scala/xml/parsing/DefaultMarkupHandler.scala +++ b/src/library/scala/xml/parsing/DefaultMarkupHandler.scala @@ -16,7 +16,7 @@ package parsing abstract class DefaultMarkupHandler extends MarkupHandler { def elem(pos: Int, pre: String, label: String, attrs: MetaData, - scope:NamespaceBinding, args: NodeSeq) = NodeSeq.Empty + scope:NamespaceBinding, empty: Boolean, args: NodeSeq) = NodeSeq.Empty def procInstr(pos: Int, target: String, txt: String) = NodeSeq.Empty diff --git a/src/library/scala/xml/parsing/MarkupHandler.scala b/src/library/scala/xml/parsing/MarkupHandler.scala old mode 100644 new mode 100755 index 87e785a98f..83db2f177d --- a/src/library/scala/xml/parsing/MarkupHandler.scala +++ b/src/library/scala/xml/parsing/MarkupHandler.scala @@ -75,10 +75,11 @@ abstract class MarkupHandler extends Logged * @param pre the prefix * @param label the local name * @param attrs the attributes (metadata) + * @param empty `true` if the element was previously empty; `false` otherwise. * @param args the children of this element * @return ... */ - def elem(pos: Int, pre: String, label: String, attrs: MetaData, scope: NamespaceBinding, args: NodeSeq): NodeSeq + def elem(pos: Int, pre: String, label: String, attrs: MetaData, scope: NamespaceBinding, empty: Boolean, args: NodeSeq): NodeSeq /** callback method invoked by MarkupParser after parsing PI. */ diff --git a/src/library/scala/xml/parsing/MarkupParser.scala b/src/library/scala/xml/parsing/MarkupParser.scala old mode 100644 new mode 100755 index 1de08b3025..32feaa2209 --- a/src/library/scala/xml/parsing/MarkupParser.scala +++ b/src/library/scala/xml/parsing/MarkupParser.scala @@ -569,7 +569,7 @@ trait MarkupParser extends MarkupParserCommon with TokenTests tmp } } - val res = handle.elem(pos, pre, local, aMap, scope, ts) + val res = handle.elem(pos, pre, local, aMap, scope, ts == NodeSeq.Empty, ts) handle.elemEnd(pos, pre, local) res } diff --git a/src/library/scala/xml/pull/XMLEventReader.scala b/src/library/scala/xml/pull/XMLEventReader.scala index f84d91d138..c764d042c8 100755 --- a/src/library/scala/xml/pull/XMLEventReader.scala +++ b/src/library/scala/xml/pull/XMLEventReader.scala @@ -81,7 +81,7 @@ extends collection.AbstractIterator[XMLEvent] // memory usage optimization return one for top level to satisfy // MarkupParser.document() otherwise NodeSeq.Empty private var ignoreWritten = false - final def elem(pos: Int, pre: String, label: String, attrs: MetaData, pscope: NamespaceBinding, nodes: NodeSeq): NodeSeq = + final def elem(pos: Int, pre: String, label: String, attrs: MetaData, pscope: NamespaceBinding, empty: Boolean, nodes: NodeSeq): NodeSeq = if (level == 1 && !ignoreWritten) {ignoreWritten = true; } else NodeSeq.Empty def procInstr(pos: Int, target: String, txt: String) = setEvent(EvProcInstr(target, txt)) -- cgit v1.2.3 From 5ea83bc80c391b75c3c569b528b9060f76f97aba Mon Sep 17 00:00:00 2001 From: Alex Cruise Date: Fri, 9 Mar 2012 01:13:50 -0800 Subject: Cleaned up failed manual patch --- src/library/scala/xml/Utility.scala | 918 ++++++++++++++++++------------------ 1 file changed, 459 insertions(+), 459 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/xml/Utility.scala b/src/library/scala/xml/Utility.scala index e5644acac8..39d348c535 100755 --- a/src/library/scala/xml/Utility.scala +++ b/src/library/scala/xml/Utility.scala @@ -1,459 +1,459 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -package scala.xml - -import scala.collection.mutable -import parsing.XhtmlEntities - -/** - * The `Utility` object provides utility functions for processing instances - * of bound and not bound XML classes, as well as escaping text nodes. - * - * @author Burak Emir - */ -object Utility extends AnyRef with parsing.TokenTests { - final val SU = '\u001A' - - implicit def implicitSbToString(sb: StringBuilder) = sb.toString() - - // helper for the extremely oft-repeated sequence of creating a - // StringBuilder, passing it around, and then grabbing its String. - private [xml] def sbToString(f: (StringBuilder) => Unit): String = { - val sb = new StringBuilder - f(sb) - sb.toString - } - private[xml] def isAtomAndNotText(x: Node) = x.isAtom && !x.isInstanceOf[Text] - - /** Trims an element - call this method, when you know that it is an - * element (and not a text node) so you know that it will not be trimmed - * away. With this assumption, the function can return a `Node`, rather - * than a `Seq[Node]`. If you don't know, call `trimProper` and account - * for the fact that you may get back an empty sequence of nodes. - * - * Precondition: node is not a text node (it might be trimmed) - */ - def trim(x: Node): Node = x match { - case Elem(pre, lab, md, scp, child@_*) => - Elem(pre, lab, md, scp, (child flatMap trimProper):_*) - } - - /** trim a child of an element. `Attribute` values and `Atom` nodes that - * are not `Text` nodes are unaffected. - */ - def trimProper(x:Node): Seq[Node] = x match { - case Elem(pre,lab,md,scp,child@_*) => - Elem(pre,lab,md,scp, (child flatMap trimProper):_*) - case Text(s) => - new TextBuffer().append(s).toText - case _ => - x - } - - /** returns a sorted attribute list */ - def sort(md: MetaData): MetaData = if((md eq Null) || (md.next eq Null)) md else { - val key = md.key - val smaller = sort(md.filter { m => m.key < key }) - val greater = sort(md.filter { m => m.key > key }) - smaller.copy(md.copy ( greater )) - } - - /** Return the node with its attribute list sorted alphabetically - * (prefixes are ignored) */ - def sort(n:Node): Node = n match { - case Elem(pre,lab,md,scp,child@_*) => - Elem(pre,lab,sort(md),scp, (child map sort):_*) - case _ => n - } - - /** - * Escapes the characters < > & and " from string. - * - * @param text ... - * @return ... - */ - final def escape(text: String): String = sbToString(escape(text, _)) - - object Escapes { - /** For reasons unclear escape and unescape are a long ways from - * being logical inverses. */ - val pairs = Map( - "lt" -> '<', - "gt" -> '>', - "amp" -> '&', - "quot" -> '"' - // enigmatic comment explaining why this isn't escaped -- - // is valid xhtml but not html, and IE doesn't know it, says jweb - // "apos" -> '\'' - ) - val escMap = pairs map { case (s, c) => c-> ("&%s;" format s) } - val unescMap = pairs ++ Map("apos" -> '\'') - } - import Escapes.{ escMap, unescMap } - - /** - * Appends escaped string to `s`. - * - * @param text ... - * @param s ... - * @return ... - */ - final def escape(text: String, s: StringBuilder): StringBuilder = { - // Implemented per XML spec: - // http://www.w3.org/International/questions/qa-controls - // imperative code 3x-4x faster than current implementation - // dpp (David Pollak) 2010/02/03 - val len = text.length - var pos = 0 - while (pos < len) { - text.charAt(pos) match { - case '<' => s.append("<") - case '>' => s.append(">") - case '&' => s.append("&") - case '"' => s.append(""") - case '\n' => s.append('\n') - case '\r' => s.append('\r') - case '\t' => s.append('\t') - case c => if (c >= ' ') s.append(c) - } - - pos += 1 - } - s - } - - /** - * Appends unescaped string to `s`, `amp` becomes `&`, - * `lt` becomes `<` etc.. - * - * @param ref ... - * @param s ... - * @return `'''null'''` if `ref` was not a predefined entity. - */ - final def unescape(ref: String, s: StringBuilder): StringBuilder = - (unescMap get ref) map (s append _) orNull - - /** - * Returns a set of all namespaces used in a sequence of nodes - * and all their descendants, including the empty namespaces. - * - * @param nodes ... - * @return ... - */ - def collectNamespaces(nodes: Seq[Node]): mutable.Set[String] = - nodes.foldLeft(new mutable.HashSet[String]) { (set, x) => collectNamespaces(x, set) ; set } - - /** - * Adds all namespaces in node to set. - * - * @param n ... - * @param set ... - */ - def collectNamespaces(n: Node, set: mutable.Set[String]) { - if (n.doCollectNamespaces) { - set += n.namespace - for (a <- n.attributes) a match { - case _:PrefixedAttribute => - set += a.getNamespace(n) - case _ => - } - for (i <- n.child) - collectNamespaces(i, set) - } - } - - // def toXML( - // x: Node, - // pscope: NamespaceBinding = TopScope, - // sb: StringBuilder = new StringBuilder, - // stripComments: Boolean = false, - // decodeEntities: Boolean = true, - // preserveWhitespace: Boolean = false, - // minimizeTags: Boolean = false): String = - // { - // toXMLsb(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) - // sb.toString() - // } - - /** - * Serialize the provided Node to the provided StringBuilder. - *

- * Note that calling this source-compatible method will result in the same old, arguably almost universally unwanted, - * behaviour. - * @deprecated please use {@link #serialize} instead and specify a minimizeTags parameter. - */ - @deprecated - def toXML( - x: Node, - pscope: NamespaceBinding = TopScope, - sb: StringBuilder = new StringBuilder, - stripComments: Boolean = false, - decodeEntities: Boolean = true, - preserveWhitespace: Boolean = false, - minimizeTags: Boolean = false): StringBuilder = - { - serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, if (minimizeTags) MinimizeMode.Always else Mini - } - - /** - * Serialize an XML Node to a StringBuilder. - * - * This is essentially a minor rework of {@link #toXML} that can't have the same name due to an unfortunate - * combination of named/default arguments and overloading. - * - * @todo seriously consider just changing the default to {@link MinimizeMode#Default} so that the serialization is - * transparent by default - * @todo use a Writer instead - */ - def serialize( - x: Node, - pscope: NamespaceBinding = TopScope, - sb: StringBuilder = new StringBuilder, - stripComments: Boolean = false, - decodeEntities: Boolean = true, - preserveWhitespace: Boolean = false, - minimizeTags: MinimizeMode.Value = MinimizeMode.Default): StringBuilder = - { - x match { - case c: Comment if !stripComments => c buildString sb - case s: SpecialNode => s buildString sb - case g: Group => for (c <- g.nodes) serialize(c, g.scope, sb, minimizeTags = minimizeTags) ; sb - case el: Elem => - // print tag with namespace declarations - sb.append('<') - el.nameToString(sb) - if (el.attributes ne null) el.attributes.buildString(sb) - el.scope.buildString(sb, pscope) - if (el.child.isEmpty && - (minimizeTags == MinimizeMode.Always || - (minimizeTags == MinimizeMode.Default && el.minimizeEmpty))) - { - // no children, so use short form: - sb.append("/>") - } else { - // children, so use long form: ... - sb.append('>') - sequenceToXML(el.child, el.scope, sb, stripComments) - sb.append("') - } - case _ => throw new IllegalArgumentException("Don't know how to serialize a " + x.getClass.getName) - } - } - - def sequenceToXML( - children: Seq[Node], - pscope: NamespaceBinding = TopScope, - sb: StringBuilder = new StringBuilder, - stripComments: Boolean = false, - decodeEntities: Boolean = true, - preserveWhitespace: Boolean = false, - minimizeTags: MinimizeMode.Value = MinimizeMode.Default): Unit = - { - if (children.isEmpty) return - else if (children forall isAtomAndNotText) { // add space - val it = children.iterator - val f = it.next - serialize(f, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) - while (it.hasNext) { - val x = it.next - sb.append(' ') - serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) - } - } - else children foreach { serialize(_, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) } - } - - /** - * Returns prefix of qualified name if any. - * - * @param name ... - * @return ... - */ - final def prefix(name: String): Option[String] = (name indexOf ':') match { - case -1 => None - case i => Some(name.substring(0, i)) - } - - /** - * Returns a hashcode for the given constituents of a node - * - * @param uri - * @param label - * @param attribHashCode - * @param children - */ - def hashCode(pre: String, label: String, attribHashCode: Int, scpeHash: Int, children: Seq[Node]) = - scala.util.MurmurHash3.orderedHash(label +: attribHashCode +: scpeHash +: children, pre.##) - - def appendQuoted(s: String): String = sbToString(appendQuoted(s, _)) - - /** - * Appends "s" if string `s` does not contain ", - * 's' otherwise. - * - * @param s ... - * @param sb ... - * @return ... - */ - def appendQuoted(s: String, sb: StringBuilder) = { - val ch = if (s contains '"') '\'' else '"' - sb.append(ch).append(s).append(ch) - } - - /** - * Appends "s" and escapes and " i s with \" - * - * @param s ... - * @param sb ... - * @return ... - */ - def appendEscapedQuoted(s: String, sb: StringBuilder): StringBuilder = { - sb.append('"') - for (c <- s) c match { - case '"' => sb.append('\\'); sb.append('"') - case _ => sb.append(c) - } - sb.append('"') - } - - /** - * @param s ... - * @param index ... - * @return ... - */ - def getName(s: String, index: Int): String = { - if (index >= s.length) null - else { - val xs = s drop index - if (xs.nonEmpty && isNameStart(xs.head)) xs takeWhile isNameChar - else "" - } - } - - /** - * Returns `'''null'''` if the value is a correct attribute value, - * error message if it isn't. - * - * @param value ... - * @return ... - */ - def checkAttributeValue(value: String): String = { - var i = 0 - while (i < value.length) { - value.charAt(i) match { - case '<' => - return "< not allowed in attribute value"; - case '&' => - val n = getName(value, i+1) - if (n eq null) - return "malformed entity reference in attribute value ["+value+"]"; - i = i + n.length + 1 - if (i >= value.length || value.charAt(i) != ';') - return "malformed entity reference in attribute value ["+value+"]"; - case _ => - } - i = i + 1 - } - null - } - - /** - * new - * - * @param value ... - * @return ... - */ - def parseAttributeValue(value: String): Seq[Node] = { - val sb = new StringBuilder - var rfb: StringBuilder = null - val nb = new NodeBuffer() - - val it = value.iterator - while (it.hasNext) { - var c = it.next - // entity! flush buffer into text node - if (c == '&') { - c = it.next - if (c == '#') { - c = it.next - val theChar = parseCharRef ({ ()=> c },{ () => c = it.next },{s => throw new RuntimeException(s)}, {s => throw new RuntimeException(s)}) - sb.append(theChar) - } - else { - if (rfb eq null) rfb = new StringBuilder() - rfb append c - c = it.next - while (c != ';') { - rfb.append(c) - c = it.next - } - val ref = rfb.toString() - rfb.clear() - unescape(ref,sb) match { - case null => - if (sb.length > 0) { // flush buffer - nb += Text(sb.toString()) - sb.clear() - } - nb += EntityRef(ref) // add entityref - case _ => - } - } - } - else sb append c - } - if (sb.length > 0) { // flush buffer - val x = Text(sb.toString()) - if (nb.length == 0) - return x - else - nb += x - } - nb - } - - /** - * {{{ - * CharRef ::= "&#" '0'..'9' {'0'..'9'} ";" - * | "&#x" '0'..'9'|'A'..'F'|'a'..'f' { hexdigit } ";" - * }}} - * See [66] - * - * @param ch ... - * @param nextch ... - * @param reportSyntaxError ... - * @return ... - */ - def parseCharRef(ch: () => Char, nextch: () => Unit, reportSyntaxError: String => Unit, reportTruncatedError: String => Unit): String = { - val hex = (ch() == 'x') && { nextch(); true } - val base = if (hex) 16 else 10 - var i = 0 - while (ch() != ';') { - ch() match { - case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => - i = i * base + ch().asDigit - case 'a' | 'b' | 'c' | 'd' | 'e' | 'f' - | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' => - if (! hex) - reportSyntaxError("hex char not allowed in decimal char ref\n" + - "Did you mean to write &#x ?") - else - i = i * base + ch().asDigit - case SU => - reportTruncatedError("") - case _ => - reportSyntaxError("character '" + ch() + "' not allowed in char ref\n") - } - nextch() - } - new String(Array(i), 0, 1) - } -} +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.xml + +import scala.collection.mutable +import parsing.XhtmlEntities + +/** + * The `Utility` object provides utility functions for processing instances + * of bound and not bound XML classes, as well as escaping text nodes. + * + * @author Burak Emir + */ +object Utility extends AnyRef with parsing.TokenTests { + final val SU = '\u001A' + + implicit def implicitSbToString(sb: StringBuilder) = sb.toString() + + // helper for the extremely oft-repeated sequence of creating a + // StringBuilder, passing it around, and then grabbing its String. + private [xml] def sbToString(f: (StringBuilder) => Unit): String = { + val sb = new StringBuilder + f(sb) + sb.toString + } + private[xml] def isAtomAndNotText(x: Node) = x.isAtom && !x.isInstanceOf[Text] + + /** Trims an element - call this method, when you know that it is an + * element (and not a text node) so you know that it will not be trimmed + * away. With this assumption, the function can return a `Node`, rather + * than a `Seq[Node]`. If you don't know, call `trimProper` and account + * for the fact that you may get back an empty sequence of nodes. + * + * Precondition: node is not a text node (it might be trimmed) + */ + def trim(x: Node): Node = x match { + case Elem(pre, lab, md, scp, child@_*) => + Elem(pre, lab, md, scp, (child flatMap trimProper):_*) + } + + /** trim a child of an element. `Attribute` values and `Atom` nodes that + * are not `Text` nodes are unaffected. + */ + def trimProper(x:Node): Seq[Node] = x match { + case Elem(pre,lab,md,scp,child@_*) => + Elem(pre,lab,md,scp, (child flatMap trimProper):_*) + case Text(s) => + new TextBuffer().append(s).toText + case _ => + x + } + + /** returns a sorted attribute list */ + def sort(md: MetaData): MetaData = if((md eq Null) || (md.next eq Null)) md else { + val key = md.key + val smaller = sort(md.filter { m => m.key < key }) + val greater = sort(md.filter { m => m.key > key }) + smaller.copy(md.copy ( greater )) + } + + /** Return the node with its attribute list sorted alphabetically + * (prefixes are ignored) */ + def sort(n:Node): Node = n match { + case Elem(pre,lab,md,scp,child@_*) => + Elem(pre,lab,sort(md),scp, (child map sort):_*) + case _ => n + } + + /** + * Escapes the characters < > & and " from string. + * + * @param text ... + * @return ... + */ + final def escape(text: String): String = sbToString(escape(text, _)) + + object Escapes { + /** For reasons unclear escape and unescape are a long ways from + * being logical inverses. */ + val pairs = Map( + "lt" -> '<', + "gt" -> '>', + "amp" -> '&', + "quot" -> '"' + // enigmatic comment explaining why this isn't escaped -- + // is valid xhtml but not html, and IE doesn't know it, says jweb + // "apos" -> '\'' + ) + val escMap = pairs map { case (s, c) => c-> ("&%s;" format s) } + val unescMap = pairs ++ Map("apos" -> '\'') + } + import Escapes.{ escMap, unescMap } + + /** + * Appends escaped string to `s`. + * + * @param text ... + * @param s ... + * @return ... + */ + final def escape(text: String, s: StringBuilder): StringBuilder = { + // Implemented per XML spec: + // http://www.w3.org/International/questions/qa-controls + // imperative code 3x-4x faster than current implementation + // dpp (David Pollak) 2010/02/03 + val len = text.length + var pos = 0 + while (pos < len) { + text.charAt(pos) match { + case '<' => s.append("<") + case '>' => s.append(">") + case '&' => s.append("&") + case '"' => s.append(""") + case '\n' => s.append('\n') + case '\r' => s.append('\r') + case '\t' => s.append('\t') + case c => if (c >= ' ') s.append(c) + } + + pos += 1 + } + s + } + + /** + * Appends unescaped string to `s`, `amp` becomes `&`, + * `lt` becomes `<` etc.. + * + * @param ref ... + * @param s ... + * @return `'''null'''` if `ref` was not a predefined entity. + */ + final def unescape(ref: String, s: StringBuilder): StringBuilder = + (unescMap get ref) map (s append _) orNull + + /** + * Returns a set of all namespaces used in a sequence of nodes + * and all their descendants, including the empty namespaces. + * + * @param nodes ... + * @return ... + */ + def collectNamespaces(nodes: Seq[Node]): mutable.Set[String] = + nodes.foldLeft(new mutable.HashSet[String]) { (set, x) => collectNamespaces(x, set) ; set } + + /** + * Adds all namespaces in node to set. + * + * @param n ... + * @param set ... + */ + def collectNamespaces(n: Node, set: mutable.Set[String]) { + if (n.doCollectNamespaces) { + set += n.namespace + for (a <- n.attributes) a match { + case _:PrefixedAttribute => + set += a.getNamespace(n) + case _ => + } + for (i <- n.child) + collectNamespaces(i, set) + } + } + + // def toXML( + // x: Node, + // pscope: NamespaceBinding = TopScope, + // sb: StringBuilder = new StringBuilder, + // stripComments: Boolean = false, + // decodeEntities: Boolean = true, + // preserveWhitespace: Boolean = false, + // minimizeTags: Boolean = false): String = + // { + // toXMLsb(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + // sb.toString() + // } + + /** + * Serialize the provided Node to the provided StringBuilder. + *

+ * Note that calling this source-compatible method will result in the same old, arguably almost universally unwanted, + * behaviour. + * @deprecated please use {@link #serialize} instead and specify a minimizeTags parameter. + */ + @deprecated + def toXML( + x: Node, + pscope: NamespaceBinding = TopScope, + sb: StringBuilder = new StringBuilder, + stripComments: Boolean = false, + decodeEntities: Boolean = true, + preserveWhitespace: Boolean = false, + minimizeTags: Boolean = false): StringBuilder = + { + serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, if (minimizeTags) MinimizeMode.Always else MinimizeMode.Never) + } + + /** + * Serialize an XML Node to a StringBuilder. + * + * This is essentially a minor rework of {@link #toXML} that can't have the same name due to an unfortunate + * combination of named/default arguments and overloading. + * + * @todo seriously consider just changing the default to {@link MinimizeMode#Default} so that the serialization is + * transparent by default + * @todo use a Writer instead + */ + def serialize( + x: Node, + pscope: NamespaceBinding = TopScope, + sb: StringBuilder = new StringBuilder, + stripComments: Boolean = false, + decodeEntities: Boolean = true, + preserveWhitespace: Boolean = false, + minimizeTags: MinimizeMode.Value = MinimizeMode.Default): StringBuilder = + { + x match { + case c: Comment if !stripComments => c buildString sb + case s: SpecialNode => s buildString sb + case g: Group => for (c <- g.nodes) serialize(c, g.scope, sb, minimizeTags = minimizeTags) ; sb + case el: Elem => + // print tag with namespace declarations + sb.append('<') + el.nameToString(sb) + if (el.attributes ne null) el.attributes.buildString(sb) + el.scope.buildString(sb, pscope) + if (el.child.isEmpty && + (minimizeTags == MinimizeMode.Always || + (minimizeTags == MinimizeMode.Default && el.minimizeEmpty))) + { + // no children, so use short form: + sb.append("/>") + } else { + // children, so use long form: ... + sb.append('>') + sequenceToXML(el.child, el.scope, sb, stripComments) + sb.append("') + } + case _ => throw new IllegalArgumentException("Don't know how to serialize a " + x.getClass.getName) + } + } + + def sequenceToXML( + children: Seq[Node], + pscope: NamespaceBinding = TopScope, + sb: StringBuilder = new StringBuilder, + stripComments: Boolean = false, + decodeEntities: Boolean = true, + preserveWhitespace: Boolean = false, + minimizeTags: MinimizeMode.Value = MinimizeMode.Default): Unit = + { + if (children.isEmpty) return + else if (children forall isAtomAndNotText) { // add space + val it = children.iterator + val f = it.next + serialize(f, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + while (it.hasNext) { + val x = it.next + sb.append(' ') + serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + } + } + else children foreach { serialize(_, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) } + } + + /** + * Returns prefix of qualified name if any. + * + * @param name ... + * @return ... + */ + final def prefix(name: String): Option[String] = (name indexOf ':') match { + case -1 => None + case i => Some(name.substring(0, i)) + } + + /** + * Returns a hashcode for the given constituents of a node + * + * @param uri + * @param label + * @param attribHashCode + * @param children + */ + def hashCode(pre: String, label: String, attribHashCode: Int, scpeHash: Int, children: Seq[Node]) = + scala.util.MurmurHash3.orderedHash(label +: attribHashCode +: scpeHash +: children, pre.##) + + def appendQuoted(s: String): String = sbToString(appendQuoted(s, _)) + + /** + * Appends "s" if string `s` does not contain ", + * 's' otherwise. + * + * @param s ... + * @param sb ... + * @return ... + */ + def appendQuoted(s: String, sb: StringBuilder) = { + val ch = if (s contains '"') '\'' else '"' + sb.append(ch).append(s).append(ch) + } + + /** + * Appends "s" and escapes and " i s with \" + * + * @param s ... + * @param sb ... + * @return ... + */ + def appendEscapedQuoted(s: String, sb: StringBuilder): StringBuilder = { + sb.append('"') + for (c <- s) c match { + case '"' => sb.append('\\'); sb.append('"') + case _ => sb.append(c) + } + sb.append('"') + } + + /** + * @param s ... + * @param index ... + * @return ... + */ + def getName(s: String, index: Int): String = { + if (index >= s.length) null + else { + val xs = s drop index + if (xs.nonEmpty && isNameStart(xs.head)) xs takeWhile isNameChar + else "" + } + } + + /** + * Returns `'''null'''` if the value is a correct attribute value, + * error message if it isn't. + * + * @param value ... + * @return ... + */ + def checkAttributeValue(value: String): String = { + var i = 0 + while (i < value.length) { + value.charAt(i) match { + case '<' => + return "< not allowed in attribute value"; + case '&' => + val n = getName(value, i+1) + if (n eq null) + return "malformed entity reference in attribute value ["+value+"]"; + i = i + n.length + 1 + if (i >= value.length || value.charAt(i) != ';') + return "malformed entity reference in attribute value ["+value+"]"; + case _ => + } + i = i + 1 + } + null + } + + /** + * new + * + * @param value ... + * @return ... + */ + def parseAttributeValue(value: String): Seq[Node] = { + val sb = new StringBuilder + var rfb: StringBuilder = null + val nb = new NodeBuffer() + + val it = value.iterator + while (it.hasNext) { + var c = it.next + // entity! flush buffer into text node + if (c == '&') { + c = it.next + if (c == '#') { + c = it.next + val theChar = parseCharRef ({ ()=> c },{ () => c = it.next },{s => throw new RuntimeException(s)}, {s => throw new RuntimeException(s)}) + sb.append(theChar) + } + else { + if (rfb eq null) rfb = new StringBuilder() + rfb append c + c = it.next + while (c != ';') { + rfb.append(c) + c = it.next + } + val ref = rfb.toString() + rfb.clear() + unescape(ref,sb) match { + case null => + if (sb.length > 0) { // flush buffer + nb += Text(sb.toString()) + sb.clear() + } + nb += EntityRef(ref) // add entityref + case _ => + } + } + } + else sb append c + } + if (sb.length > 0) { // flush buffer + val x = Text(sb.toString()) + if (nb.length == 0) + return x + else + nb += x + } + nb + } + + /** + * {{{ + * CharRef ::= "&#" '0'..'9' {'0'..'9'} ";" + * | "&#x" '0'..'9'|'A'..'F'|'a'..'f' { hexdigit } ";" + * }}} + * See [66] + * + * @param ch ... + * @param nextch ... + * @param reportSyntaxError ... + * @return ... + */ + def parseCharRef(ch: () => Char, nextch: () => Unit, reportSyntaxError: String => Unit, reportTruncatedError: String => Unit): String = { + val hex = (ch() == 'x') && { nextch(); true } + val base = if (hex) 16 else 10 + var i = 0 + while (ch() != ';') { + ch() match { + case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => + i = i * base + ch().asDigit + case 'a' | 'b' | 'c' | 'd' | 'e' | 'f' + | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' => + if (! hex) + reportSyntaxError("hex char not allowed in decimal char ref\n" + + "Did you mean to write &#x ?") + else + i = i * base + ch().asDigit + case SU => + reportTruncatedError("") + case _ => + reportSyntaxError("character '" + ch() + "' not allowed in char ref\n") + } + nextch() + } + new String(Array(i), 0, 1) + } +} -- cgit v1.2.3 From e533b2672b8c7e558e27fc264e714d656adf38b2 Mon Sep 17 00:00:00 2001 From: Alex Cruise Date: Mon, 12 Mar 2012 13:59:28 -0700 Subject: SI-1118: * Use new-style deprecation annotations * Slightly less cutesy test text * Move t1118.scala to the right directory --- src/library/scala/xml/Utility.scala | 915 ++++++++++++++++----------------- src/library/scala/xml/XML.scala | 6 +- test/files/jvm/deprecation/t1118.scala | 21 - test/files/jvm/t1118.check | 20 +- test/files/jvm/t1118.scala | 21 + 5 files changed, 490 insertions(+), 493 deletions(-) delete mode 100755 test/files/jvm/deprecation/t1118.scala create mode 100755 test/files/jvm/t1118.scala (limited to 'src/library') diff --git a/src/library/scala/xml/Utility.scala b/src/library/scala/xml/Utility.scala index 39d348c535..fce6e7e897 100755 --- a/src/library/scala/xml/Utility.scala +++ b/src/library/scala/xml/Utility.scala @@ -1,459 +1,456 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -package scala.xml - -import scala.collection.mutable -import parsing.XhtmlEntities - -/** - * The `Utility` object provides utility functions for processing instances - * of bound and not bound XML classes, as well as escaping text nodes. - * - * @author Burak Emir - */ -object Utility extends AnyRef with parsing.TokenTests { - final val SU = '\u001A' - - implicit def implicitSbToString(sb: StringBuilder) = sb.toString() - - // helper for the extremely oft-repeated sequence of creating a - // StringBuilder, passing it around, and then grabbing its String. - private [xml] def sbToString(f: (StringBuilder) => Unit): String = { - val sb = new StringBuilder - f(sb) - sb.toString - } - private[xml] def isAtomAndNotText(x: Node) = x.isAtom && !x.isInstanceOf[Text] - - /** Trims an element - call this method, when you know that it is an - * element (and not a text node) so you know that it will not be trimmed - * away. With this assumption, the function can return a `Node`, rather - * than a `Seq[Node]`. If you don't know, call `trimProper` and account - * for the fact that you may get back an empty sequence of nodes. - * - * Precondition: node is not a text node (it might be trimmed) - */ - def trim(x: Node): Node = x match { - case Elem(pre, lab, md, scp, child@_*) => - Elem(pre, lab, md, scp, (child flatMap trimProper):_*) - } - - /** trim a child of an element. `Attribute` values and `Atom` nodes that - * are not `Text` nodes are unaffected. - */ - def trimProper(x:Node): Seq[Node] = x match { - case Elem(pre,lab,md,scp,child@_*) => - Elem(pre,lab,md,scp, (child flatMap trimProper):_*) - case Text(s) => - new TextBuffer().append(s).toText - case _ => - x - } - - /** returns a sorted attribute list */ - def sort(md: MetaData): MetaData = if((md eq Null) || (md.next eq Null)) md else { - val key = md.key - val smaller = sort(md.filter { m => m.key < key }) - val greater = sort(md.filter { m => m.key > key }) - smaller.copy(md.copy ( greater )) - } - - /** Return the node with its attribute list sorted alphabetically - * (prefixes are ignored) */ - def sort(n:Node): Node = n match { - case Elem(pre,lab,md,scp,child@_*) => - Elem(pre,lab,sort(md),scp, (child map sort):_*) - case _ => n - } - - /** - * Escapes the characters < > & and " from string. - * - * @param text ... - * @return ... - */ - final def escape(text: String): String = sbToString(escape(text, _)) - - object Escapes { - /** For reasons unclear escape and unescape are a long ways from - * being logical inverses. */ - val pairs = Map( - "lt" -> '<', - "gt" -> '>', - "amp" -> '&', - "quot" -> '"' - // enigmatic comment explaining why this isn't escaped -- - // is valid xhtml but not html, and IE doesn't know it, says jweb - // "apos" -> '\'' - ) - val escMap = pairs map { case (s, c) => c-> ("&%s;" format s) } - val unescMap = pairs ++ Map("apos" -> '\'') - } - import Escapes.{ escMap, unescMap } - - /** - * Appends escaped string to `s`. - * - * @param text ... - * @param s ... - * @return ... - */ - final def escape(text: String, s: StringBuilder): StringBuilder = { - // Implemented per XML spec: - // http://www.w3.org/International/questions/qa-controls - // imperative code 3x-4x faster than current implementation - // dpp (David Pollak) 2010/02/03 - val len = text.length - var pos = 0 - while (pos < len) { - text.charAt(pos) match { - case '<' => s.append("<") - case '>' => s.append(">") - case '&' => s.append("&") - case '"' => s.append(""") - case '\n' => s.append('\n') - case '\r' => s.append('\r') - case '\t' => s.append('\t') - case c => if (c >= ' ') s.append(c) - } - - pos += 1 - } - s - } - - /** - * Appends unescaped string to `s`, `amp` becomes `&`, - * `lt` becomes `<` etc.. - * - * @param ref ... - * @param s ... - * @return `'''null'''` if `ref` was not a predefined entity. - */ - final def unescape(ref: String, s: StringBuilder): StringBuilder = - (unescMap get ref) map (s append _) orNull - - /** - * Returns a set of all namespaces used in a sequence of nodes - * and all their descendants, including the empty namespaces. - * - * @param nodes ... - * @return ... - */ - def collectNamespaces(nodes: Seq[Node]): mutable.Set[String] = - nodes.foldLeft(new mutable.HashSet[String]) { (set, x) => collectNamespaces(x, set) ; set } - - /** - * Adds all namespaces in node to set. - * - * @param n ... - * @param set ... - */ - def collectNamespaces(n: Node, set: mutable.Set[String]) { - if (n.doCollectNamespaces) { - set += n.namespace - for (a <- n.attributes) a match { - case _:PrefixedAttribute => - set += a.getNamespace(n) - case _ => - } - for (i <- n.child) - collectNamespaces(i, set) - } - } - - // def toXML( - // x: Node, - // pscope: NamespaceBinding = TopScope, - // sb: StringBuilder = new StringBuilder, - // stripComments: Boolean = false, - // decodeEntities: Boolean = true, - // preserveWhitespace: Boolean = false, - // minimizeTags: Boolean = false): String = - // { - // toXMLsb(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) - // sb.toString() - // } - - /** - * Serialize the provided Node to the provided StringBuilder. - *

- * Note that calling this source-compatible method will result in the same old, arguably almost universally unwanted, - * behaviour. - * @deprecated please use {@link #serialize} instead and specify a minimizeTags parameter. - */ - @deprecated - def toXML( - x: Node, - pscope: NamespaceBinding = TopScope, - sb: StringBuilder = new StringBuilder, - stripComments: Boolean = false, - decodeEntities: Boolean = true, - preserveWhitespace: Boolean = false, - minimizeTags: Boolean = false): StringBuilder = - { - serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, if (minimizeTags) MinimizeMode.Always else MinimizeMode.Never) - } - - /** - * Serialize an XML Node to a StringBuilder. - * - * This is essentially a minor rework of {@link #toXML} that can't have the same name due to an unfortunate - * combination of named/default arguments and overloading. - * - * @todo seriously consider just changing the default to {@link MinimizeMode#Default} so that the serialization is - * transparent by default - * @todo use a Writer instead - */ - def serialize( - x: Node, - pscope: NamespaceBinding = TopScope, - sb: StringBuilder = new StringBuilder, - stripComments: Boolean = false, - decodeEntities: Boolean = true, - preserveWhitespace: Boolean = false, - minimizeTags: MinimizeMode.Value = MinimizeMode.Default): StringBuilder = - { - x match { - case c: Comment if !stripComments => c buildString sb - case s: SpecialNode => s buildString sb - case g: Group => for (c <- g.nodes) serialize(c, g.scope, sb, minimizeTags = minimizeTags) ; sb - case el: Elem => - // print tag with namespace declarations - sb.append('<') - el.nameToString(sb) - if (el.attributes ne null) el.attributes.buildString(sb) - el.scope.buildString(sb, pscope) - if (el.child.isEmpty && - (minimizeTags == MinimizeMode.Always || - (minimizeTags == MinimizeMode.Default && el.minimizeEmpty))) - { - // no children, so use short form: - sb.append("/>") - } else { - // children, so use long form: ... - sb.append('>') - sequenceToXML(el.child, el.scope, sb, stripComments) - sb.append("') - } - case _ => throw new IllegalArgumentException("Don't know how to serialize a " + x.getClass.getName) - } - } - - def sequenceToXML( - children: Seq[Node], - pscope: NamespaceBinding = TopScope, - sb: StringBuilder = new StringBuilder, - stripComments: Boolean = false, - decodeEntities: Boolean = true, - preserveWhitespace: Boolean = false, - minimizeTags: MinimizeMode.Value = MinimizeMode.Default): Unit = - { - if (children.isEmpty) return - else if (children forall isAtomAndNotText) { // add space - val it = children.iterator - val f = it.next - serialize(f, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) - while (it.hasNext) { - val x = it.next - sb.append(' ') - serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) - } - } - else children foreach { serialize(_, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) } - } - - /** - * Returns prefix of qualified name if any. - * - * @param name ... - * @return ... - */ - final def prefix(name: String): Option[String] = (name indexOf ':') match { - case -1 => None - case i => Some(name.substring(0, i)) - } - - /** - * Returns a hashcode for the given constituents of a node - * - * @param uri - * @param label - * @param attribHashCode - * @param children - */ - def hashCode(pre: String, label: String, attribHashCode: Int, scpeHash: Int, children: Seq[Node]) = - scala.util.MurmurHash3.orderedHash(label +: attribHashCode +: scpeHash +: children, pre.##) - - def appendQuoted(s: String): String = sbToString(appendQuoted(s, _)) - - /** - * Appends "s" if string `s` does not contain ", - * 's' otherwise. - * - * @param s ... - * @param sb ... - * @return ... - */ - def appendQuoted(s: String, sb: StringBuilder) = { - val ch = if (s contains '"') '\'' else '"' - sb.append(ch).append(s).append(ch) - } - - /** - * Appends "s" and escapes and " i s with \" - * - * @param s ... - * @param sb ... - * @return ... - */ - def appendEscapedQuoted(s: String, sb: StringBuilder): StringBuilder = { - sb.append('"') - for (c <- s) c match { - case '"' => sb.append('\\'); sb.append('"') - case _ => sb.append(c) - } - sb.append('"') - } - - /** - * @param s ... - * @param index ... - * @return ... - */ - def getName(s: String, index: Int): String = { - if (index >= s.length) null - else { - val xs = s drop index - if (xs.nonEmpty && isNameStart(xs.head)) xs takeWhile isNameChar - else "" - } - } - - /** - * Returns `'''null'''` if the value is a correct attribute value, - * error message if it isn't. - * - * @param value ... - * @return ... - */ - def checkAttributeValue(value: String): String = { - var i = 0 - while (i < value.length) { - value.charAt(i) match { - case '<' => - return "< not allowed in attribute value"; - case '&' => - val n = getName(value, i+1) - if (n eq null) - return "malformed entity reference in attribute value ["+value+"]"; - i = i + n.length + 1 - if (i >= value.length || value.charAt(i) != ';') - return "malformed entity reference in attribute value ["+value+"]"; - case _ => - } - i = i + 1 - } - null - } - - /** - * new - * - * @param value ... - * @return ... - */ - def parseAttributeValue(value: String): Seq[Node] = { - val sb = new StringBuilder - var rfb: StringBuilder = null - val nb = new NodeBuffer() - - val it = value.iterator - while (it.hasNext) { - var c = it.next - // entity! flush buffer into text node - if (c == '&') { - c = it.next - if (c == '#') { - c = it.next - val theChar = parseCharRef ({ ()=> c },{ () => c = it.next },{s => throw new RuntimeException(s)}, {s => throw new RuntimeException(s)}) - sb.append(theChar) - } - else { - if (rfb eq null) rfb = new StringBuilder() - rfb append c - c = it.next - while (c != ';') { - rfb.append(c) - c = it.next - } - val ref = rfb.toString() - rfb.clear() - unescape(ref,sb) match { - case null => - if (sb.length > 0) { // flush buffer - nb += Text(sb.toString()) - sb.clear() - } - nb += EntityRef(ref) // add entityref - case _ => - } - } - } - else sb append c - } - if (sb.length > 0) { // flush buffer - val x = Text(sb.toString()) - if (nb.length == 0) - return x - else - nb += x - } - nb - } - - /** - * {{{ - * CharRef ::= "&#" '0'..'9' {'0'..'9'} ";" - * | "&#x" '0'..'9'|'A'..'F'|'a'..'f' { hexdigit } ";" - * }}} - * See [66] - * - * @param ch ... - * @param nextch ... - * @param reportSyntaxError ... - * @return ... - */ - def parseCharRef(ch: () => Char, nextch: () => Unit, reportSyntaxError: String => Unit, reportTruncatedError: String => Unit): String = { - val hex = (ch() == 'x') && { nextch(); true } - val base = if (hex) 16 else 10 - var i = 0 - while (ch() != ';') { - ch() match { - case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => - i = i * base + ch().asDigit - case 'a' | 'b' | 'c' | 'd' | 'e' | 'f' - | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' => - if (! hex) - reportSyntaxError("hex char not allowed in decimal char ref\n" + - "Did you mean to write &#x ?") - else - i = i * base + ch().asDigit - case SU => - reportTruncatedError("") - case _ => - reportSyntaxError("character '" + ch() + "' not allowed in char ref\n") - } - nextch() - } - new String(Array(i), 0, 1) - } -} +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.xml + +import scala.collection.mutable +import parsing.XhtmlEntities + +/** + * The `Utility` object provides utility functions for processing instances + * of bound and not bound XML classes, as well as escaping text nodes. + * + * @author Burak Emir + */ +object Utility extends AnyRef with parsing.TokenTests { + final val SU = '\u001A' + + implicit def implicitSbToString(sb: StringBuilder) = sb.toString() + + // helper for the extremely oft-repeated sequence of creating a + // StringBuilder, passing it around, and then grabbing its String. + private [xml] def sbToString(f: (StringBuilder) => Unit): String = { + val sb = new StringBuilder + f(sb) + sb.toString + } + private[xml] def isAtomAndNotText(x: Node) = x.isAtom && !x.isInstanceOf[Text] + + /** Trims an element - call this method, when you know that it is an + * element (and not a text node) so you know that it will not be trimmed + * away. With this assumption, the function can return a `Node`, rather + * than a `Seq[Node]`. If you don't know, call `trimProper` and account + * for the fact that you may get back an empty sequence of nodes. + * + * Precondition: node is not a text node (it might be trimmed) + */ + def trim(x: Node): Node = x match { + case Elem(pre, lab, md, scp, child@_*) => + Elem(pre, lab, md, scp, (child flatMap trimProper):_*) + } + + /** trim a child of an element. `Attribute` values and `Atom` nodes that + * are not `Text` nodes are unaffected. + */ + def trimProper(x:Node): Seq[Node] = x match { + case Elem(pre,lab,md,scp,child@_*) => + Elem(pre,lab,md,scp, (child flatMap trimProper):_*) + case Text(s) => + new TextBuffer().append(s).toText + case _ => + x + } + + /** returns a sorted attribute list */ + def sort(md: MetaData): MetaData = if((md eq Null) || (md.next eq Null)) md else { + val key = md.key + val smaller = sort(md.filter { m => m.key < key }) + val greater = sort(md.filter { m => m.key > key }) + smaller.copy(md.copy ( greater )) + } + + /** Return the node with its attribute list sorted alphabetically + * (prefixes are ignored) */ + def sort(n:Node): Node = n match { + case Elem(pre,lab,md,scp,child@_*) => + Elem(pre,lab,sort(md),scp, (child map sort):_*) + case _ => n + } + + /** + * Escapes the characters < > & and " from string. + * + * @param text ... + * @return ... + */ + final def escape(text: String): String = sbToString(escape(text, _)) + + object Escapes { + /** For reasons unclear escape and unescape are a long ways from + * being logical inverses. */ + val pairs = Map( + "lt" -> '<', + "gt" -> '>', + "amp" -> '&', + "quot" -> '"' + // enigmatic comment explaining why this isn't escaped -- + // is valid xhtml but not html, and IE doesn't know it, says jweb + // "apos" -> '\'' + ) + val escMap = pairs map { case (s, c) => c-> ("&%s;" format s) } + val unescMap = pairs ++ Map("apos" -> '\'') + } + import Escapes.{ escMap, unescMap } + + /** + * Appends escaped string to `s`. + * + * @param text ... + * @param s ... + * @return ... + */ + final def escape(text: String, s: StringBuilder): StringBuilder = { + // Implemented per XML spec: + // http://www.w3.org/International/questions/qa-controls + // imperative code 3x-4x faster than current implementation + // dpp (David Pollak) 2010/02/03 + val len = text.length + var pos = 0 + while (pos < len) { + text.charAt(pos) match { + case '<' => s.append("<") + case '>' => s.append(">") + case '&' => s.append("&") + case '"' => s.append(""") + case '\n' => s.append('\n') + case '\r' => s.append('\r') + case '\t' => s.append('\t') + case c => if (c >= ' ') s.append(c) + } + + pos += 1 + } + s + } + + /** + * Appends unescaped string to `s`, `amp` becomes `&`, + * `lt` becomes `<` etc.. + * + * @param ref ... + * @param s ... + * @return `'''null'''` if `ref` was not a predefined entity. + */ + final def unescape(ref: String, s: StringBuilder): StringBuilder = + (unescMap get ref) map (s append _) orNull + + /** + * Returns a set of all namespaces used in a sequence of nodes + * and all their descendants, including the empty namespaces. + * + * @param nodes ... + * @return ... + */ + def collectNamespaces(nodes: Seq[Node]): mutable.Set[String] = + nodes.foldLeft(new mutable.HashSet[String]) { (set, x) => collectNamespaces(x, set) ; set } + + /** + * Adds all namespaces in node to set. + * + * @param n ... + * @param set ... + */ + def collectNamespaces(n: Node, set: mutable.Set[String]) { + if (n.doCollectNamespaces) { + set += n.namespace + for (a <- n.attributes) a match { + case _:PrefixedAttribute => + set += a.getNamespace(n) + case _ => + } + for (i <- n.child) + collectNamespaces(i, set) + } + } + + // def toXML( + // x: Node, + // pscope: NamespaceBinding = TopScope, + // sb: StringBuilder = new StringBuilder, + // stripComments: Boolean = false, + // decodeEntities: Boolean = true, + // preserveWhitespace: Boolean = false, + // minimizeTags: Boolean = false): String = + // { + // toXMLsb(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + // sb.toString() + // } + + /** + * Serialize the provided Node to the provided StringBuilder. + *

+ * Note that calling this source-compatible method will result in the same old, arguably almost universally unwanted, + * behaviour. + */ + @deprecated(since="2.10", message="please use `serialize` instead and specify a `minimizeTags` parameter") + def toXML( + x: Node, + pscope: NamespaceBinding = TopScope, + sb: StringBuilder = new StringBuilder, + stripComments: Boolean = false, + decodeEntities: Boolean = true, + preserveWhitespace: Boolean = false, + minimizeTags: Boolean = false): StringBuilder = + { + serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, if (minimizeTags) MinimizeMode.Always else MinimizeMode.Never) + } + + /** + * Serialize an XML Node to a StringBuilder. + * + * This is essentially a minor rework of `toXML` that can't have the same name due to an unfortunate + * combination of named/default arguments and overloading. + * + * @todo use a Writer instead + */ + def serialize( + x: Node, + pscope: NamespaceBinding = TopScope, + sb: StringBuilder = new StringBuilder, + stripComments: Boolean = false, + decodeEntities: Boolean = true, + preserveWhitespace: Boolean = false, + minimizeTags: MinimizeMode.Value = MinimizeMode.Default): StringBuilder = + { + x match { + case c: Comment if !stripComments => c buildString sb + case s: SpecialNode => s buildString sb + case g: Group => for (c <- g.nodes) serialize(c, g.scope, sb, minimizeTags = minimizeTags) ; sb + case el: Elem => + // print tag with namespace declarations + sb.append('<') + el.nameToString(sb) + if (el.attributes ne null) el.attributes.buildString(sb) + el.scope.buildString(sb, pscope) + if (el.child.isEmpty && + (minimizeTags == MinimizeMode.Always || + (minimizeTags == MinimizeMode.Default && el.minimizeEmpty))) + { + // no children, so use short form: + sb.append("/>") + } else { + // children, so use long form: ... + sb.append('>') + sequenceToXML(el.child, el.scope, sb, stripComments) + sb.append("') + } + case _ => throw new IllegalArgumentException("Don't know how to serialize a " + x.getClass.getName) + } + } + + def sequenceToXML( + children: Seq[Node], + pscope: NamespaceBinding = TopScope, + sb: StringBuilder = new StringBuilder, + stripComments: Boolean = false, + decodeEntities: Boolean = true, + preserveWhitespace: Boolean = false, + minimizeTags: MinimizeMode.Value = MinimizeMode.Default): Unit = + { + if (children.isEmpty) return + else if (children forall isAtomAndNotText) { // add space + val it = children.iterator + val f = it.next + serialize(f, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + while (it.hasNext) { + val x = it.next + sb.append(' ') + serialize(x, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) + } + } + else children foreach { serialize(_, pscope, sb, stripComments, decodeEntities, preserveWhitespace, minimizeTags) } + } + + /** + * Returns prefix of qualified name if any. + * + * @param name ... + * @return ... + */ + final def prefix(name: String): Option[String] = (name indexOf ':') match { + case -1 => None + case i => Some(name.substring(0, i)) + } + + /** + * Returns a hashcode for the given constituents of a node + * + * @param uri + * @param label + * @param attribHashCode + * @param children + */ + def hashCode(pre: String, label: String, attribHashCode: Int, scpeHash: Int, children: Seq[Node]) = + scala.util.MurmurHash3.orderedHash(label +: attribHashCode +: scpeHash +: children, pre.##) + + def appendQuoted(s: String): String = sbToString(appendQuoted(s, _)) + + /** + * Appends "s" if string `s` does not contain ", + * 's' otherwise. + * + * @param s ... + * @param sb ... + * @return ... + */ + def appendQuoted(s: String, sb: StringBuilder) = { + val ch = if (s contains '"') '\'' else '"' + sb.append(ch).append(s).append(ch) + } + + /** + * Appends "s" and escapes and " i s with \" + * + * @param s ... + * @param sb ... + * @return ... + */ + def appendEscapedQuoted(s: String, sb: StringBuilder): StringBuilder = { + sb.append('"') + for (c <- s) c match { + case '"' => sb.append('\\'); sb.append('"') + case _ => sb.append(c) + } + sb.append('"') + } + + /** + * @param s ... + * @param index ... + * @return ... + */ + def getName(s: String, index: Int): String = { + if (index >= s.length) null + else { + val xs = s drop index + if (xs.nonEmpty && isNameStart(xs.head)) xs takeWhile isNameChar + else "" + } + } + + /** + * Returns `'''null'''` if the value is a correct attribute value, + * error message if it isn't. + * + * @param value ... + * @return ... + */ + def checkAttributeValue(value: String): String = { + var i = 0 + while (i < value.length) { + value.charAt(i) match { + case '<' => + return "< not allowed in attribute value"; + case '&' => + val n = getName(value, i+1) + if (n eq null) + return "malformed entity reference in attribute value ["+value+"]"; + i = i + n.length + 1 + if (i >= value.length || value.charAt(i) != ';') + return "malformed entity reference in attribute value ["+value+"]"; + case _ => + } + i = i + 1 + } + null + } + + /** + * new + * + * @param value ... + * @return ... + */ + def parseAttributeValue(value: String): Seq[Node] = { + val sb = new StringBuilder + var rfb: StringBuilder = null + val nb = new NodeBuffer() + + val it = value.iterator + while (it.hasNext) { + var c = it.next + // entity! flush buffer into text node + if (c == '&') { + c = it.next + if (c == '#') { + c = it.next + val theChar = parseCharRef ({ ()=> c },{ () => c = it.next },{s => throw new RuntimeException(s)}, {s => throw new RuntimeException(s)}) + sb.append(theChar) + } + else { + if (rfb eq null) rfb = new StringBuilder() + rfb append c + c = it.next + while (c != ';') { + rfb.append(c) + c = it.next + } + val ref = rfb.toString() + rfb.clear() + unescape(ref,sb) match { + case null => + if (sb.length > 0) { // flush buffer + nb += Text(sb.toString()) + sb.clear() + } + nb += EntityRef(ref) // add entityref + case _ => + } + } + } + else sb append c + } + if (sb.length > 0) { // flush buffer + val x = Text(sb.toString()) + if (nb.length == 0) + return x + else + nb += x + } + nb + } + + /** + * {{{ + * CharRef ::= "&#" '0'..'9' {'0'..'9'} ";" + * | "&#x" '0'..'9'|'A'..'F'|'a'..'f' { hexdigit } ";" + * }}} + * See [66] + * + * @param ch ... + * @param nextch ... + * @param reportSyntaxError ... + * @return ... + */ + def parseCharRef(ch: () => Char, nextch: () => Unit, reportSyntaxError: String => Unit, reportTruncatedError: String => Unit): String = { + val hex = (ch() == 'x') && { nextch(); true } + val base = if (hex) 16 else 10 + var i = 0 + while (ch() != ';') { + ch() match { + case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => + i = i * base + ch().asDigit + case 'a' | 'b' | 'c' | 'd' | 'e' | 'f' + | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' => + if (! hex) + reportSyntaxError("hex char not allowed in decimal char ref\n" + + "Did you mean to write &#x ?") + else + i = i * base + ch().asDigit + case SU => + reportTruncatedError("") + case _ => + reportSyntaxError("character '" + ch() + "' not allowed in char ref\n") + } + nextch() + } + new String(Array(i), 0, 1) + } +} diff --git a/src/library/scala/xml/XML.scala b/src/library/scala/xml/XML.scala index dfdd71a9ae..4beba91899 100755 --- a/src/library/scala/xml/XML.scala +++ b/src/library/scala/xml/XML.scala @@ -28,13 +28,13 @@ object Source } /** - * Governs how empty elements (i.e. those without children) should be serialized. + * Governs how empty elements (i.e. those without child elements) should be serialized. */ object MinimizeMode extends Enumeration { - /** Minimize empty tags if they were originally empty when parsed, or if they were constructed with {@link Elem#minimizeEmpty} == true */ + /** Minimize empty tags if they were originally empty when parsed, or if they were constructed with [[scala.xml.Elem]]`#minimizeEmpty` == true */ val Default = Value - /** Always minimize empty tags. Note that this may be problematic for XHTML, in which case {@link Xhtml#toXhtml} should be used instead. */ + /** Always minimize empty tags. Note that this may be problematic for XHTML, in which case [[scala.xml.Xhtml]]`#toXhtml` should be used instead. */ val Always = Value /** Never minimize empty tags. */ diff --git a/test/files/jvm/deprecation/t1118.scala b/test/files/jvm/deprecation/t1118.scala deleted file mode 100755 index 4464e51f89..0000000000 --- a/test/files/jvm/deprecation/t1118.scala +++ /dev/null @@ -1,21 +0,0 @@ -import scala.xml._ - -object Test { - def main(args: Array[String]) { - println( - - - - -scala stuff is pretty cool -) - - println(Elem(null, "bob", Null, TopScope, false) ++ Text(" ") ++ Comment("programmatic long")) - - println(Elem(null, "dobbs", Null, TopScope, true) ++ Text(" ") ++ Comment("programmatic short")) - - println(Elem(null, "is", Attribute("really", Text("yep"), Null), TopScope, true) ++ Text(" ") ++ Comment ("programmatic short with attribute")) - - println(Elem(null, "slack", Attribute("sing", Text("it"), Null), TopScope, false) ++ Text(" ") ++ Comment ("programmatic long with attribute")) - } -} \ No newline at end of file diff --git a/test/files/jvm/t1118.check b/test/files/jvm/t1118.check index f8a17e0195..b246dc6fb9 100755 --- a/test/files/jvm/t1118.check +++ b/test/files/jvm/t1118.check @@ -1,10 +1,10 @@ - - - - -scala stuff is pretty cool - - - - - \ No newline at end of file + + + + +is pretty cool + + + + + \ No newline at end of file diff --git a/test/files/jvm/t1118.scala b/test/files/jvm/t1118.scala new file mode 100755 index 0000000000..3c86547241 --- /dev/null +++ b/test/files/jvm/t1118.scala @@ -0,0 +1,21 @@ +import scala.xml._ + +object Test { + def main(args: Array[String]) { + println( + + + + +is pretty cool +) + + println(Elem(null, "emptiness", Null, TopScope, false) ++ Text(" ") ++ Comment("programmatic long")) + + println(Elem(null, "vide", Null, TopScope, true) ++ Text(" ") ++ Comment("programmatic short")) + + println(Elem(null, "elem", Attribute("attr", Text("value"), Null), TopScope, true) ++ Text(" ") ++ Comment ("programmatic short with attribute")) + + println(Elem(null, "elem2", Attribute("attr2", Text("value2"), Null), TopScope, false) ++ Text(" ") ++ Comment ("programmatic long with attribute")) + } +} \ No newline at end of file -- cgit v1.2.3 From 57eaf9efbc4d52e1226d8fdccd2b274e860fc198 Mon Sep 17 00:00:00 2001 From: Alex Cruise Date: Thu, 15 Mar 2012 17:43:50 -0700 Subject: Tweaked deprecation annotations to avoid warning --- src/library/scala/xml/Elem.scala | 2 +- src/library/scala/xml/Utility.scala | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/xml/Elem.scala b/src/library/scala/xml/Elem.scala index 605f3cb7fb..cc244a5b88 100755 --- a/src/library/scala/xml/Elem.scala +++ b/src/library/scala/xml/Elem.scala @@ -59,7 +59,7 @@ class Elem( val child: Node*) extends Node with Serializable { - @deprecated(since="2.10", message="this constructor is retained for backward compatibility. Please use the primary constructor, which lets you specify your own preference for `minimizeEmpty`.") + @deprecated("This constructor is retained for backward compatibility. Please use the primary constructor, which lets you specify your own preference for `minimizeEmpty`.", "2.10") def this(prefix: String, label: String, attributes: MetaData, scope: NamespaceBinding, child: Node*) = { this(prefix, label, attributes, scope, child.isEmpty, child: _*) } diff --git a/src/library/scala/xml/Utility.scala b/src/library/scala/xml/Utility.scala index fce6e7e897..9f944c0e92 100755 --- a/src/library/scala/xml/Utility.scala +++ b/src/library/scala/xml/Utility.scala @@ -187,7 +187,7 @@ object Utility extends AnyRef with parsing.TokenTests { * Note that calling this source-compatible method will result in the same old, arguably almost universally unwanted, * behaviour. */ - @deprecated(since="2.10", message="please use `serialize` instead and specify a `minimizeTags` parameter") + @deprecated("Please use `serialize` instead and specify a `minimizeTags` parameter", "2.10") def toXML( x: Node, pscope: NamespaceBinding = TopScope, -- cgit v1.2.3 From f5215cd20ca5bc4566538c87e7095ec65b63aaae Mon Sep 17 00:00:00 2001 From: Aleksandar Prokopec Date: Fri, 16 Mar 2012 16:11:41 +0100 Subject: Renaming Ctrie to ConcurrentTrieMap. --- src/library/scala/collection/mutable/Ctrie.scala | 100 ++++++++++----------- .../collection/parallel/mutable/ParCtrie.scala | 54 +++++------ test/files/jvm/serialization.check | 8 +- test/files/jvm/serialization.scala | 14 +-- test/files/run/ctries/concmap.scala | 24 ++--- test/files/run/ctries/iterator.scala | 20 ++--- test/files/run/ctries/lnode.scala | 14 +-- test/files/run/ctries/snapshot.scala | 26 +++--- test/files/scalacheck/Ctrie.scala | 14 +-- .../parallel-collections/ParallelCtrieCheck.scala | 12 +-- .../files/scalacheck/parallel-collections/pc.scala | 2 +- 11 files changed, 144 insertions(+), 144 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/collection/mutable/Ctrie.scala b/src/library/scala/collection/mutable/Ctrie.scala index cbec118aa9..1a44c8e423 100644 --- a/src/library/scala/collection/mutable/Ctrie.scala +++ b/src/library/scala/collection/mutable/Ctrie.scala @@ -13,7 +13,7 @@ package mutable import java.util.concurrent.atomic._ import collection.immutable.{ ListMap => ImmutableListMap } -import collection.parallel.mutable.ParCtrie +import collection.parallel.mutable.ParConcurrentTrieMap import generic._ import annotation.tailrec import annotation.switch @@ -31,16 +31,16 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends @inline final def CAS(old: MainNode[K, V], n: MainNode[K, V]) = INodeBase.updater.compareAndSet(this, old, n) - final def gcasRead(ct: Ctrie[K, V]): MainNode[K, V] = GCAS_READ(ct) + final def gcasRead(ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = GCAS_READ(ct) - @inline final def GCAS_READ(ct: Ctrie[K, V]): MainNode[K, V] = { + @inline final def GCAS_READ(ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = { val m = /*READ*/mainnode val prevval = /*READ*/m.prev if (prevval eq null) m else GCAS_Complete(m, ct) } - @tailrec private def GCAS_Complete(m: MainNode[K, V], ct: Ctrie[K, V]): MainNode[K, V] = if (m eq null) null else { + @tailrec private def GCAS_Complete(m: MainNode[K, V], ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = if (m eq null) null else { // complete the GCAS val prev = /*READ*/m.prev val ctr = ct.readRoot(true) @@ -72,7 +72,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends } } - @inline final def GCAS(old: MainNode[K, V], n: MainNode[K, V], ct: Ctrie[K, V]): Boolean = { + @inline final def GCAS(old: MainNode[K, V], n: MainNode[K, V], ct: ConcurrentTrieMap[K, V]): Boolean = { n.WRITE_PREV(old) if (CAS(old, n)) { GCAS_Complete(n, ct) @@ -86,7 +86,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends nin } - final def copyToGen(ngen: Gen, ct: Ctrie[K, V]) = { + final def copyToGen(ngen: Gen, ct: ConcurrentTrieMap[K, V]) = { val nin = new INode[K, V](ngen) val main = GCAS_READ(ct) nin.WRITE(main) @@ -97,7 +97,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends * * @return true if successful, false otherwise */ - @tailrec final def rec_insert(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: Ctrie[K, V]): Boolean = { + @tailrec final def rec_insert(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Boolean = { val m = GCAS_READ(ct) // use -Yinline! m match { @@ -143,7 +143,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends * @param cond null - don't care if the key was there; KEY_ABSENT - key wasn't there; KEY_PRESENT - key was there; other value `v` - key must be bound to `v` * @return null if unsuccessful, Option[V] otherwise (indicating previous value bound to the key) */ - @tailrec final def rec_insertif(k: K, v: V, hc: Int, cond: AnyRef, lev: Int, parent: INode[K, V], startgen: Gen, ct: Ctrie[K, V]): Option[V] = { + @tailrec final def rec_insertif(k: K, v: V, hc: Int, cond: AnyRef, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Option[V] = { val m = GCAS_READ(ct) // use -Yinline! m match { @@ -233,7 +233,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends * * @return null if no value has been found, RESTART if the operation wasn't successful, or any other value otherwise */ - @tailrec final def rec_lookup(k: K, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: Ctrie[K, V]): AnyRef = { + @tailrec final def rec_lookup(k: K, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): AnyRef = { val m = GCAS_READ(ct) // use -Yinline! m match { @@ -276,7 +276,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends * @param v if null, will remove the key irregardless of the value; otherwise removes only if binding contains that exact key and value * @return null if not successful, an Option[V] indicating the previous value otherwise */ - final def rec_remove(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: Ctrie[K, V]): Option[V] = { + final def rec_remove(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Option[V] = { val m = GCAS_READ(ct) // use -Yinline! m match { @@ -352,7 +352,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends } } - private def clean(nd: INode[K, V], ct: Ctrie[K, V], lev: Int) { + private def clean(nd: INode[K, V], ct: ConcurrentTrieMap[K, V], lev: Int) { val m = nd.GCAS_READ(ct) m match { case cn: CNode[K, V] => nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct) @@ -360,9 +360,9 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends } } - final def isNullInode(ct: Ctrie[K, V]) = GCAS_READ(ct) eq null + final def isNullInode(ct: ConcurrentTrieMap[K, V]) = GCAS_READ(ct) eq null - final def cachedSize(ct: Ctrie[K, V]): Int = { + final def cachedSize(ct: ConcurrentTrieMap[K, V]): Int = { val m = GCAS_READ(ct) m.cachedSize(ct) } @@ -438,7 +438,7 @@ extends MainNode[K, V] { if (updmap.size > 1) new LNode(updmap) else { val (k, v) = updmap.iterator.next - new TNode(k, v, Ctrie.computeHash(k)) // create it tombed so that it gets compressed on subsequent accesses + new TNode(k, v, ConcurrentTrieMap.computeHash(k)) // create it tombed so that it gets compressed on subsequent accesses } } def get(k: K) = listmap.get(k) @@ -455,7 +455,7 @@ extends CNodeBase[K, V] { val currsz = READ_SIZE() if (currsz != -1) currsz else { - val sz = computeSize(ct.asInstanceOf[Ctrie[K, V]]) + val sz = computeSize(ct.asInstanceOf[ConcurrentTrieMap[K, V]]) while (READ_SIZE() == -1) CAS_SIZE(-1, sz) READ_SIZE() } @@ -466,7 +466,7 @@ extends CNodeBase[K, V] { // => if there are concurrent size computations, they start // at different positions, so they are more likely to // to be independent - private def computeSize(ct: Ctrie[K, V]): Int = { + private def computeSize(ct: ConcurrentTrieMap[K, V]): Int = { var i = 0 var sz = 0 val offset = math.abs(util.Random.nextInt()) % array.length @@ -511,7 +511,7 @@ extends CNodeBase[K, V] { /** Returns a copy of this cnode such that all the i-nodes below it are copied * to the specified generation `ngen`. */ - final def renewed(ngen: Gen, ct: Ctrie[K, V]) = { + final def renewed(ngen: Gen, ct: ConcurrentTrieMap[K, V]) = { var i = 0 val arr = array val len = arr.length @@ -542,7 +542,7 @@ extends CNodeBase[K, V] { // returns the version of this node with at least some null-inodes // removed (those existing when the op began) // - if there are only null-i-nodes below, returns null - final def toCompressed(ct: Ctrie[K, V], lev: Int, gen: Gen) = { + final def toCompressed(ct: ConcurrentTrieMap[K, V], lev: Int, gen: Gen) = { var bmp = bitmap var i = 0 val arr = array @@ -594,7 +594,7 @@ private[mutable] object CNode { val yidx = (yhc >>> lev) & 0x1f val bmp = (1 << xidx) | (1 << yidx) if (xidx == yidx) { - val subinode = new INode[K, V](gen)//(Ctrie.inodeupdater) + val subinode = new INode[K, V](gen)//(ConcurrentTrieMap.inodeupdater) subinode.mainnode = dual(x, xhc, y, yhc, lev + 5, gen) new CNode(bmp, Array(subinode), gen) } else { @@ -613,7 +613,7 @@ private[mutable] case class RDCSS_Descriptor[K, V](old: INode[K, V], expectedmai } -/** A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free +/** A concurrent hash-trie or ConcurrentTrieMap is a concurrent thread-safe lock-free * implementation of a hash array mapped trie. It is used to implement the * concurrent map abstraction. It has particularly scalable concurrent insert * and remove operations and is memory-efficient. It supports O(1), atomic, @@ -627,20 +627,20 @@ private[mutable] case class RDCSS_Descriptor[K, V](old: INode[K, V], expectedmai * @since 2.10 */ @SerialVersionUID(0L - 6402774413839597105L) -final class Ctrie[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[Ctrie[K, V], AnyRef]) +final class ConcurrentTrieMap[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[ConcurrentTrieMap[K, V], AnyRef]) extends ConcurrentMap[K, V] - with MapLike[K, V, Ctrie[K, V]] - with CustomParallelizable[(K, V), ParCtrie[K, V]] + with MapLike[K, V, ConcurrentTrieMap[K, V]] + with CustomParallelizable[(K, V), ParConcurrentTrieMap[K, V]] with Serializable { - import Ctrie.computeHash + import ConcurrentTrieMap.computeHash private var rootupdater = rtupd @volatile var root = r def this() = this( INode.newRootNode, - AtomicReferenceFieldUpdater.newUpdater(classOf[Ctrie[K, V]], classOf[AnyRef], "root") + AtomicReferenceFieldUpdater.newUpdater(classOf[ConcurrentTrieMap[K, V]], classOf[AnyRef], "root") ) /* internal methods */ @@ -652,22 +652,22 @@ extends ConcurrentMap[K, V] out.writeObject(k) out.writeObject(v) } - out.writeObject(CtrieSerializationEnd) + out.writeObject(ConcurrentTrieMapSerializationEnd) } private def readObject(in: java.io.ObjectInputStream) { root = INode.newRootNode - rootupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[Ctrie[K, V]], classOf[AnyRef], "root") + rootupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[ConcurrentTrieMap[K, V]], classOf[AnyRef], "root") var obj: AnyRef = null do { obj = in.readObject() - if (obj != CtrieSerializationEnd) { + if (obj != ConcurrentTrieMapSerializationEnd) { val k = obj.asInstanceOf[K] val v = in.readObject().asInstanceOf[V] update(k, v) } - } while (obj != CtrieSerializationEnd) + } while (obj != ConcurrentTrieMapSerializationEnd) } @inline final def CAS_ROOT(ov: AnyRef, nv: AnyRef) = rootupdater.compareAndSet(this, ov, nv) @@ -760,37 +760,37 @@ extends ConcurrentMap[K, V] override def seq = this - override def par = new ParCtrie(this) + override def par = new ParConcurrentTrieMap(this) - override def empty: Ctrie[K, V] = new Ctrie[K, V] + override def empty: ConcurrentTrieMap[K, V] = new ConcurrentTrieMap[K, V] final def isReadOnly = rootupdater eq null final def nonReadOnly = rootupdater ne null - /** Returns a snapshot of this Ctrie. + /** Returns a snapshot of this ConcurrentTrieMap. * This operation is lock-free and linearizable. * * The snapshot is lazily updated - the first time some branch - * in the snapshot or this Ctrie are accessed, they are rewritten. + * in the snapshot or this ConcurrentTrieMap are accessed, they are rewritten. * This means that the work of rebuilding both the snapshot and this - * Ctrie is distributed across all the threads doing updates or accesses + * ConcurrentTrieMap is distributed across all the threads doing updates or accesses * subsequent to the snapshot creation. */ - @tailrec final def snapshot(): Ctrie[K, V] = { + @tailrec final def snapshot(): ConcurrentTrieMap[K, V] = { val r = RDCSS_READ_ROOT() val expmain = r.gcasRead(this) - if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new Ctrie(r.copyToGen(new Gen, this), rootupdater) + if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new ConcurrentTrieMap(r.copyToGen(new Gen, this), rootupdater) else snapshot() } - /** Returns a read-only snapshot of this Ctrie. + /** Returns a read-only snapshot of this ConcurrentTrieMap. * This operation is lock-free and linearizable. * * The snapshot is lazily updated - the first time some branch - * of this Ctrie are accessed, it is rewritten. The work of creating + * of this ConcurrentTrieMap are accessed, it is rewritten. The work of creating * the snapshot is thus distributed across subsequent updates - * and accesses on this Ctrie by all threads. + * and accesses on this ConcurrentTrieMap by all threads. * Note that the snapshot itself is never rewritten unlike when calling * the `snapshot` method, but the obtained snapshot cannot be modified. * @@ -799,7 +799,7 @@ extends ConcurrentMap[K, V] @tailrec final def readOnlySnapshot(): collection.Map[K, V] = { val r = RDCSS_READ_ROOT() val expmain = r.gcasRead(this) - if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new Ctrie(r, null) + if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new ConcurrentTrieMap(r, null) else readOnlySnapshot() } @@ -872,7 +872,7 @@ extends ConcurrentMap[K, V] def iterator: Iterator[(K, V)] = if (nonReadOnly) readOnlySnapshot().iterator - else new CtrieIterator(0, this) + else new ConcurrentTrieMapIterator(0, this) private def cachedSize() = { val r = RDCSS_READ_ROOT() @@ -883,17 +883,17 @@ extends ConcurrentMap[K, V] if (nonReadOnly) readOnlySnapshot().size else cachedSize() - override def stringPrefix = "Ctrie" + override def stringPrefix = "ConcurrentTrieMap" } -object Ctrie extends MutableMapFactory[Ctrie] { +object ConcurrentTrieMap extends MutableMapFactory[ConcurrentTrieMap] { val inodeupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[INodeBase[_, _]], classOf[MainNode[_, _]], "mainnode") - implicit def canBuildFrom[K, V]: CanBuildFrom[Coll, (K, V), Ctrie[K, V]] = new MapCanBuildFrom[K, V] + implicit def canBuildFrom[K, V]: CanBuildFrom[Coll, (K, V), ConcurrentTrieMap[K, V]] = new MapCanBuildFrom[K, V] - def empty[K, V]: Ctrie[K, V] = new Ctrie[K, V] + def empty[K, V]: ConcurrentTrieMap[K, V] = new ConcurrentTrieMap[K, V] @inline final def computeHash[K](k: K): Int = { var hcode = k.hashCode @@ -905,7 +905,7 @@ object Ctrie extends MutableMapFactory[Ctrie] { } -private[collection] class CtrieIterator[K, V](var level: Int, private var ct: Ctrie[K, V], mustInit: Boolean = true) extends Iterator[(K, V)] { +private[collection] class ConcurrentTrieMapIterator[K, V](var level: Int, private var ct: ConcurrentTrieMap[K, V], mustInit: Boolean = true) extends Iterator[(K, V)] { var stack = new Array[Array[BasicNode]](7) var stackpos = new Array[Int](7) var depth = -1 @@ -971,9 +971,9 @@ private[collection] class CtrieIterator[K, V](var level: Int, private var ct: Ct } } else current = null - protected def newIterator(_lev: Int, _ct: Ctrie[K, V], _mustInit: Boolean) = new CtrieIterator[K, V](_lev, _ct, _mustInit) + protected def newIterator(_lev: Int, _ct: ConcurrentTrieMap[K, V], _mustInit: Boolean) = new ConcurrentTrieMapIterator[K, V](_lev, _ct, _mustInit) - protected def dupTo(it: CtrieIterator[K, V]) = { + protected def dupTo(it: ConcurrentTrieMapIterator[K, V]) = { it.level = this.level it.ct = this.ct it.depth = this.depth @@ -993,7 +993,7 @@ private[collection] class CtrieIterator[K, V](var level: Int, private var ct: Ct } /** Returns a sequence of iterators over subsets of this iterator. - * It's used to ease the implementation of splitters for a parallel version of the Ctrie. + * It's used to ease the implementation of splitters for a parallel version of the ConcurrentTrieMap. */ protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne null) { // the case where an LNode is being iterated @@ -1043,7 +1043,7 @@ private[mutable] object RestartException extends util.control.ControlThrowable /** Only used for ctrie serialization. */ @SerialVersionUID(0L - 7237891413820527142L) -private[mutable] case object CtrieSerializationEnd +private[mutable] case object ConcurrentTrieMapSerializationEnd private[mutable] object Debug { diff --git a/src/library/scala/collection/parallel/mutable/ParCtrie.scala b/src/library/scala/collection/parallel/mutable/ParCtrie.scala index 470972adad..a6495161ea 100644 --- a/src/library/scala/collection/parallel/mutable/ParCtrie.scala +++ b/src/library/scala/collection/parallel/mutable/ParCtrie.scala @@ -20,12 +20,12 @@ import scala.collection.mutable.LNode import scala.collection.mutable.CNode import scala.collection.mutable.SNode import scala.collection.mutable.INode -import scala.collection.mutable.Ctrie -import scala.collection.mutable.CtrieIterator +import scala.collection.mutable.ConcurrentTrieMap +import scala.collection.mutable.ConcurrentTrieMapIterator -/** Parallel Ctrie collection. +/** Parallel ConcurrentTrieMap collection. * * It has its bulk operations parallelized, but uses the snapshot operation * to create the splitter. This means that parallel bulk operations can be @@ -34,24 +34,24 @@ import scala.collection.mutable.CtrieIterator * @author Aleksandar Prokopec * @since 2.10 */ -final class ParCtrie[K, V] private[collection] (private val ctrie: Ctrie[K, V]) +final class ParConcurrentTrieMap[K, V] private[collection] (private val ctrie: ConcurrentTrieMap[K, V]) extends ParMap[K, V] - with GenericParMapTemplate[K, V, ParCtrie] - with ParMapLike[K, V, ParCtrie[K, V], Ctrie[K, V]] - with ParCtrieCombiner[K, V] + with GenericParMapTemplate[K, V, ParConcurrentTrieMap] + with ParMapLike[K, V, ParConcurrentTrieMap[K, V], ConcurrentTrieMap[K, V]] + with ParConcurrentTrieMapCombiner[K, V] with Serializable { - def this() = this(new Ctrie) + def this() = this(new ConcurrentTrieMap) - override def mapCompanion: GenericParMapCompanion[ParCtrie] = ParCtrie + override def mapCompanion: GenericParMapCompanion[ParConcurrentTrieMap] = ParConcurrentTrieMap - override def empty: ParCtrie[K, V] = ParCtrie.empty + override def empty: ParConcurrentTrieMap[K, V] = ParConcurrentTrieMap.empty - protected[this] override def newCombiner = ParCtrie.newCombiner + protected[this] override def newCombiner = ParConcurrentTrieMap.newCombiner override def seq = ctrie - def splitter = new ParCtrieSplitter(0, ctrie.readOnlySnapshot().asInstanceOf[Ctrie[K, V]], true) + def splitter = new ParConcurrentTrieMapSplitter(0, ctrie.readOnlySnapshot().asInstanceOf[ConcurrentTrieMap[K, V]], true) override def clear() = ctrie.clear() @@ -87,11 +87,11 @@ extends ParMap[K, V] } } - override def stringPrefix = "ParCtrie" + override def stringPrefix = "ParConcurrentTrieMap" /* tasks */ - /** Computes Ctrie size in parallel. */ + /** Computes ConcurrentTrieMap size in parallel. */ class Size(offset: Int, howmany: Int, array: Array[BasicNode]) extends Task[Int, Size] { var result = -1 def leaf(prev: Option[Int]) = { @@ -118,15 +118,15 @@ extends ParMap[K, V] } -private[collection] class ParCtrieSplitter[K, V](lev: Int, ct: Ctrie[K, V], mustInit: Boolean) -extends CtrieIterator[K, V](lev, ct, mustInit) +private[collection] class ParConcurrentTrieMapSplitter[K, V](lev: Int, ct: ConcurrentTrieMap[K, V], mustInit: Boolean) +extends ConcurrentTrieMapIterator[K, V](lev, ct, mustInit) with IterableSplitter[(K, V)] { // only evaluated if `remaining` is invoked (which is not used by most tasks) lazy val totalsize = ct.par.size var iterated = 0 - protected override def newIterator(_lev: Int, _ct: Ctrie[K, V], _mustInit: Boolean) = new ParCtrieSplitter[K, V](_lev, _ct, _mustInit) + protected override def newIterator(_lev: Int, _ct: ConcurrentTrieMap[K, V], _mustInit: Boolean) = new ParConcurrentTrieMapSplitter[K, V](_lev, _ct, _mustInit) override def shouldSplitFurther[S](coll: collection.parallel.ParIterable[S], parallelismLevel: Int) = { val maxsplits = 3 + Integer.highestOneBit(parallelismLevel) @@ -153,15 +153,15 @@ extends CtrieIterator[K, V](lev, ct, mustInit) } -/** Only used within the `ParCtrie`. */ -private[mutable] trait ParCtrieCombiner[K, V] extends Combiner[(K, V), ParCtrie[K, V]] { +/** Only used within the `ParConcurrentTrieMap`. */ +private[mutable] trait ParConcurrentTrieMapCombiner[K, V] extends Combiner[(K, V), ParConcurrentTrieMap[K, V]] { - def combine[N <: (K, V), NewTo >: ParCtrie[K, V]](other: Combiner[N, NewTo]): Combiner[N, NewTo] = if (this eq other) this else { + def combine[N <: (K, V), NewTo >: ParConcurrentTrieMap[K, V]](other: Combiner[N, NewTo]): Combiner[N, NewTo] = if (this eq other) this else { throw new UnsupportedOperationException("This shouldn't have been called in the first place.") - val thiz = this.asInstanceOf[ParCtrie[K, V]] - val that = other.asInstanceOf[ParCtrie[K, V]] - val result = new ParCtrie[K, V] + val thiz = this.asInstanceOf[ParConcurrentTrieMap[K, V]] + val that = other.asInstanceOf[ParConcurrentTrieMap[K, V]] + val result = new ParConcurrentTrieMap[K, V] result ++= thiz.iterator result ++= that.iterator @@ -174,13 +174,13 @@ private[mutable] trait ParCtrieCombiner[K, V] extends Combiner[(K, V), ParCtrie[ } -object ParCtrie extends ParMapFactory[ParCtrie] { +object ParConcurrentTrieMap extends ParMapFactory[ParConcurrentTrieMap] { - def empty[K, V]: ParCtrie[K, V] = new ParCtrie[K, V] + def empty[K, V]: ParConcurrentTrieMap[K, V] = new ParConcurrentTrieMap[K, V] - def newCombiner[K, V]: Combiner[(K, V), ParCtrie[K, V]] = new ParCtrie[K, V] + def newCombiner[K, V]: Combiner[(K, V), ParConcurrentTrieMap[K, V]] = new ParConcurrentTrieMap[K, V] - implicit def canBuildFrom[K, V]: CanCombineFrom[Coll, (K, V), ParCtrie[K, V]] = new CanCombineFromMap[K, V] + implicit def canBuildFrom[K, V]: CanCombineFrom[Coll, (K, V), ParConcurrentTrieMap[K, V]] = new CanCombineFromMap[K, V] } diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check index 81b68f0f5d..0b8055a6b9 100644 --- a/test/files/jvm/serialization.check +++ b/test/files/jvm/serialization.check @@ -192,8 +192,8 @@ x = TreeSet(1, 2, 3) y = TreeSet(1, 2, 3) x equals y: true, y equals x: true -x = Ctrie(1 -> one, 2 -> two, 3 -> three) -y = Ctrie(1 -> one, 2 -> two, 3 -> three) +x = ConcurrentTrieMap(1 -> one, 2 -> two, 3 -> three) +y = ConcurrentTrieMap(1 -> one, 2 -> two, 3 -> three) x equals y: true, y equals x: true x = xml:src="hello" @@ -287,8 +287,8 @@ x = ParHashMap(2 -> 4, 1 -> 2) y = ParHashMap(2 -> 4, 1 -> 2) x equals y: true, y equals x: true -x = ParCtrie(1 -> 2, 2 -> 4) -y = ParCtrie(1 -> 2, 2 -> 4) +x = ParConcurrentTrieMap(1 -> 2, 2 -> 4) +y = ParConcurrentTrieMap(1 -> 2, 2 -> 4) x equals y: true, y equals x: true x = ParHashSet(1, 2, 3) diff --git a/test/files/jvm/serialization.scala b/test/files/jvm/serialization.scala index 75daa8903d..1e89036f37 100644 --- a/test/files/jvm/serialization.scala +++ b/test/files/jvm/serialization.scala @@ -286,7 +286,7 @@ object Test3_mutable { import scala.collection.mutable.{ ArrayBuffer, ArrayBuilder, ArraySeq, ArrayStack, BitSet, DoubleLinkedList, HashMap, HashSet, History, LinkedList, ListBuffer, Publisher, Queue, - Stack, StringBuilder, WrappedArray, TreeSet, Ctrie} + Stack, StringBuilder, WrappedArray, TreeSet, ConcurrentTrieMap} // in alphabetic order try { @@ -386,9 +386,9 @@ object Test3_mutable { val _ts1: TreeSet[Int] = read(write(ts1)) check(ts1, _ts1) - // Ctrie - val ct1 = Ctrie[Int, String]() ++= Array(1 -> "one", 2 -> "two", 3 -> "three") - val _ct1: Ctrie[Int, String] = read(write(ct1)) + // ConcurrentTrieMap + val ct1 = ConcurrentTrieMap[Int, String]() ++= Array(1 -> "one", 2 -> "two", 3 -> "three") + val _ct1: ConcurrentTrieMap[Int, String] = read(write(ct1)) check(ct1, _ct1) } catch { @@ -613,9 +613,9 @@ object Test9_parallel { val _mpm: mutable.ParHashMap[Int, Int] = read(write(mpm)) check(mpm, _mpm) - // mutable.ParCtrie - val mpc = mutable.ParCtrie(1 -> 2, 2 -> 4) - val _mpc: mutable.ParCtrie[Int, Int] = read(write(mpc)) + // mutable.ParConcurrentTrieMap + val mpc = mutable.ParConcurrentTrieMap(1 -> 2, 2 -> 4) + val _mpc: mutable.ParConcurrentTrieMap[Int, Int] = read(write(mpc)) check(mpc, _mpc) // mutable.ParHashSet diff --git a/test/files/run/ctries/concmap.scala b/test/files/run/ctries/concmap.scala index d73e33182a..bf8cc9d12f 100644 --- a/test/files/run/ctries/concmap.scala +++ b/test/files/run/ctries/concmap.scala @@ -1,7 +1,7 @@ -import collection.mutable.Ctrie +import collection.mutable.ConcurrentTrieMap object ConcurrentMapSpec extends Spec { @@ -11,13 +11,13 @@ object ConcurrentMapSpec extends Spec { def test() { "support put" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until initsz) assert(ct.put(new Wrap(i), i) == None) for (i <- 0 until initsz) assert(ct.put(new Wrap(i), -i) == Some(i)) } "support put if absent" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until initsz) ct.update(new Wrap(i), i) for (i <- 0 until initsz) assert(ct.putIfAbsent(new Wrap(i), -i) == Some(i)) for (i <- 0 until initsz) assert(ct.putIfAbsent(new Wrap(i), -i) == Some(i)) @@ -26,7 +26,7 @@ object ConcurrentMapSpec extends Spec { } "support remove if mapped to a specific value" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until initsz) ct.update(new Wrap(i), i) for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), -i - 1) == false) for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), i) == true) @@ -34,7 +34,7 @@ object ConcurrentMapSpec extends Spec { } "support replace if mapped to a specific value" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until initsz) ct.update(new Wrap(i), i) for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), -i - 1, -i - 2) == false) for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i, -i - 2) == true) @@ -43,7 +43,7 @@ object ConcurrentMapSpec extends Spec { } "support replace if present" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until initsz) ct.update(new Wrap(i), i) for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), -i) == Some(i)) for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i) == Some(-i)) @@ -56,7 +56,7 @@ object ConcurrentMapSpec extends Spec { } "support replace if mapped to a specific value, using several threads" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] val sz = 55000 for (i <- 0 until sz) ct.update(new Wrap(i), i) @@ -89,7 +89,7 @@ object ConcurrentMapSpec extends Spec { } "support put if absent, several threads" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] val sz = 110000 class Updater(offs: Int) extends Thread { @@ -110,7 +110,7 @@ object ConcurrentMapSpec extends Spec { } "support remove if mapped to a specific value, several threads" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] val sz = 55000 for (i <- 0 until sz) ct.update(new Wrap(i), i) @@ -132,7 +132,7 @@ object ConcurrentMapSpec extends Spec { } "have all or none of the elements depending on the oddity" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] val sz = 65000 for (i <- 0 until sz) ct(new Wrap(i)) = i @@ -165,7 +165,7 @@ object ConcurrentMapSpec extends Spec { } "compute size correctly" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] val sz = 36450 for (i <- 0 until sz) ct(new Wrap(i)) = i @@ -174,7 +174,7 @@ object ConcurrentMapSpec extends Spec { } "compute size correctly in parallel" in { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] val sz = 36450 for (i <- 0 until sz) ct(new Wrap(i)) = i val pct = ct.par diff --git a/test/files/run/ctries/iterator.scala b/test/files/run/ctries/iterator.scala index 85a6ab7623..dbfab6b8a9 100644 --- a/test/files/run/ctries/iterator.scala +++ b/test/files/run/ctries/iterator.scala @@ -3,7 +3,7 @@ import collection._ -import collection.mutable.Ctrie +import collection.mutable.ConcurrentTrieMap @@ -11,7 +11,7 @@ object IteratorSpec extends Spec { def test() { "work for an empty trie" in { - val ct = new Ctrie + val ct = new ConcurrentTrieMap val it = ct.iterator it.hasNext shouldEqual (false) @@ -19,7 +19,7 @@ object IteratorSpec extends Spec { } def nonEmptyIteratorCheck(sz: Int) { - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct.put(new Wrap(i), i) val it = ct.iterator @@ -84,7 +84,7 @@ object IteratorSpec extends Spec { } def nonEmptyCollideCheck(sz: Int) { - val ct = new Ctrie[DumbHash, Int] + val ct = new ConcurrentTrieMap[DumbHash, Int] for (i <- 0 until sz) ct.put(new DumbHash(i), i) val it = ct.iterator @@ -144,7 +144,7 @@ object IteratorSpec extends Spec { val W = 15 val S = 5 val checks = 5 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct.put(new Wrap(i), i) class Modifier extends Thread { @@ -156,7 +156,7 @@ object IteratorSpec extends Spec { } } - def consistentIteration(ct: Ctrie[Wrap, Int], checks: Int) { + def consistentIteration(ct: ConcurrentTrieMap[Wrap, Int], checks: Int) { class Iter extends Thread { override def run() { val snap = ct.readOnlySnapshot() @@ -185,7 +185,7 @@ object IteratorSpec extends Spec { val sgroupsize = 10 val sgroupnum = 5 val removerslowdown = 50 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct.put(new Wrap(i), i) class Remover extends Thread { @@ -227,7 +227,7 @@ object IteratorSpec extends Spec { val sgroupsize = 10 val sgroupnum = 10 val inserterslowdown = 50 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] class Inserter extends Thread { override def run() { @@ -265,7 +265,7 @@ object IteratorSpec extends Spec { "work on a yet unevaluated snapshot" in { val sz = 50000 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct.update(new Wrap(i), i) val snap = ct.snapshot() @@ -276,7 +276,7 @@ object IteratorSpec extends Spec { "be duplicated" in { val sz = 50 - val ct = collection.parallel.mutable.ParCtrie((0 until sz) zip (0 until sz): _*) + val ct = collection.parallel.mutable.ParConcurrentTrieMap((0 until sz) zip (0 until sz): _*) val it = ct.splitter for (_ <- 0 until (sz / 2)) it.next() val dupit = it.dup diff --git a/test/files/run/ctries/lnode.scala b/test/files/run/ctries/lnode.scala index 88cbeed1f6..e480795956 100644 --- a/test/files/run/ctries/lnode.scala +++ b/test/files/run/ctries/lnode.scala @@ -1,7 +1,7 @@ -import collection.mutable.Ctrie +import collection.mutable.ConcurrentTrieMap object LNodeSpec extends Spec { @@ -11,19 +11,19 @@ object LNodeSpec extends Spec { def test() { "accept elements with the same hash codes" in { - val ct = new Ctrie[DumbHash, Int] + val ct = new ConcurrentTrieMap[DumbHash, Int] for (i <- 0 until initsz) ct.update(new DumbHash(i), i) } "lookup elements with the same hash codes" in { - val ct = new Ctrie[DumbHash, Int] + val ct = new ConcurrentTrieMap[DumbHash, Int] for (i <- 0 until initsz) ct.update(new DumbHash(i), i) for (i <- 0 until initsz) assert(ct.get(new DumbHash(i)) == Some(i)) for (i <- initsz until secondsz) assert(ct.get(new DumbHash(i)) == None) } "remove elements with the same hash codes" in { - val ct = new Ctrie[DumbHash, Int] + val ct = new ConcurrentTrieMap[DumbHash, Int] for (i <- 0 until initsz) ct.update(new DumbHash(i), i) for (i <- 0 until initsz) { val remelem = ct.remove(new DumbHash(i)) @@ -33,7 +33,7 @@ object LNodeSpec extends Spec { } "put elements with the same hash codes if absent" in { - val ct = new Ctrie[DumbHash, Int] + val ct = new ConcurrentTrieMap[DumbHash, Int] for (i <- 0 until initsz) ct.put(new DumbHash(i), i) for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == i) for (i <- 0 until initsz) assert(ct.putIfAbsent(new DumbHash(i), i) == Some(i)) @@ -42,7 +42,7 @@ object LNodeSpec extends Spec { } "replace elements with the same hash codes" in { - val ct = new Ctrie[DumbHash, Int] + val ct = new ConcurrentTrieMap[DumbHash, Int] for (i <- 0 until initsz) assert(ct.put(new DumbHash(i), i) == None) for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == i) for (i <- 0 until initsz) assert(ct.replace(new DumbHash(i), -i) == Some(i)) @@ -51,7 +51,7 @@ object LNodeSpec extends Spec { } "remove elements with the same hash codes if mapped to a specific value" in { - val ct = new Ctrie[DumbHash, Int] + val ct = new ConcurrentTrieMap[DumbHash, Int] for (i <- 0 until initsz) assert(ct.put(new DumbHash(i), i) == None) for (i <- 0 until initsz) assert(ct.remove(new DumbHash(i), i) == true) } diff --git a/test/files/run/ctries/snapshot.scala b/test/files/run/ctries/snapshot.scala index 69073d3f06..3c816130b3 100644 --- a/test/files/run/ctries/snapshot.scala +++ b/test/files/run/ctries/snapshot.scala @@ -3,7 +3,7 @@ import collection._ -import collection.mutable.Ctrie +import collection.mutable.ConcurrentTrieMap @@ -11,11 +11,11 @@ object SnapshotSpec extends Spec { def test() { "support snapshots" in { - val ctn = new Ctrie + val ctn = new ConcurrentTrieMap ctn.snapshot() ctn.readOnlySnapshot() - val ct = new Ctrie[Int, Int] + val ct = new ConcurrentTrieMap[Int, Int] for (i <- 0 until 100) ct.put(i, i) ct.snapshot() ct.readOnlySnapshot() @@ -24,7 +24,7 @@ object SnapshotSpec extends Spec { "empty 2 quiescent snapshots in isolation" in { val sz = 4000 - class Worker(trie: Ctrie[Wrap, Int]) extends Thread { + class Worker(trie: ConcurrentTrieMap[Wrap, Int]) extends Thread { override def run() { for (i <- 0 until sz) { assert(trie.remove(new Wrap(i)) == Some(i)) @@ -35,7 +35,7 @@ object SnapshotSpec extends Spec { } } - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct.put(new Wrap(i), i) val snapt = ct.snapshot() @@ -96,7 +96,7 @@ object SnapshotSpec extends Spec { } // traverses the trie `rep` times and modifies each entry - class Modifier(trie: Ctrie[Wrap, Int], index: Int, rep: Int, sz: Int) extends Thread { + class Modifier(trie: ConcurrentTrieMap[Wrap, Int], index: Int, rep: Int, sz: Int) extends Thread { setName("Modifier %d".format(index)) override def run() { @@ -110,7 +110,7 @@ object SnapshotSpec extends Spec { } // removes all the elements from the trie - class Remover(trie: Ctrie[Wrap, Int], index: Int, totremovers: Int, sz: Int) extends Thread { + class Remover(trie: ConcurrentTrieMap[Wrap, Int], index: Int, totremovers: Int, sz: Int) extends Thread { setName("Remover %d".format(index)) override def run() { @@ -123,7 +123,7 @@ object SnapshotSpec extends Spec { val N = 100 val W = 10 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct(new Wrap(i)) = i val readonly = ct.readOnlySnapshot() val threads = for (i <- 0 until W) yield new Modifier(ct, i, N, sz) @@ -141,7 +141,7 @@ object SnapshotSpec extends Spec { val W = 100 val S = 5000 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct(new Wrap(i)) = i val threads = for (i <- 0 until W) yield new Remover(ct, i, W, sz) @@ -156,7 +156,7 @@ object SnapshotSpec extends Spec { val W = 10 val S = 7000 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct(new Wrap(i)) = i val threads = for (i <- 0 until W) yield new Modifier(ct, i, N, sz) @@ -165,7 +165,7 @@ object SnapshotSpec extends Spec { threads.foreach(_.join()) } - def consistentNonReadOnly(name: String, trie: Ctrie[Wrap, Int], sz: Int, N: Int) { + def consistentNonReadOnly(name: String, trie: ConcurrentTrieMap[Wrap, Int], sz: Int, N: Int) { @volatile var e: Exception = null // reads possible entries once and stores them @@ -223,7 +223,7 @@ object SnapshotSpec extends Spec { val W = 10 val S = 400 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct(new Wrap(i)) = i val threads = for (i <- 0 until W) yield new Modifier(ct, i, N, sz) @@ -241,7 +241,7 @@ object SnapshotSpec extends Spec { val S = 10 val modifytimes = 1200 val snaptimes = 600 - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct(new Wrap(i)) = i class Snapshooter extends Thread { diff --git a/test/files/scalacheck/Ctrie.scala b/test/files/scalacheck/Ctrie.scala index 2950937278..b9d71b88a3 100644 --- a/test/files/scalacheck/Ctrie.scala +++ b/test/files/scalacheck/Ctrie.scala @@ -5,7 +5,7 @@ import org.scalacheck._ import Prop._ import org.scalacheck.Gen._ import collection._ -import collection.mutable.Ctrie +import collection.mutable.ConcurrentTrieMap @@ -16,7 +16,7 @@ case class Wrap(i: Int) { /** A check mainly oriented towards checking snapshot correctness. */ -object Test extends Properties("Ctrie") { +object Test extends Properties("ConcurrentTrieMap") { /* generators */ @@ -102,7 +102,7 @@ object Test extends Properties("Ctrie") { (numThreads, numElems) => val p = 3 //numThreads val sz = 102 //numElems - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] // checker val checker = spawn { @@ -134,7 +134,7 @@ object Test extends Properties("Ctrie") { property("update") = forAll(sizes) { (n: Int) => - val ct = new Ctrie[Int, Int] + val ct = new ConcurrentTrieMap[Int, Int] for (i <- 0 until n) ct(i) = i (0 until n) forall { case i => ct(i) == i @@ -143,7 +143,7 @@ object Test extends Properties("Ctrie") { property("concurrent update") = forAll(threadCountsAndSizes) { case (p, sz) => - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] inParallel(p) { idx => @@ -158,7 +158,7 @@ object Test extends Properties("Ctrie") { property("concurrent remove") = forAll(threadCounts, sizes) { (p, sz) => - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] for (i <- 0 until sz) ct(Wrap(i)) = i inParallel(p) { @@ -174,7 +174,7 @@ object Test extends Properties("Ctrie") { property("concurrent putIfAbsent") = forAll(threadCounts, sizes) { (p, sz) => - val ct = new Ctrie[Wrap, Int] + val ct = new ConcurrentTrieMap[Wrap, Int] val results = inParallel(p) { idx => diff --git a/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala b/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala index d1924f0ada..a04c0ff8d4 100644 --- a/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala @@ -15,25 +15,25 @@ import scala.collection.parallel.ops._ -abstract class ParallelCtrieCheck[K, V](tp: String) extends ParallelMapCheck[K, V]("mutable.ParCtrie[" + tp + "]") { +abstract class ParallelConcurrentTrieMapCheck[K, V](tp: String) extends ParallelMapCheck[K, V]("mutable.ParConcurrentTrieMap[" + tp + "]") { // ForkJoinTasks.defaultForkJoinPool.setMaximumPoolSize(Runtime.getRuntime.availableProcessors * 2) // ForkJoinTasks.defaultForkJoinPool.setParallelism(Runtime.getRuntime.availableProcessors * 2) - type CollType = ParCtrie[K, V] + type CollType = ParConcurrentTrieMap[K, V] def isCheckingViews = false def hasStrictOrder = false def ofSize(vals: Seq[Gen[(K, V)]], sz: Int) = { - val ct = new mutable.Ctrie[K, V] + val ct = new mutable.ConcurrentTrieMap[K, V] val gen = vals(rnd.nextInt(vals.size)) for (i <- 0 until sz) ct += sample(gen) ct } def fromTraversable(t: Traversable[(K, V)]) = { - val pct = new ParCtrie[K, V] + val pct = new ParConcurrentTrieMap[K, V] var i = 0 for (kv <- t.toList) { pct += kv @@ -45,7 +45,7 @@ abstract class ParallelCtrieCheck[K, V](tp: String) extends ParallelMapCheck[K, } -object IntIntParallelCtrieCheck extends ParallelCtrieCheck[Int, Int]("Int, Int") +object IntIntParallelConcurrentTrieMapCheck extends ParallelConcurrentTrieMapCheck[Int, Int]("Int, Int") with PairOperators[Int, Int] with PairValues[Int, Int] { @@ -58,7 +58,7 @@ with PairValues[Int, Int] def koperators = intoperators override def printDataStructureDebugInfo(ds: AnyRef) = ds match { - case pm: ParCtrie[k, v] => + case pm: ParConcurrentTrieMap[k, v] => println("Mutable parallel ctrie") case _ => println("could not match data structure type: " + ds.getClass) diff --git a/test/files/scalacheck/parallel-collections/pc.scala b/test/files/scalacheck/parallel-collections/pc.scala index 8a0dba3c25..0a91977da0 100644 --- a/test/files/scalacheck/parallel-collections/pc.scala +++ b/test/files/scalacheck/parallel-collections/pc.scala @@ -26,7 +26,7 @@ class ParCollProperties extends Properties("Parallel collections") { include(mutable.IntIntParallelHashMapCheck) // parallel ctrie - include(mutable.IntIntParallelCtrieCheck) + include(mutable.IntIntParallelConcurrentTrieMapCheck) // parallel mutable hash sets (tables) include(mutable.IntParallelHashSetCheck) -- cgit v1.2.3 From dd24b6a21616cbec49f3df22735374c474b5511b Mon Sep 17 00:00:00 2001 From: Aleksandar Prokopec Date: Fri, 16 Mar 2012 16:12:49 +0100 Subject: Renamed concurrent trie source files. --- .../collection/mutable/ConcurrentTrieMap.scala | 1075 ++++++++++++++++++++ src/library/scala/collection/mutable/Ctrie.scala | 1075 -------------------- .../parallel/mutable/ParConcurrentTrieMap.scala | 193 ++++ .../collection/parallel/mutable/ParCtrie.scala | 193 ---- 4 files changed, 1268 insertions(+), 1268 deletions(-) create mode 100644 src/library/scala/collection/mutable/ConcurrentTrieMap.scala delete mode 100644 src/library/scala/collection/mutable/Ctrie.scala create mode 100644 src/library/scala/collection/parallel/mutable/ParConcurrentTrieMap.scala delete mode 100644 src/library/scala/collection/parallel/mutable/ParCtrie.scala (limited to 'src/library') diff --git a/src/library/scala/collection/mutable/ConcurrentTrieMap.scala b/src/library/scala/collection/mutable/ConcurrentTrieMap.scala new file mode 100644 index 0000000000..1a44c8e423 --- /dev/null +++ b/src/library/scala/collection/mutable/ConcurrentTrieMap.scala @@ -0,0 +1,1075 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2012, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection +package mutable + + + +import java.util.concurrent.atomic._ +import collection.immutable.{ ListMap => ImmutableListMap } +import collection.parallel.mutable.ParConcurrentTrieMap +import generic._ +import annotation.tailrec +import annotation.switch + + + +private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends INodeBase[K, V](g) { + import INodeBase._ + + WRITE(bn) + + def this(g: Gen) = this(null, g) + + @inline final def WRITE(nval: MainNode[K, V]) = INodeBase.updater.set(this, nval) + + @inline final def CAS(old: MainNode[K, V], n: MainNode[K, V]) = INodeBase.updater.compareAndSet(this, old, n) + + final def gcasRead(ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = GCAS_READ(ct) + + @inline final def GCAS_READ(ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = { + val m = /*READ*/mainnode + val prevval = /*READ*/m.prev + if (prevval eq null) m + else GCAS_Complete(m, ct) + } + + @tailrec private def GCAS_Complete(m: MainNode[K, V], ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = if (m eq null) null else { + // complete the GCAS + val prev = /*READ*/m.prev + val ctr = ct.readRoot(true) + + prev match { + case null => + m + case fn: FailedNode[_, _] => // try to commit to previous value + if (CAS(m, fn.prev)) fn.prev + else GCAS_Complete(/*READ*/mainnode, ct) + case vn: MainNode[_, _] => + // Assume that you've read the root from the generation G. + // Assume that the snapshot algorithm is correct. + // ==> you can only reach nodes in generations <= G. + // ==> `gen` is <= G. + // We know that `ctr.gen` is >= G. + // ==> if `ctr.gen` = `gen` then they are both equal to G. + // ==> otherwise, we know that either `ctr.gen` > G, `gen` < G, + // or both + if ((ctr.gen eq gen) && ct.nonReadOnly) { + // try to commit + if (m.CAS_PREV(prev, null)) m + else GCAS_Complete(m, ct) + } else { + // try to abort + m.CAS_PREV(prev, new FailedNode(prev)) + GCAS_Complete(/*READ*/mainnode, ct) + } + } + } + + @inline final def GCAS(old: MainNode[K, V], n: MainNode[K, V], ct: ConcurrentTrieMap[K, V]): Boolean = { + n.WRITE_PREV(old) + if (CAS(old, n)) { + GCAS_Complete(n, ct) + /*READ*/n.prev eq null + } else false + } + + @inline private def inode(cn: MainNode[K, V]) = { + val nin = new INode[K, V](gen) + nin.WRITE(cn) + nin + } + + final def copyToGen(ngen: Gen, ct: ConcurrentTrieMap[K, V]) = { + val nin = new INode[K, V](ngen) + val main = GCAS_READ(ct) + nin.WRITE(main) + nin + } + + /** Inserts a key value pair, overwriting the old pair if the keys match. + * + * @return true if successful, false otherwise + */ + @tailrec final def rec_insert(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Boolean = { + val m = GCAS_READ(ct) // use -Yinline! + + m match { + case cn: CNode[K, V] => // 1) a multiway node + val idx = (hc >>> lev) & 0x1f + val flag = 1 << idx + val bmp = cn.bitmap + val mask = flag - 1 + val pos = Integer.bitCount(bmp & mask) + if ((bmp & flag) != 0) { + // 1a) insert below + cn.array(pos) match { + case in: INode[K, V] => + if (startgen eq in.gen) in.rec_insert(k, v, hc, lev + 5, this, startgen, ct) + else { + if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_insert(k, v, hc, lev, parent, startgen, ct) + else false + } + case sn: SNode[K, V] => + if (sn.hc == hc && sn.k == k) GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct) + else { + val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) + val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) + GCAS(cn, nn, ct) + } + } + } else { + val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) + val ncnode = rn.insertedAt(pos, flag, new SNode(k, v, hc), gen) + GCAS(cn, ncnode, ct) + } + case tn: TNode[K, V] => + clean(parent, ct, lev - 5) + false + case ln: LNode[K, V] => // 3) an l-node + val nn = ln.inserted(k, v) + GCAS(ln, nn, ct) + } + } + + /** Inserts a new key value pair, given that a specific condition is met. + * + * @param cond null - don't care if the key was there; KEY_ABSENT - key wasn't there; KEY_PRESENT - key was there; other value `v` - key must be bound to `v` + * @return null if unsuccessful, Option[V] otherwise (indicating previous value bound to the key) + */ + @tailrec final def rec_insertif(k: K, v: V, hc: Int, cond: AnyRef, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Option[V] = { + val m = GCAS_READ(ct) // use -Yinline! + + m match { + case cn: CNode[K, V] => // 1) a multiway node + val idx = (hc >>> lev) & 0x1f + val flag = 1 << idx + val bmp = cn.bitmap + val mask = flag - 1 + val pos = Integer.bitCount(bmp & mask) + if ((bmp & flag) != 0) { + // 1a) insert below + cn.array(pos) match { + case in: INode[K, V] => + if (startgen eq in.gen) in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct) + else { + if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_insertif(k, v, hc, cond, lev, parent, startgen, ct) + else null + } + case sn: SNode[K, V] => cond match { + case null => + if (sn.hc == hc && sn.k == k) { + if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null + } else { + val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) + val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) + if (GCAS(cn, nn, ct)) None + else null + } + case INode.KEY_ABSENT => + if (sn.hc == hc && sn.k == k) Some(sn.v) + else { + val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) + val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) + if (GCAS(cn, nn, ct)) None + else null + } + case INode.KEY_PRESENT => + if (sn.hc == hc && sn.k == k) { + if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null + } else None + case otherv: V => + if (sn.hc == hc && sn.k == k && sn.v == otherv) { + if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null + } else None + } + } + } else cond match { + case null | INode.KEY_ABSENT => + val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) + val ncnode = rn.insertedAt(pos, flag, new SNode(k, v, hc), gen) + if (GCAS(cn, ncnode, ct)) None else null + case INode.KEY_PRESENT => None + case otherv: V => None + } + case sn: TNode[K, V] => + clean(parent, ct, lev - 5) + null + case ln: LNode[K, V] => // 3) an l-node + @inline def insertln() = { + val nn = ln.inserted(k, v) + GCAS(ln, nn, ct) + } + cond match { + case null => + val optv = ln.get(k) + if (insertln()) optv else null + case INode.KEY_ABSENT => + ln.get(k) match { + case None => if (insertln()) None else null + case optv => optv + } + case INode.KEY_PRESENT => + ln.get(k) match { + case Some(v0) => if (insertln()) Some(v0) else null + case None => None + } + case otherv: V => + ln.get(k) match { + case Some(v0) if v0 == otherv => if (insertln()) Some(otherv) else null + case _ => None + } + } + } + } + + /** Looks up the value associated with the key. + * + * @return null if no value has been found, RESTART if the operation wasn't successful, or any other value otherwise + */ + @tailrec final def rec_lookup(k: K, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): AnyRef = { + val m = GCAS_READ(ct) // use -Yinline! + + m match { + case cn: CNode[K, V] => // 1) a multinode + val idx = (hc >>> lev) & 0x1f + val flag = 1 << idx + val bmp = cn.bitmap + if ((bmp & flag) == 0) null // 1a) bitmap shows no binding + else { // 1b) bitmap contains a value - descend + val pos = if (bmp == 0xffffffff) idx else Integer.bitCount(bmp & (flag - 1)) + val sub = cn.array(pos) + sub match { + case in: INode[K, V] => + if (ct.isReadOnly || (startgen eq in.gen)) in.rec_lookup(k, hc, lev + 5, this, startgen, ct) + else { + if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_lookup(k, hc, lev, parent, startgen, ct) + else return RESTART // used to be throw RestartException + } + case sn: SNode[K, V] => // 2) singleton node + if (sn.hc == hc && sn.k == k) sn.v.asInstanceOf[AnyRef] + else null + } + } + case tn: TNode[K, V] => // 3) non-live node + def cleanReadOnly(tn: TNode[K, V]) = if (ct.nonReadOnly) { + clean(parent, ct, lev - 5) + RESTART // used to be throw RestartException + } else { + if (tn.hc == hc && tn.k == k) tn.v.asInstanceOf[AnyRef] + else null + } + cleanReadOnly(tn) + case ln: LNode[K, V] => // 5) an l-node + ln.get(k).asInstanceOf[Option[AnyRef]].orNull + } + } + + /** Removes the key associated with the given value. + * + * @param v if null, will remove the key irregardless of the value; otherwise removes only if binding contains that exact key and value + * @return null if not successful, an Option[V] indicating the previous value otherwise + */ + final def rec_remove(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Option[V] = { + val m = GCAS_READ(ct) // use -Yinline! + + m match { + case cn: CNode[K, V] => + val idx = (hc >>> lev) & 0x1f + val bmp = cn.bitmap + val flag = 1 << idx + if ((bmp & flag) == 0) None + else { + val pos = Integer.bitCount(bmp & (flag - 1)) + val sub = cn.array(pos) + val res = sub match { + case in: INode[K, V] => + if (startgen eq in.gen) in.rec_remove(k, v, hc, lev + 5, this, startgen, ct) + else { + if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_remove(k, v, hc, lev, parent, startgen, ct) + else null + } + case sn: SNode[K, V] => + if (sn.hc == hc && sn.k == k && (v == null || sn.v == v)) { + val ncn = cn.removedAt(pos, flag, gen).toContracted(lev) + if (GCAS(cn, ncn, ct)) Some(sn.v) else null + } else None + } + + if (res == None || (res eq null)) res + else { + @tailrec def cleanParent(nonlive: AnyRef) { + val pm = parent.GCAS_READ(ct) + pm match { + case cn: CNode[K, V] => + val idx = (hc >>> (lev - 5)) & 0x1f + val bmp = cn.bitmap + val flag = 1 << idx + if ((bmp & flag) == 0) {} // somebody already removed this i-node, we're done + else { + val pos = Integer.bitCount(bmp & (flag - 1)) + val sub = cn.array(pos) + if (sub eq this) nonlive match { + case tn: TNode[K, V] => + val ncn = cn.updatedAt(pos, tn.copyUntombed, gen).toContracted(lev - 5) + if (!parent.GCAS(cn, ncn, ct)) + if (ct.readRoot().gen == startgen) cleanParent(nonlive) + } + } + case _ => // parent is no longer a cnode, we're done + } + } + + if (parent ne null) { // never tomb at root + val n = GCAS_READ(ct) + if (n.isInstanceOf[TNode[_, _]]) + cleanParent(n) + } + + res + } + } + case tn: TNode[K, V] => + clean(parent, ct, lev - 5) + null + case ln: LNode[K, V] => + if (v == null) { + val optv = ln.get(k) + val nn = ln.removed(k) + if (GCAS(ln, nn, ct)) optv else null + } else ln.get(k) match { + case optv @ Some(v0) if v0 == v => + val nn = ln.removed(k) + if (GCAS(ln, nn, ct)) optv else null + case _ => None + } + } + } + + private def clean(nd: INode[K, V], ct: ConcurrentTrieMap[K, V], lev: Int) { + val m = nd.GCAS_READ(ct) + m match { + case cn: CNode[K, V] => nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct) + case _ => + } + } + + final def isNullInode(ct: ConcurrentTrieMap[K, V]) = GCAS_READ(ct) eq null + + final def cachedSize(ct: ConcurrentTrieMap[K, V]): Int = { + val m = GCAS_READ(ct) + m.cachedSize(ct) + } + + /* this is a quiescent method! */ + def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode match { + case null => "" + case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v, tn.hc) + case cn: CNode[_, _] => cn.string(lev) + case ln: LNode[_, _] => ln.string(lev) + case x => "".format(x) + }) + +} + + +private[mutable] object INode { + val KEY_PRESENT = new AnyRef + val KEY_ABSENT = new AnyRef + + def newRootNode[K, V] = { + val gen = new Gen + val cn = new CNode[K, V](0, new Array(0), gen) + new INode[K, V](cn, gen) + } +} + + +private[mutable] final class FailedNode[K, V](p: MainNode[K, V]) extends MainNode[K, V] { + WRITE_PREV(p) + + def string(lev: Int) = throw new UnsupportedOperationException + + def cachedSize(ct: AnyRef): Int = throw new UnsupportedOperationException + + override def toString = "FailedNode(%s)".format(p) +} + + +private[mutable] trait KVNode[K, V] { + def kvPair: (K, V) +} + + +private[collection] final class SNode[K, V](final val k: K, final val v: V, final val hc: Int) +extends BasicNode with KVNode[K, V] { + final def copy = new SNode(k, v, hc) + final def copyTombed = new TNode(k, v, hc) + final def copyUntombed = new SNode(k, v, hc) + final def kvPair = (k, v) + final def string(lev: Int) = (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc) +} + + +private[collection] final class TNode[K, V](final val k: K, final val v: V, final val hc: Int) +extends MainNode[K, V] with KVNode[K, V] { + final def copy = new TNode(k, v, hc) + final def copyTombed = new TNode(k, v, hc) + final def copyUntombed = new SNode(k, v, hc) + final def kvPair = (k, v) + final def cachedSize(ct: AnyRef): Int = 1 + final def string(lev: Int) = (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc) +} + + +private[collection] final class LNode[K, V](final val listmap: ImmutableListMap[K, V]) +extends MainNode[K, V] { + def this(k: K, v: V) = this(ImmutableListMap(k -> v)) + def this(k1: K, v1: V, k2: K, v2: V) = this(ImmutableListMap(k1 -> v1, k2 -> v2)) + def inserted(k: K, v: V) = new LNode(listmap + ((k, v))) + def removed(k: K): MainNode[K, V] = { + val updmap = listmap - k + if (updmap.size > 1) new LNode(updmap) + else { + val (k, v) = updmap.iterator.next + new TNode(k, v, ConcurrentTrieMap.computeHash(k)) // create it tombed so that it gets compressed on subsequent accesses + } + } + def get(k: K) = listmap.get(k) + def cachedSize(ct: AnyRef): Int = listmap.size + def string(lev: Int) = (" " * lev) + "LNode(%s)".format(listmap.mkString(", ")) +} + + +private[collection] final class CNode[K, V](final val bitmap: Int, final val array: Array[BasicNode], final val gen: Gen) +extends CNodeBase[K, V] { + + // this should only be called from within read-only snapshots + final def cachedSize(ct: AnyRef) = { + val currsz = READ_SIZE() + if (currsz != -1) currsz + else { + val sz = computeSize(ct.asInstanceOf[ConcurrentTrieMap[K, V]]) + while (READ_SIZE() == -1) CAS_SIZE(-1, sz) + READ_SIZE() + } + } + + // lends itself towards being parallelizable by choosing + // a random starting offset in the array + // => if there are concurrent size computations, they start + // at different positions, so they are more likely to + // to be independent + private def computeSize(ct: ConcurrentTrieMap[K, V]): Int = { + var i = 0 + var sz = 0 + val offset = math.abs(util.Random.nextInt()) % array.length + while (i < array.length) { + val pos = (i + offset) % array.length + array(pos) match { + case sn: SNode[_, _] => sz += 1 + case in: INode[K, V] => sz += in.cachedSize(ct) + } + i += 1 + } + sz + } + + final def updatedAt(pos: Int, nn: BasicNode, gen: Gen) = { + val len = array.length + val narr = new Array[BasicNode](len) + Array.copy(array, 0, narr, 0, len) + narr(pos) = nn + new CNode[K, V](bitmap, narr, gen) + } + + final def removedAt(pos: Int, flag: Int, gen: Gen) = { + val arr = array + val len = arr.length + val narr = new Array[BasicNode](len - 1) + Array.copy(arr, 0, narr, 0, pos) + Array.copy(arr, pos + 1, narr, pos, len - pos - 1) + new CNode[K, V](bitmap ^ flag, narr, gen) + } + + final def insertedAt(pos: Int, flag: Int, nn: BasicNode, gen: Gen) = { + val len = array.length + val bmp = bitmap + val narr = new Array[BasicNode](len + 1) + Array.copy(array, 0, narr, 0, pos) + narr(pos) = nn + Array.copy(array, pos, narr, pos + 1, len - pos) + new CNode[K, V](bmp | flag, narr, gen) + } + + /** Returns a copy of this cnode such that all the i-nodes below it are copied + * to the specified generation `ngen`. + */ + final def renewed(ngen: Gen, ct: ConcurrentTrieMap[K, V]) = { + var i = 0 + val arr = array + val len = arr.length + val narr = new Array[BasicNode](len) + while (i < len) { + arr(i) match { + case in: INode[K, V] => narr(i) = in.copyToGen(ngen, ct) + case bn: BasicNode => narr(i) = bn + } + i += 1 + } + new CNode[K, V](bitmap, narr, ngen) + } + + private def resurrect(inode: INode[K, V], inodemain: AnyRef): BasicNode = inodemain match { + case tn: TNode[_, _] => tn.copyUntombed + case _ => inode + } + + final def toContracted(lev: Int): MainNode[K, V] = if (array.length == 1 && lev > 0) array(0) match { + case sn: SNode[K, V] => sn.copyTombed + case _ => this + } else this + + // - if the branching factor is 1 for this CNode, and the child + // is a tombed SNode, returns its tombed version + // - otherwise, if there is at least one non-null node below, + // returns the version of this node with at least some null-inodes + // removed (those existing when the op began) + // - if there are only null-i-nodes below, returns null + final def toCompressed(ct: ConcurrentTrieMap[K, V], lev: Int, gen: Gen) = { + var bmp = bitmap + var i = 0 + val arr = array + val tmparray = new Array[BasicNode](arr.length) + while (i < arr.length) { // construct new bitmap + val sub = arr(i) + sub match { + case in: INode[K, V] => + val inodemain = in.gcasRead(ct) + assert(inodemain ne null) + tmparray(i) = resurrect(in, inodemain) + case sn: SNode[K, V] => + tmparray(i) = sn + } + i += 1 + } + + new CNode[K, V](bmp, tmparray, gen).toContracted(lev) + } + + private[mutable] def string(lev: Int): String = "CNode %x\n%s".format(bitmap, array.map(_.string(lev + 1)).mkString("\n")) + + /* quiescently consistent - don't call concurrently to anything involving a GCAS!! */ + protected def collectElems: Seq[(K, V)] = array flatMap { + case sn: SNode[K, V] => Some(sn.kvPair) + case in: INode[K, V] => in.mainnode match { + case tn: TNode[K, V] => Some(tn.kvPair) + case ln: LNode[K, V] => ln.listmap.toList + case cn: CNode[K, V] => cn.collectElems + } + } + + protected def collectLocalElems: Seq[String] = array flatMap { + case sn: SNode[K, V] => Some(sn.kvPair._2.toString) + case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen + ")") + } + + override def toString = { + val elems = collectLocalElems + "CNode(sz: %d; %s)".format(elems.size, elems.sorted.mkString(", ")) + } +} + + +private[mutable] object CNode { + + def dual[K, V](x: SNode[K, V], xhc: Int, y: SNode[K, V], yhc: Int, lev: Int, gen: Gen): MainNode[K, V] = if (lev < 35) { + val xidx = (xhc >>> lev) & 0x1f + val yidx = (yhc >>> lev) & 0x1f + val bmp = (1 << xidx) | (1 << yidx) + if (xidx == yidx) { + val subinode = new INode[K, V](gen)//(ConcurrentTrieMap.inodeupdater) + subinode.mainnode = dual(x, xhc, y, yhc, lev + 5, gen) + new CNode(bmp, Array(subinode), gen) + } else { + if (xidx < yidx) new CNode(bmp, Array(x, y), gen) + else new CNode(bmp, Array(y, x), gen) + } + } else { + new LNode(x.k, x.v, y.k, y.v) + } + +} + + +private[mutable] case class RDCSS_Descriptor[K, V](old: INode[K, V], expectedmain: MainNode[K, V], nv: INode[K, V]) { + @volatile var committed = false +} + + +/** A concurrent hash-trie or ConcurrentTrieMap is a concurrent thread-safe lock-free + * implementation of a hash array mapped trie. It is used to implement the + * concurrent map abstraction. It has particularly scalable concurrent insert + * and remove operations and is memory-efficient. It supports O(1), atomic, + * lock-free snapshots which are used to implement linearizable lock-free size, + * iterator and clear operations. The cost of evaluating the (lazy) snapshot is + * distributed across subsequent updates, thus making snapshot evaluation horizontally scalable. + * + * For details, see: http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf + * + * @author Aleksandar Prokopec + * @since 2.10 + */ +@SerialVersionUID(0L - 6402774413839597105L) +final class ConcurrentTrieMap[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[ConcurrentTrieMap[K, V], AnyRef]) +extends ConcurrentMap[K, V] + with MapLike[K, V, ConcurrentTrieMap[K, V]] + with CustomParallelizable[(K, V), ParConcurrentTrieMap[K, V]] + with Serializable +{ + import ConcurrentTrieMap.computeHash + + private var rootupdater = rtupd + @volatile var root = r + + def this() = this( + INode.newRootNode, + AtomicReferenceFieldUpdater.newUpdater(classOf[ConcurrentTrieMap[K, V]], classOf[AnyRef], "root") + ) + + /* internal methods */ + + private def writeObject(out: java.io.ObjectOutputStream) { + val it = iterator + while (it.hasNext) { + val (k, v) = it.next() + out.writeObject(k) + out.writeObject(v) + } + out.writeObject(ConcurrentTrieMapSerializationEnd) + } + + private def readObject(in: java.io.ObjectInputStream) { + root = INode.newRootNode + rootupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[ConcurrentTrieMap[K, V]], classOf[AnyRef], "root") + + var obj: AnyRef = null + do { + obj = in.readObject() + if (obj != ConcurrentTrieMapSerializationEnd) { + val k = obj.asInstanceOf[K] + val v = in.readObject().asInstanceOf[V] + update(k, v) + } + } while (obj != ConcurrentTrieMapSerializationEnd) + } + + @inline final def CAS_ROOT(ov: AnyRef, nv: AnyRef) = rootupdater.compareAndSet(this, ov, nv) + + final def readRoot(abort: Boolean = false): INode[K, V] = RDCSS_READ_ROOT(abort) + + @inline final def RDCSS_READ_ROOT(abort: Boolean = false): INode[K, V] = { + val r = /*READ*/root + r match { + case in: INode[K, V] => in + case desc: RDCSS_Descriptor[K, V] => RDCSS_Complete(abort) + } + } + + @tailrec private def RDCSS_Complete(abort: Boolean): INode[K, V] = { + val v = /*READ*/root + v match { + case in: INode[K, V] => in + case desc: RDCSS_Descriptor[K, V] => + val RDCSS_Descriptor(ov, exp, nv) = desc + if (abort) { + if (CAS_ROOT(desc, ov)) ov + else RDCSS_Complete(abort) + } else { + val oldmain = ov.gcasRead(this) + if (oldmain eq exp) { + if (CAS_ROOT(desc, nv)) { + desc.committed = true + nv + } else RDCSS_Complete(abort) + } else { + if (CAS_ROOT(desc, ov)) ov + else RDCSS_Complete(abort) + } + } + } + } + + private def RDCSS_ROOT(ov: INode[K, V], expectedmain: MainNode[K, V], nv: INode[K, V]): Boolean = { + val desc = RDCSS_Descriptor(ov, expectedmain, nv) + if (CAS_ROOT(ov, desc)) { + RDCSS_Complete(false) + /*READ*/desc.committed + } else false + } + + @tailrec private def inserthc(k: K, hc: Int, v: V) { + val r = RDCSS_READ_ROOT() + if (!r.rec_insert(k, v, hc, 0, null, r.gen, this)) inserthc(k, hc, v) + } + + @tailrec private def insertifhc(k: K, hc: Int, v: V, cond: AnyRef): Option[V] = { + val r = RDCSS_READ_ROOT() + + val ret = r.rec_insertif(k, v, hc, cond, 0, null, r.gen, this) + if (ret eq null) insertifhc(k, hc, v, cond) + else ret + } + + @tailrec private def lookuphc(k: K, hc: Int): AnyRef = { + val r = RDCSS_READ_ROOT() + val res = r.rec_lookup(k, hc, 0, null, r.gen, this) + if (res eq INodeBase.RESTART) lookuphc(k, hc) + else res + } + + /* slower: + //@tailrec + private def lookuphc(k: K, hc: Int): AnyRef = { + val r = RDCSS_READ_ROOT() + try { + r.rec_lookup(k, hc, 0, null, r.gen, this) + } catch { + case RestartException => + lookuphc(k, hc) + } + } + */ + + @tailrec private def removehc(k: K, v: V, hc: Int): Option[V] = { + val r = RDCSS_READ_ROOT() + val res = r.rec_remove(k, v, hc, 0, null, r.gen, this) + if (res ne null) res + else removehc(k, v, hc) + } + + def string = RDCSS_READ_ROOT().string(0) + + /* public methods */ + + override def seq = this + + override def par = new ParConcurrentTrieMap(this) + + override def empty: ConcurrentTrieMap[K, V] = new ConcurrentTrieMap[K, V] + + final def isReadOnly = rootupdater eq null + + final def nonReadOnly = rootupdater ne null + + /** Returns a snapshot of this ConcurrentTrieMap. + * This operation is lock-free and linearizable. + * + * The snapshot is lazily updated - the first time some branch + * in the snapshot or this ConcurrentTrieMap are accessed, they are rewritten. + * This means that the work of rebuilding both the snapshot and this + * ConcurrentTrieMap is distributed across all the threads doing updates or accesses + * subsequent to the snapshot creation. + */ + @tailrec final def snapshot(): ConcurrentTrieMap[K, V] = { + val r = RDCSS_READ_ROOT() + val expmain = r.gcasRead(this) + if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new ConcurrentTrieMap(r.copyToGen(new Gen, this), rootupdater) + else snapshot() + } + + /** Returns a read-only snapshot of this ConcurrentTrieMap. + * This operation is lock-free and linearizable. + * + * The snapshot is lazily updated - the first time some branch + * of this ConcurrentTrieMap are accessed, it is rewritten. The work of creating + * the snapshot is thus distributed across subsequent updates + * and accesses on this ConcurrentTrieMap by all threads. + * Note that the snapshot itself is never rewritten unlike when calling + * the `snapshot` method, but the obtained snapshot cannot be modified. + * + * This method is used by other methods such as `size` and `iterator`. + */ + @tailrec final def readOnlySnapshot(): collection.Map[K, V] = { + val r = RDCSS_READ_ROOT() + val expmain = r.gcasRead(this) + if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new ConcurrentTrieMap(r, null) + else readOnlySnapshot() + } + + @tailrec final override def clear() { + val r = RDCSS_READ_ROOT() + if (!RDCSS_ROOT(r, r.gcasRead(this), INode.newRootNode[K, V])) clear() + } + + final def lookup(k: K): V = { + val hc = computeHash(k) + lookuphc(k, hc).asInstanceOf[V] + } + + final override def apply(k: K): V = { + val hc = computeHash(k) + val res = lookuphc(k, hc) + if (res eq null) throw new NoSuchElementException + else res.asInstanceOf[V] + } + + final def get(k: K): Option[V] = { + val hc = computeHash(k) + Option(lookuphc(k, hc)).asInstanceOf[Option[V]] + } + + override def put(key: K, value: V): Option[V] = { + val hc = computeHash(key) + insertifhc(key, hc, value, null) + } + + final override def update(k: K, v: V) { + val hc = computeHash(k) + inserthc(k, hc, v) + } + + final def +=(kv: (K, V)) = { + update(kv._1, kv._2) + this + } + + final override def remove(k: K): Option[V] = { + val hc = computeHash(k) + removehc(k, null.asInstanceOf[V], hc) + } + + final def -=(k: K) = { + remove(k) + this + } + + def putIfAbsent(k: K, v: V): Option[V] = { + val hc = computeHash(k) + insertifhc(k, hc, v, INode.KEY_ABSENT) + } + + def remove(k: K, v: V): Boolean = { + val hc = computeHash(k) + removehc(k, v, hc).nonEmpty + } + + def replace(k: K, oldvalue: V, newvalue: V): Boolean = { + val hc = computeHash(k) + insertifhc(k, hc, newvalue, oldvalue.asInstanceOf[AnyRef]).nonEmpty + } + + def replace(k: K, v: V): Option[V] = { + val hc = computeHash(k) + insertifhc(k, hc, v, INode.KEY_PRESENT) + } + + def iterator: Iterator[(K, V)] = + if (nonReadOnly) readOnlySnapshot().iterator + else new ConcurrentTrieMapIterator(0, this) + + private def cachedSize() = { + val r = RDCSS_READ_ROOT() + r.cachedSize(this) + } + + override def size: Int = + if (nonReadOnly) readOnlySnapshot().size + else cachedSize() + + override def stringPrefix = "ConcurrentTrieMap" + +} + + +object ConcurrentTrieMap extends MutableMapFactory[ConcurrentTrieMap] { + val inodeupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[INodeBase[_, _]], classOf[MainNode[_, _]], "mainnode") + + implicit def canBuildFrom[K, V]: CanBuildFrom[Coll, (K, V), ConcurrentTrieMap[K, V]] = new MapCanBuildFrom[K, V] + + def empty[K, V]: ConcurrentTrieMap[K, V] = new ConcurrentTrieMap[K, V] + + @inline final def computeHash[K](k: K): Int = { + var hcode = k.hashCode + hcode = hcode * 0x9e3775cd + hcode = java.lang.Integer.reverseBytes(hcode) + hcode * 0x9e3775cd + } + +} + + +private[collection] class ConcurrentTrieMapIterator[K, V](var level: Int, private var ct: ConcurrentTrieMap[K, V], mustInit: Boolean = true) extends Iterator[(K, V)] { + var stack = new Array[Array[BasicNode]](7) + var stackpos = new Array[Int](7) + var depth = -1 + var subiter: Iterator[(K, V)] = null + var current: KVNode[K, V] = null + + if (mustInit) initialize() + + def hasNext = (current ne null) || (subiter ne null) + + def next() = if (hasNext) { + var r: (K, V) = null + if (subiter ne null) { + r = subiter.next() + checkSubiter() + } else { + r = current.kvPair + advance() + } + r + } else Iterator.empty.next() + + private def readin(in: INode[K, V]) = in.gcasRead(ct) match { + case cn: CNode[K, V] => + depth += 1 + stack(depth) = cn.array + stackpos(depth) = -1 + advance() + case tn: TNode[K, V] => + current = tn + case ln: LNode[K, V] => + subiter = ln.listmap.iterator + checkSubiter() + case null => + current = null + } + + @inline private def checkSubiter() = if (!subiter.hasNext) { + subiter = null + advance() + } + + @inline private def initialize() { + assert(ct.isReadOnly) + + val r = ct.RDCSS_READ_ROOT() + readin(r) + } + + def advance(): Unit = if (depth >= 0) { + val npos = stackpos(depth) + 1 + if (npos < stack(depth).length) { + stackpos(depth) = npos + stack(depth)(npos) match { + case sn: SNode[K, V] => + current = sn + case in: INode[K, V] => + readin(in) + } + } else { + depth -= 1 + advance() + } + } else current = null + + protected def newIterator(_lev: Int, _ct: ConcurrentTrieMap[K, V], _mustInit: Boolean) = new ConcurrentTrieMapIterator[K, V](_lev, _ct, _mustInit) + + protected def dupTo(it: ConcurrentTrieMapIterator[K, V]) = { + it.level = this.level + it.ct = this.ct + it.depth = this.depth + it.current = this.current + + // these need a deep copy + Array.copy(this.stack, 0, it.stack, 0, 7) + Array.copy(this.stackpos, 0, it.stackpos, 0, 7) + + // this one needs to be evaluated + if (this.subiter == null) it.subiter = null + else { + val lst = this.subiter.toList + this.subiter = lst.iterator + it.subiter = lst.iterator + } + } + + /** Returns a sequence of iterators over subsets of this iterator. + * It's used to ease the implementation of splitters for a parallel version of the ConcurrentTrieMap. + */ + protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne null) { + // the case where an LNode is being iterated + val it = subiter + subiter = null + advance() + this.level += 1 + Seq(it, this) + } else if (depth == -1) { + this.level += 1 + Seq(this) + } else { + var d = 0 + while (d <= depth) { + val rem = stack(d).length - 1 - stackpos(d) + if (rem > 0) { + val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2) + stack(d) = arr1 + stackpos(d) = -1 + val it = newIterator(level + 1, ct, false) + it.stack(0) = arr2 + it.stackpos(0) = -1 + it.depth = 0 + it.advance() // <-- fix it + this.level += 1 + return Seq(this, it) + } + d += 1 + } + this.level += 1 + Seq(this) + } + + def printDebug { + println("ctrie iterator") + println(stackpos.mkString(",")) + println("depth: " + depth) + println("curr.: " + current) + println(stack.mkString("\n")) + } + +} + + +private[mutable] object RestartException extends util.control.ControlThrowable + + +/** Only used for ctrie serialization. */ +@SerialVersionUID(0L - 7237891413820527142L) +private[mutable] case object ConcurrentTrieMapSerializationEnd + + +private[mutable] object Debug { + import collection._ + + lazy val logbuffer = new java.util.concurrent.ConcurrentLinkedQueue[AnyRef] + + def log(s: AnyRef) = logbuffer.add(s) + + def flush() { + for (s <- JavaConversions.asScalaIterator(logbuffer.iterator())) Console.out.println(s.toString) + logbuffer.clear() + } + + def clear() { + logbuffer.clear() + } + +} + + + + + + + + + + diff --git a/src/library/scala/collection/mutable/Ctrie.scala b/src/library/scala/collection/mutable/Ctrie.scala deleted file mode 100644 index 1a44c8e423..0000000000 --- a/src/library/scala/collection/mutable/Ctrie.scala +++ /dev/null @@ -1,1075 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2012, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -package scala.collection -package mutable - - - -import java.util.concurrent.atomic._ -import collection.immutable.{ ListMap => ImmutableListMap } -import collection.parallel.mutable.ParConcurrentTrieMap -import generic._ -import annotation.tailrec -import annotation.switch - - - -private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends INodeBase[K, V](g) { - import INodeBase._ - - WRITE(bn) - - def this(g: Gen) = this(null, g) - - @inline final def WRITE(nval: MainNode[K, V]) = INodeBase.updater.set(this, nval) - - @inline final def CAS(old: MainNode[K, V], n: MainNode[K, V]) = INodeBase.updater.compareAndSet(this, old, n) - - final def gcasRead(ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = GCAS_READ(ct) - - @inline final def GCAS_READ(ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = { - val m = /*READ*/mainnode - val prevval = /*READ*/m.prev - if (prevval eq null) m - else GCAS_Complete(m, ct) - } - - @tailrec private def GCAS_Complete(m: MainNode[K, V], ct: ConcurrentTrieMap[K, V]): MainNode[K, V] = if (m eq null) null else { - // complete the GCAS - val prev = /*READ*/m.prev - val ctr = ct.readRoot(true) - - prev match { - case null => - m - case fn: FailedNode[_, _] => // try to commit to previous value - if (CAS(m, fn.prev)) fn.prev - else GCAS_Complete(/*READ*/mainnode, ct) - case vn: MainNode[_, _] => - // Assume that you've read the root from the generation G. - // Assume that the snapshot algorithm is correct. - // ==> you can only reach nodes in generations <= G. - // ==> `gen` is <= G. - // We know that `ctr.gen` is >= G. - // ==> if `ctr.gen` = `gen` then they are both equal to G. - // ==> otherwise, we know that either `ctr.gen` > G, `gen` < G, - // or both - if ((ctr.gen eq gen) && ct.nonReadOnly) { - // try to commit - if (m.CAS_PREV(prev, null)) m - else GCAS_Complete(m, ct) - } else { - // try to abort - m.CAS_PREV(prev, new FailedNode(prev)) - GCAS_Complete(/*READ*/mainnode, ct) - } - } - } - - @inline final def GCAS(old: MainNode[K, V], n: MainNode[K, V], ct: ConcurrentTrieMap[K, V]): Boolean = { - n.WRITE_PREV(old) - if (CAS(old, n)) { - GCAS_Complete(n, ct) - /*READ*/n.prev eq null - } else false - } - - @inline private def inode(cn: MainNode[K, V]) = { - val nin = new INode[K, V](gen) - nin.WRITE(cn) - nin - } - - final def copyToGen(ngen: Gen, ct: ConcurrentTrieMap[K, V]) = { - val nin = new INode[K, V](ngen) - val main = GCAS_READ(ct) - nin.WRITE(main) - nin - } - - /** Inserts a key value pair, overwriting the old pair if the keys match. - * - * @return true if successful, false otherwise - */ - @tailrec final def rec_insert(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Boolean = { - val m = GCAS_READ(ct) // use -Yinline! - - m match { - case cn: CNode[K, V] => // 1) a multiway node - val idx = (hc >>> lev) & 0x1f - val flag = 1 << idx - val bmp = cn.bitmap - val mask = flag - 1 - val pos = Integer.bitCount(bmp & mask) - if ((bmp & flag) != 0) { - // 1a) insert below - cn.array(pos) match { - case in: INode[K, V] => - if (startgen eq in.gen) in.rec_insert(k, v, hc, lev + 5, this, startgen, ct) - else { - if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_insert(k, v, hc, lev, parent, startgen, ct) - else false - } - case sn: SNode[K, V] => - if (sn.hc == hc && sn.k == k) GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct) - else { - val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) - val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) - GCAS(cn, nn, ct) - } - } - } else { - val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) - val ncnode = rn.insertedAt(pos, flag, new SNode(k, v, hc), gen) - GCAS(cn, ncnode, ct) - } - case tn: TNode[K, V] => - clean(parent, ct, lev - 5) - false - case ln: LNode[K, V] => // 3) an l-node - val nn = ln.inserted(k, v) - GCAS(ln, nn, ct) - } - } - - /** Inserts a new key value pair, given that a specific condition is met. - * - * @param cond null - don't care if the key was there; KEY_ABSENT - key wasn't there; KEY_PRESENT - key was there; other value `v` - key must be bound to `v` - * @return null if unsuccessful, Option[V] otherwise (indicating previous value bound to the key) - */ - @tailrec final def rec_insertif(k: K, v: V, hc: Int, cond: AnyRef, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Option[V] = { - val m = GCAS_READ(ct) // use -Yinline! - - m match { - case cn: CNode[K, V] => // 1) a multiway node - val idx = (hc >>> lev) & 0x1f - val flag = 1 << idx - val bmp = cn.bitmap - val mask = flag - 1 - val pos = Integer.bitCount(bmp & mask) - if ((bmp & flag) != 0) { - // 1a) insert below - cn.array(pos) match { - case in: INode[K, V] => - if (startgen eq in.gen) in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct) - else { - if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_insertif(k, v, hc, cond, lev, parent, startgen, ct) - else null - } - case sn: SNode[K, V] => cond match { - case null => - if (sn.hc == hc && sn.k == k) { - if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null - } else { - val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) - val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) - if (GCAS(cn, nn, ct)) None - else null - } - case INode.KEY_ABSENT => - if (sn.hc == hc && sn.k == k) Some(sn.v) - else { - val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) - val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) - if (GCAS(cn, nn, ct)) None - else null - } - case INode.KEY_PRESENT => - if (sn.hc == hc && sn.k == k) { - if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null - } else None - case otherv: V => - if (sn.hc == hc && sn.k == k && sn.v == otherv) { - if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null - } else None - } - } - } else cond match { - case null | INode.KEY_ABSENT => - val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) - val ncnode = rn.insertedAt(pos, flag, new SNode(k, v, hc), gen) - if (GCAS(cn, ncnode, ct)) None else null - case INode.KEY_PRESENT => None - case otherv: V => None - } - case sn: TNode[K, V] => - clean(parent, ct, lev - 5) - null - case ln: LNode[K, V] => // 3) an l-node - @inline def insertln() = { - val nn = ln.inserted(k, v) - GCAS(ln, nn, ct) - } - cond match { - case null => - val optv = ln.get(k) - if (insertln()) optv else null - case INode.KEY_ABSENT => - ln.get(k) match { - case None => if (insertln()) None else null - case optv => optv - } - case INode.KEY_PRESENT => - ln.get(k) match { - case Some(v0) => if (insertln()) Some(v0) else null - case None => None - } - case otherv: V => - ln.get(k) match { - case Some(v0) if v0 == otherv => if (insertln()) Some(otherv) else null - case _ => None - } - } - } - } - - /** Looks up the value associated with the key. - * - * @return null if no value has been found, RESTART if the operation wasn't successful, or any other value otherwise - */ - @tailrec final def rec_lookup(k: K, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): AnyRef = { - val m = GCAS_READ(ct) // use -Yinline! - - m match { - case cn: CNode[K, V] => // 1) a multinode - val idx = (hc >>> lev) & 0x1f - val flag = 1 << idx - val bmp = cn.bitmap - if ((bmp & flag) == 0) null // 1a) bitmap shows no binding - else { // 1b) bitmap contains a value - descend - val pos = if (bmp == 0xffffffff) idx else Integer.bitCount(bmp & (flag - 1)) - val sub = cn.array(pos) - sub match { - case in: INode[K, V] => - if (ct.isReadOnly || (startgen eq in.gen)) in.rec_lookup(k, hc, lev + 5, this, startgen, ct) - else { - if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_lookup(k, hc, lev, parent, startgen, ct) - else return RESTART // used to be throw RestartException - } - case sn: SNode[K, V] => // 2) singleton node - if (sn.hc == hc && sn.k == k) sn.v.asInstanceOf[AnyRef] - else null - } - } - case tn: TNode[K, V] => // 3) non-live node - def cleanReadOnly(tn: TNode[K, V]) = if (ct.nonReadOnly) { - clean(parent, ct, lev - 5) - RESTART // used to be throw RestartException - } else { - if (tn.hc == hc && tn.k == k) tn.v.asInstanceOf[AnyRef] - else null - } - cleanReadOnly(tn) - case ln: LNode[K, V] => // 5) an l-node - ln.get(k).asInstanceOf[Option[AnyRef]].orNull - } - } - - /** Removes the key associated with the given value. - * - * @param v if null, will remove the key irregardless of the value; otherwise removes only if binding contains that exact key and value - * @return null if not successful, an Option[V] indicating the previous value otherwise - */ - final def rec_remove(k: K, v: V, hc: Int, lev: Int, parent: INode[K, V], startgen: Gen, ct: ConcurrentTrieMap[K, V]): Option[V] = { - val m = GCAS_READ(ct) // use -Yinline! - - m match { - case cn: CNode[K, V] => - val idx = (hc >>> lev) & 0x1f - val bmp = cn.bitmap - val flag = 1 << idx - if ((bmp & flag) == 0) None - else { - val pos = Integer.bitCount(bmp & (flag - 1)) - val sub = cn.array(pos) - val res = sub match { - case in: INode[K, V] => - if (startgen eq in.gen) in.rec_remove(k, v, hc, lev + 5, this, startgen, ct) - else { - if (GCAS(cn, cn.renewed(startgen, ct), ct)) rec_remove(k, v, hc, lev, parent, startgen, ct) - else null - } - case sn: SNode[K, V] => - if (sn.hc == hc && sn.k == k && (v == null || sn.v == v)) { - val ncn = cn.removedAt(pos, flag, gen).toContracted(lev) - if (GCAS(cn, ncn, ct)) Some(sn.v) else null - } else None - } - - if (res == None || (res eq null)) res - else { - @tailrec def cleanParent(nonlive: AnyRef) { - val pm = parent.GCAS_READ(ct) - pm match { - case cn: CNode[K, V] => - val idx = (hc >>> (lev - 5)) & 0x1f - val bmp = cn.bitmap - val flag = 1 << idx - if ((bmp & flag) == 0) {} // somebody already removed this i-node, we're done - else { - val pos = Integer.bitCount(bmp & (flag - 1)) - val sub = cn.array(pos) - if (sub eq this) nonlive match { - case tn: TNode[K, V] => - val ncn = cn.updatedAt(pos, tn.copyUntombed, gen).toContracted(lev - 5) - if (!parent.GCAS(cn, ncn, ct)) - if (ct.readRoot().gen == startgen) cleanParent(nonlive) - } - } - case _ => // parent is no longer a cnode, we're done - } - } - - if (parent ne null) { // never tomb at root - val n = GCAS_READ(ct) - if (n.isInstanceOf[TNode[_, _]]) - cleanParent(n) - } - - res - } - } - case tn: TNode[K, V] => - clean(parent, ct, lev - 5) - null - case ln: LNode[K, V] => - if (v == null) { - val optv = ln.get(k) - val nn = ln.removed(k) - if (GCAS(ln, nn, ct)) optv else null - } else ln.get(k) match { - case optv @ Some(v0) if v0 == v => - val nn = ln.removed(k) - if (GCAS(ln, nn, ct)) optv else null - case _ => None - } - } - } - - private def clean(nd: INode[K, V], ct: ConcurrentTrieMap[K, V], lev: Int) { - val m = nd.GCAS_READ(ct) - m match { - case cn: CNode[K, V] => nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct) - case _ => - } - } - - final def isNullInode(ct: ConcurrentTrieMap[K, V]) = GCAS_READ(ct) eq null - - final def cachedSize(ct: ConcurrentTrieMap[K, V]): Int = { - val m = GCAS_READ(ct) - m.cachedSize(ct) - } - - /* this is a quiescent method! */ - def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode match { - case null => "" - case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v, tn.hc) - case cn: CNode[_, _] => cn.string(lev) - case ln: LNode[_, _] => ln.string(lev) - case x => "".format(x) - }) - -} - - -private[mutable] object INode { - val KEY_PRESENT = new AnyRef - val KEY_ABSENT = new AnyRef - - def newRootNode[K, V] = { - val gen = new Gen - val cn = new CNode[K, V](0, new Array(0), gen) - new INode[K, V](cn, gen) - } -} - - -private[mutable] final class FailedNode[K, V](p: MainNode[K, V]) extends MainNode[K, V] { - WRITE_PREV(p) - - def string(lev: Int) = throw new UnsupportedOperationException - - def cachedSize(ct: AnyRef): Int = throw new UnsupportedOperationException - - override def toString = "FailedNode(%s)".format(p) -} - - -private[mutable] trait KVNode[K, V] { - def kvPair: (K, V) -} - - -private[collection] final class SNode[K, V](final val k: K, final val v: V, final val hc: Int) -extends BasicNode with KVNode[K, V] { - final def copy = new SNode(k, v, hc) - final def copyTombed = new TNode(k, v, hc) - final def copyUntombed = new SNode(k, v, hc) - final def kvPair = (k, v) - final def string(lev: Int) = (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc) -} - - -private[collection] final class TNode[K, V](final val k: K, final val v: V, final val hc: Int) -extends MainNode[K, V] with KVNode[K, V] { - final def copy = new TNode(k, v, hc) - final def copyTombed = new TNode(k, v, hc) - final def copyUntombed = new SNode(k, v, hc) - final def kvPair = (k, v) - final def cachedSize(ct: AnyRef): Int = 1 - final def string(lev: Int) = (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc) -} - - -private[collection] final class LNode[K, V](final val listmap: ImmutableListMap[K, V]) -extends MainNode[K, V] { - def this(k: K, v: V) = this(ImmutableListMap(k -> v)) - def this(k1: K, v1: V, k2: K, v2: V) = this(ImmutableListMap(k1 -> v1, k2 -> v2)) - def inserted(k: K, v: V) = new LNode(listmap + ((k, v))) - def removed(k: K): MainNode[K, V] = { - val updmap = listmap - k - if (updmap.size > 1) new LNode(updmap) - else { - val (k, v) = updmap.iterator.next - new TNode(k, v, ConcurrentTrieMap.computeHash(k)) // create it tombed so that it gets compressed on subsequent accesses - } - } - def get(k: K) = listmap.get(k) - def cachedSize(ct: AnyRef): Int = listmap.size - def string(lev: Int) = (" " * lev) + "LNode(%s)".format(listmap.mkString(", ")) -} - - -private[collection] final class CNode[K, V](final val bitmap: Int, final val array: Array[BasicNode], final val gen: Gen) -extends CNodeBase[K, V] { - - // this should only be called from within read-only snapshots - final def cachedSize(ct: AnyRef) = { - val currsz = READ_SIZE() - if (currsz != -1) currsz - else { - val sz = computeSize(ct.asInstanceOf[ConcurrentTrieMap[K, V]]) - while (READ_SIZE() == -1) CAS_SIZE(-1, sz) - READ_SIZE() - } - } - - // lends itself towards being parallelizable by choosing - // a random starting offset in the array - // => if there are concurrent size computations, they start - // at different positions, so they are more likely to - // to be independent - private def computeSize(ct: ConcurrentTrieMap[K, V]): Int = { - var i = 0 - var sz = 0 - val offset = math.abs(util.Random.nextInt()) % array.length - while (i < array.length) { - val pos = (i + offset) % array.length - array(pos) match { - case sn: SNode[_, _] => sz += 1 - case in: INode[K, V] => sz += in.cachedSize(ct) - } - i += 1 - } - sz - } - - final def updatedAt(pos: Int, nn: BasicNode, gen: Gen) = { - val len = array.length - val narr = new Array[BasicNode](len) - Array.copy(array, 0, narr, 0, len) - narr(pos) = nn - new CNode[K, V](bitmap, narr, gen) - } - - final def removedAt(pos: Int, flag: Int, gen: Gen) = { - val arr = array - val len = arr.length - val narr = new Array[BasicNode](len - 1) - Array.copy(arr, 0, narr, 0, pos) - Array.copy(arr, pos + 1, narr, pos, len - pos - 1) - new CNode[K, V](bitmap ^ flag, narr, gen) - } - - final def insertedAt(pos: Int, flag: Int, nn: BasicNode, gen: Gen) = { - val len = array.length - val bmp = bitmap - val narr = new Array[BasicNode](len + 1) - Array.copy(array, 0, narr, 0, pos) - narr(pos) = nn - Array.copy(array, pos, narr, pos + 1, len - pos) - new CNode[K, V](bmp | flag, narr, gen) - } - - /** Returns a copy of this cnode such that all the i-nodes below it are copied - * to the specified generation `ngen`. - */ - final def renewed(ngen: Gen, ct: ConcurrentTrieMap[K, V]) = { - var i = 0 - val arr = array - val len = arr.length - val narr = new Array[BasicNode](len) - while (i < len) { - arr(i) match { - case in: INode[K, V] => narr(i) = in.copyToGen(ngen, ct) - case bn: BasicNode => narr(i) = bn - } - i += 1 - } - new CNode[K, V](bitmap, narr, ngen) - } - - private def resurrect(inode: INode[K, V], inodemain: AnyRef): BasicNode = inodemain match { - case tn: TNode[_, _] => tn.copyUntombed - case _ => inode - } - - final def toContracted(lev: Int): MainNode[K, V] = if (array.length == 1 && lev > 0) array(0) match { - case sn: SNode[K, V] => sn.copyTombed - case _ => this - } else this - - // - if the branching factor is 1 for this CNode, and the child - // is a tombed SNode, returns its tombed version - // - otherwise, if there is at least one non-null node below, - // returns the version of this node with at least some null-inodes - // removed (those existing when the op began) - // - if there are only null-i-nodes below, returns null - final def toCompressed(ct: ConcurrentTrieMap[K, V], lev: Int, gen: Gen) = { - var bmp = bitmap - var i = 0 - val arr = array - val tmparray = new Array[BasicNode](arr.length) - while (i < arr.length) { // construct new bitmap - val sub = arr(i) - sub match { - case in: INode[K, V] => - val inodemain = in.gcasRead(ct) - assert(inodemain ne null) - tmparray(i) = resurrect(in, inodemain) - case sn: SNode[K, V] => - tmparray(i) = sn - } - i += 1 - } - - new CNode[K, V](bmp, tmparray, gen).toContracted(lev) - } - - private[mutable] def string(lev: Int): String = "CNode %x\n%s".format(bitmap, array.map(_.string(lev + 1)).mkString("\n")) - - /* quiescently consistent - don't call concurrently to anything involving a GCAS!! */ - protected def collectElems: Seq[(K, V)] = array flatMap { - case sn: SNode[K, V] => Some(sn.kvPair) - case in: INode[K, V] => in.mainnode match { - case tn: TNode[K, V] => Some(tn.kvPair) - case ln: LNode[K, V] => ln.listmap.toList - case cn: CNode[K, V] => cn.collectElems - } - } - - protected def collectLocalElems: Seq[String] = array flatMap { - case sn: SNode[K, V] => Some(sn.kvPair._2.toString) - case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen + ")") - } - - override def toString = { - val elems = collectLocalElems - "CNode(sz: %d; %s)".format(elems.size, elems.sorted.mkString(", ")) - } -} - - -private[mutable] object CNode { - - def dual[K, V](x: SNode[K, V], xhc: Int, y: SNode[K, V], yhc: Int, lev: Int, gen: Gen): MainNode[K, V] = if (lev < 35) { - val xidx = (xhc >>> lev) & 0x1f - val yidx = (yhc >>> lev) & 0x1f - val bmp = (1 << xidx) | (1 << yidx) - if (xidx == yidx) { - val subinode = new INode[K, V](gen)//(ConcurrentTrieMap.inodeupdater) - subinode.mainnode = dual(x, xhc, y, yhc, lev + 5, gen) - new CNode(bmp, Array(subinode), gen) - } else { - if (xidx < yidx) new CNode(bmp, Array(x, y), gen) - else new CNode(bmp, Array(y, x), gen) - } - } else { - new LNode(x.k, x.v, y.k, y.v) - } - -} - - -private[mutable] case class RDCSS_Descriptor[K, V](old: INode[K, V], expectedmain: MainNode[K, V], nv: INode[K, V]) { - @volatile var committed = false -} - - -/** A concurrent hash-trie or ConcurrentTrieMap is a concurrent thread-safe lock-free - * implementation of a hash array mapped trie. It is used to implement the - * concurrent map abstraction. It has particularly scalable concurrent insert - * and remove operations and is memory-efficient. It supports O(1), atomic, - * lock-free snapshots which are used to implement linearizable lock-free size, - * iterator and clear operations. The cost of evaluating the (lazy) snapshot is - * distributed across subsequent updates, thus making snapshot evaluation horizontally scalable. - * - * For details, see: http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf - * - * @author Aleksandar Prokopec - * @since 2.10 - */ -@SerialVersionUID(0L - 6402774413839597105L) -final class ConcurrentTrieMap[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[ConcurrentTrieMap[K, V], AnyRef]) -extends ConcurrentMap[K, V] - with MapLike[K, V, ConcurrentTrieMap[K, V]] - with CustomParallelizable[(K, V), ParConcurrentTrieMap[K, V]] - with Serializable -{ - import ConcurrentTrieMap.computeHash - - private var rootupdater = rtupd - @volatile var root = r - - def this() = this( - INode.newRootNode, - AtomicReferenceFieldUpdater.newUpdater(classOf[ConcurrentTrieMap[K, V]], classOf[AnyRef], "root") - ) - - /* internal methods */ - - private def writeObject(out: java.io.ObjectOutputStream) { - val it = iterator - while (it.hasNext) { - val (k, v) = it.next() - out.writeObject(k) - out.writeObject(v) - } - out.writeObject(ConcurrentTrieMapSerializationEnd) - } - - private def readObject(in: java.io.ObjectInputStream) { - root = INode.newRootNode - rootupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[ConcurrentTrieMap[K, V]], classOf[AnyRef], "root") - - var obj: AnyRef = null - do { - obj = in.readObject() - if (obj != ConcurrentTrieMapSerializationEnd) { - val k = obj.asInstanceOf[K] - val v = in.readObject().asInstanceOf[V] - update(k, v) - } - } while (obj != ConcurrentTrieMapSerializationEnd) - } - - @inline final def CAS_ROOT(ov: AnyRef, nv: AnyRef) = rootupdater.compareAndSet(this, ov, nv) - - final def readRoot(abort: Boolean = false): INode[K, V] = RDCSS_READ_ROOT(abort) - - @inline final def RDCSS_READ_ROOT(abort: Boolean = false): INode[K, V] = { - val r = /*READ*/root - r match { - case in: INode[K, V] => in - case desc: RDCSS_Descriptor[K, V] => RDCSS_Complete(abort) - } - } - - @tailrec private def RDCSS_Complete(abort: Boolean): INode[K, V] = { - val v = /*READ*/root - v match { - case in: INode[K, V] => in - case desc: RDCSS_Descriptor[K, V] => - val RDCSS_Descriptor(ov, exp, nv) = desc - if (abort) { - if (CAS_ROOT(desc, ov)) ov - else RDCSS_Complete(abort) - } else { - val oldmain = ov.gcasRead(this) - if (oldmain eq exp) { - if (CAS_ROOT(desc, nv)) { - desc.committed = true - nv - } else RDCSS_Complete(abort) - } else { - if (CAS_ROOT(desc, ov)) ov - else RDCSS_Complete(abort) - } - } - } - } - - private def RDCSS_ROOT(ov: INode[K, V], expectedmain: MainNode[K, V], nv: INode[K, V]): Boolean = { - val desc = RDCSS_Descriptor(ov, expectedmain, nv) - if (CAS_ROOT(ov, desc)) { - RDCSS_Complete(false) - /*READ*/desc.committed - } else false - } - - @tailrec private def inserthc(k: K, hc: Int, v: V) { - val r = RDCSS_READ_ROOT() - if (!r.rec_insert(k, v, hc, 0, null, r.gen, this)) inserthc(k, hc, v) - } - - @tailrec private def insertifhc(k: K, hc: Int, v: V, cond: AnyRef): Option[V] = { - val r = RDCSS_READ_ROOT() - - val ret = r.rec_insertif(k, v, hc, cond, 0, null, r.gen, this) - if (ret eq null) insertifhc(k, hc, v, cond) - else ret - } - - @tailrec private def lookuphc(k: K, hc: Int): AnyRef = { - val r = RDCSS_READ_ROOT() - val res = r.rec_lookup(k, hc, 0, null, r.gen, this) - if (res eq INodeBase.RESTART) lookuphc(k, hc) - else res - } - - /* slower: - //@tailrec - private def lookuphc(k: K, hc: Int): AnyRef = { - val r = RDCSS_READ_ROOT() - try { - r.rec_lookup(k, hc, 0, null, r.gen, this) - } catch { - case RestartException => - lookuphc(k, hc) - } - } - */ - - @tailrec private def removehc(k: K, v: V, hc: Int): Option[V] = { - val r = RDCSS_READ_ROOT() - val res = r.rec_remove(k, v, hc, 0, null, r.gen, this) - if (res ne null) res - else removehc(k, v, hc) - } - - def string = RDCSS_READ_ROOT().string(0) - - /* public methods */ - - override def seq = this - - override def par = new ParConcurrentTrieMap(this) - - override def empty: ConcurrentTrieMap[K, V] = new ConcurrentTrieMap[K, V] - - final def isReadOnly = rootupdater eq null - - final def nonReadOnly = rootupdater ne null - - /** Returns a snapshot of this ConcurrentTrieMap. - * This operation is lock-free and linearizable. - * - * The snapshot is lazily updated - the first time some branch - * in the snapshot or this ConcurrentTrieMap are accessed, they are rewritten. - * This means that the work of rebuilding both the snapshot and this - * ConcurrentTrieMap is distributed across all the threads doing updates or accesses - * subsequent to the snapshot creation. - */ - @tailrec final def snapshot(): ConcurrentTrieMap[K, V] = { - val r = RDCSS_READ_ROOT() - val expmain = r.gcasRead(this) - if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new ConcurrentTrieMap(r.copyToGen(new Gen, this), rootupdater) - else snapshot() - } - - /** Returns a read-only snapshot of this ConcurrentTrieMap. - * This operation is lock-free and linearizable. - * - * The snapshot is lazily updated - the first time some branch - * of this ConcurrentTrieMap are accessed, it is rewritten. The work of creating - * the snapshot is thus distributed across subsequent updates - * and accesses on this ConcurrentTrieMap by all threads. - * Note that the snapshot itself is never rewritten unlike when calling - * the `snapshot` method, but the obtained snapshot cannot be modified. - * - * This method is used by other methods such as `size` and `iterator`. - */ - @tailrec final def readOnlySnapshot(): collection.Map[K, V] = { - val r = RDCSS_READ_ROOT() - val expmain = r.gcasRead(this) - if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new ConcurrentTrieMap(r, null) - else readOnlySnapshot() - } - - @tailrec final override def clear() { - val r = RDCSS_READ_ROOT() - if (!RDCSS_ROOT(r, r.gcasRead(this), INode.newRootNode[K, V])) clear() - } - - final def lookup(k: K): V = { - val hc = computeHash(k) - lookuphc(k, hc).asInstanceOf[V] - } - - final override def apply(k: K): V = { - val hc = computeHash(k) - val res = lookuphc(k, hc) - if (res eq null) throw new NoSuchElementException - else res.asInstanceOf[V] - } - - final def get(k: K): Option[V] = { - val hc = computeHash(k) - Option(lookuphc(k, hc)).asInstanceOf[Option[V]] - } - - override def put(key: K, value: V): Option[V] = { - val hc = computeHash(key) - insertifhc(key, hc, value, null) - } - - final override def update(k: K, v: V) { - val hc = computeHash(k) - inserthc(k, hc, v) - } - - final def +=(kv: (K, V)) = { - update(kv._1, kv._2) - this - } - - final override def remove(k: K): Option[V] = { - val hc = computeHash(k) - removehc(k, null.asInstanceOf[V], hc) - } - - final def -=(k: K) = { - remove(k) - this - } - - def putIfAbsent(k: K, v: V): Option[V] = { - val hc = computeHash(k) - insertifhc(k, hc, v, INode.KEY_ABSENT) - } - - def remove(k: K, v: V): Boolean = { - val hc = computeHash(k) - removehc(k, v, hc).nonEmpty - } - - def replace(k: K, oldvalue: V, newvalue: V): Boolean = { - val hc = computeHash(k) - insertifhc(k, hc, newvalue, oldvalue.asInstanceOf[AnyRef]).nonEmpty - } - - def replace(k: K, v: V): Option[V] = { - val hc = computeHash(k) - insertifhc(k, hc, v, INode.KEY_PRESENT) - } - - def iterator: Iterator[(K, V)] = - if (nonReadOnly) readOnlySnapshot().iterator - else new ConcurrentTrieMapIterator(0, this) - - private def cachedSize() = { - val r = RDCSS_READ_ROOT() - r.cachedSize(this) - } - - override def size: Int = - if (nonReadOnly) readOnlySnapshot().size - else cachedSize() - - override def stringPrefix = "ConcurrentTrieMap" - -} - - -object ConcurrentTrieMap extends MutableMapFactory[ConcurrentTrieMap] { - val inodeupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[INodeBase[_, _]], classOf[MainNode[_, _]], "mainnode") - - implicit def canBuildFrom[K, V]: CanBuildFrom[Coll, (K, V), ConcurrentTrieMap[K, V]] = new MapCanBuildFrom[K, V] - - def empty[K, V]: ConcurrentTrieMap[K, V] = new ConcurrentTrieMap[K, V] - - @inline final def computeHash[K](k: K): Int = { - var hcode = k.hashCode - hcode = hcode * 0x9e3775cd - hcode = java.lang.Integer.reverseBytes(hcode) - hcode * 0x9e3775cd - } - -} - - -private[collection] class ConcurrentTrieMapIterator[K, V](var level: Int, private var ct: ConcurrentTrieMap[K, V], mustInit: Boolean = true) extends Iterator[(K, V)] { - var stack = new Array[Array[BasicNode]](7) - var stackpos = new Array[Int](7) - var depth = -1 - var subiter: Iterator[(K, V)] = null - var current: KVNode[K, V] = null - - if (mustInit) initialize() - - def hasNext = (current ne null) || (subiter ne null) - - def next() = if (hasNext) { - var r: (K, V) = null - if (subiter ne null) { - r = subiter.next() - checkSubiter() - } else { - r = current.kvPair - advance() - } - r - } else Iterator.empty.next() - - private def readin(in: INode[K, V]) = in.gcasRead(ct) match { - case cn: CNode[K, V] => - depth += 1 - stack(depth) = cn.array - stackpos(depth) = -1 - advance() - case tn: TNode[K, V] => - current = tn - case ln: LNode[K, V] => - subiter = ln.listmap.iterator - checkSubiter() - case null => - current = null - } - - @inline private def checkSubiter() = if (!subiter.hasNext) { - subiter = null - advance() - } - - @inline private def initialize() { - assert(ct.isReadOnly) - - val r = ct.RDCSS_READ_ROOT() - readin(r) - } - - def advance(): Unit = if (depth >= 0) { - val npos = stackpos(depth) + 1 - if (npos < stack(depth).length) { - stackpos(depth) = npos - stack(depth)(npos) match { - case sn: SNode[K, V] => - current = sn - case in: INode[K, V] => - readin(in) - } - } else { - depth -= 1 - advance() - } - } else current = null - - protected def newIterator(_lev: Int, _ct: ConcurrentTrieMap[K, V], _mustInit: Boolean) = new ConcurrentTrieMapIterator[K, V](_lev, _ct, _mustInit) - - protected def dupTo(it: ConcurrentTrieMapIterator[K, V]) = { - it.level = this.level - it.ct = this.ct - it.depth = this.depth - it.current = this.current - - // these need a deep copy - Array.copy(this.stack, 0, it.stack, 0, 7) - Array.copy(this.stackpos, 0, it.stackpos, 0, 7) - - // this one needs to be evaluated - if (this.subiter == null) it.subiter = null - else { - val lst = this.subiter.toList - this.subiter = lst.iterator - it.subiter = lst.iterator - } - } - - /** Returns a sequence of iterators over subsets of this iterator. - * It's used to ease the implementation of splitters for a parallel version of the ConcurrentTrieMap. - */ - protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne null) { - // the case where an LNode is being iterated - val it = subiter - subiter = null - advance() - this.level += 1 - Seq(it, this) - } else if (depth == -1) { - this.level += 1 - Seq(this) - } else { - var d = 0 - while (d <= depth) { - val rem = stack(d).length - 1 - stackpos(d) - if (rem > 0) { - val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2) - stack(d) = arr1 - stackpos(d) = -1 - val it = newIterator(level + 1, ct, false) - it.stack(0) = arr2 - it.stackpos(0) = -1 - it.depth = 0 - it.advance() // <-- fix it - this.level += 1 - return Seq(this, it) - } - d += 1 - } - this.level += 1 - Seq(this) - } - - def printDebug { - println("ctrie iterator") - println(stackpos.mkString(",")) - println("depth: " + depth) - println("curr.: " + current) - println(stack.mkString("\n")) - } - -} - - -private[mutable] object RestartException extends util.control.ControlThrowable - - -/** Only used for ctrie serialization. */ -@SerialVersionUID(0L - 7237891413820527142L) -private[mutable] case object ConcurrentTrieMapSerializationEnd - - -private[mutable] object Debug { - import collection._ - - lazy val logbuffer = new java.util.concurrent.ConcurrentLinkedQueue[AnyRef] - - def log(s: AnyRef) = logbuffer.add(s) - - def flush() { - for (s <- JavaConversions.asScalaIterator(logbuffer.iterator())) Console.out.println(s.toString) - logbuffer.clear() - } - - def clear() { - logbuffer.clear() - } - -} - - - - - - - - - - diff --git a/src/library/scala/collection/parallel/mutable/ParConcurrentTrieMap.scala b/src/library/scala/collection/parallel/mutable/ParConcurrentTrieMap.scala new file mode 100644 index 0000000000..a6495161ea --- /dev/null +++ b/src/library/scala/collection/parallel/mutable/ParConcurrentTrieMap.scala @@ -0,0 +1,193 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2012, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection.parallel.mutable + + + +import scala.collection.generic._ +import scala.collection.parallel.Combiner +import scala.collection.parallel.IterableSplitter +import scala.collection.parallel.Task +import scala.collection.mutable.BasicNode +import scala.collection.mutable.TNode +import scala.collection.mutable.LNode +import scala.collection.mutable.CNode +import scala.collection.mutable.SNode +import scala.collection.mutable.INode +import scala.collection.mutable.ConcurrentTrieMap +import scala.collection.mutable.ConcurrentTrieMapIterator + + + +/** Parallel ConcurrentTrieMap collection. + * + * It has its bulk operations parallelized, but uses the snapshot operation + * to create the splitter. This means that parallel bulk operations can be + * called concurrently with the modifications. + * + * @author Aleksandar Prokopec + * @since 2.10 + */ +final class ParConcurrentTrieMap[K, V] private[collection] (private val ctrie: ConcurrentTrieMap[K, V]) +extends ParMap[K, V] + with GenericParMapTemplate[K, V, ParConcurrentTrieMap] + with ParMapLike[K, V, ParConcurrentTrieMap[K, V], ConcurrentTrieMap[K, V]] + with ParConcurrentTrieMapCombiner[K, V] + with Serializable +{ + def this() = this(new ConcurrentTrieMap) + + override def mapCompanion: GenericParMapCompanion[ParConcurrentTrieMap] = ParConcurrentTrieMap + + override def empty: ParConcurrentTrieMap[K, V] = ParConcurrentTrieMap.empty + + protected[this] override def newCombiner = ParConcurrentTrieMap.newCombiner + + override def seq = ctrie + + def splitter = new ParConcurrentTrieMapSplitter(0, ctrie.readOnlySnapshot().asInstanceOf[ConcurrentTrieMap[K, V]], true) + + override def clear() = ctrie.clear() + + def result = this + + def get(key: K): Option[V] = ctrie.get(key) + + def put(key: K, value: V): Option[V] = ctrie.put(key, value) + + def update(key: K, value: V): Unit = ctrie.update(key, value) + + def remove(key: K): Option[V] = ctrie.remove(key) + + def +=(kv: (K, V)): this.type = { + ctrie.+=(kv) + this + } + + def -=(key: K): this.type = { + ctrie.-=(key) + this + } + + override def size = { + val in = ctrie.readRoot() + val r = in.gcasRead(ctrie) + r match { + case tn: TNode[_, _] => tn.cachedSize(ctrie) + case ln: LNode[_, _] => ln.cachedSize(ctrie) + case cn: CNode[_, _] => + tasksupport.executeAndWaitResult(new Size(0, cn.array.length, cn.array)) + cn.cachedSize(ctrie) + } + } + + override def stringPrefix = "ParConcurrentTrieMap" + + /* tasks */ + + /** Computes ConcurrentTrieMap size in parallel. */ + class Size(offset: Int, howmany: Int, array: Array[BasicNode]) extends Task[Int, Size] { + var result = -1 + def leaf(prev: Option[Int]) = { + var sz = 0 + var i = offset + val until = offset + howmany + while (i < until) { + array(i) match { + case sn: SNode[_, _] => sz += 1 + case in: INode[K, V] => sz += in.cachedSize(ctrie) + } + i += 1 + } + result = sz + } + def split = { + val fp = howmany / 2 + Seq(new Size(offset, fp, array), new Size(offset + fp, howmany - fp, array)) + } + def shouldSplitFurther = howmany > 1 + override def merge(that: Size) = result = result + that.result + } + +} + + +private[collection] class ParConcurrentTrieMapSplitter[K, V](lev: Int, ct: ConcurrentTrieMap[K, V], mustInit: Boolean) +extends ConcurrentTrieMapIterator[K, V](lev, ct, mustInit) + with IterableSplitter[(K, V)] +{ + // only evaluated if `remaining` is invoked (which is not used by most tasks) + lazy val totalsize = ct.par.size + var iterated = 0 + + protected override def newIterator(_lev: Int, _ct: ConcurrentTrieMap[K, V], _mustInit: Boolean) = new ParConcurrentTrieMapSplitter[K, V](_lev, _ct, _mustInit) + + override def shouldSplitFurther[S](coll: collection.parallel.ParIterable[S], parallelismLevel: Int) = { + val maxsplits = 3 + Integer.highestOneBit(parallelismLevel) + level < maxsplits + } + + def dup = { + val it = newIterator(0, ct, false) + dupTo(it) + it.iterated = this.iterated + it + } + + override def next() = { + iterated += 1 + super.next() + } + + def split: Seq[IterableSplitter[(K, V)]] = subdivide().asInstanceOf[Seq[IterableSplitter[(K, V)]]] + + override def isRemainingCheap = false + + def remaining: Int = totalsize - iterated +} + + +/** Only used within the `ParConcurrentTrieMap`. */ +private[mutable] trait ParConcurrentTrieMapCombiner[K, V] extends Combiner[(K, V), ParConcurrentTrieMap[K, V]] { + + def combine[N <: (K, V), NewTo >: ParConcurrentTrieMap[K, V]](other: Combiner[N, NewTo]): Combiner[N, NewTo] = if (this eq other) this else { + throw new UnsupportedOperationException("This shouldn't have been called in the first place.") + + val thiz = this.asInstanceOf[ParConcurrentTrieMap[K, V]] + val that = other.asInstanceOf[ParConcurrentTrieMap[K, V]] + val result = new ParConcurrentTrieMap[K, V] + + result ++= thiz.iterator + result ++= that.iterator + + result + } + + override def canBeShared = true + +} + + +object ParConcurrentTrieMap extends ParMapFactory[ParConcurrentTrieMap] { + + def empty[K, V]: ParConcurrentTrieMap[K, V] = new ParConcurrentTrieMap[K, V] + + def newCombiner[K, V]: Combiner[(K, V), ParConcurrentTrieMap[K, V]] = new ParConcurrentTrieMap[K, V] + + implicit def canBuildFrom[K, V]: CanCombineFrom[Coll, (K, V), ParConcurrentTrieMap[K, V]] = new CanCombineFromMap[K, V] + +} + + + + + + + + diff --git a/src/library/scala/collection/parallel/mutable/ParCtrie.scala b/src/library/scala/collection/parallel/mutable/ParCtrie.scala deleted file mode 100644 index a6495161ea..0000000000 --- a/src/library/scala/collection/parallel/mutable/ParCtrie.scala +++ /dev/null @@ -1,193 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2012, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -package scala.collection.parallel.mutable - - - -import scala.collection.generic._ -import scala.collection.parallel.Combiner -import scala.collection.parallel.IterableSplitter -import scala.collection.parallel.Task -import scala.collection.mutable.BasicNode -import scala.collection.mutable.TNode -import scala.collection.mutable.LNode -import scala.collection.mutable.CNode -import scala.collection.mutable.SNode -import scala.collection.mutable.INode -import scala.collection.mutable.ConcurrentTrieMap -import scala.collection.mutable.ConcurrentTrieMapIterator - - - -/** Parallel ConcurrentTrieMap collection. - * - * It has its bulk operations parallelized, but uses the snapshot operation - * to create the splitter. This means that parallel bulk operations can be - * called concurrently with the modifications. - * - * @author Aleksandar Prokopec - * @since 2.10 - */ -final class ParConcurrentTrieMap[K, V] private[collection] (private val ctrie: ConcurrentTrieMap[K, V]) -extends ParMap[K, V] - with GenericParMapTemplate[K, V, ParConcurrentTrieMap] - with ParMapLike[K, V, ParConcurrentTrieMap[K, V], ConcurrentTrieMap[K, V]] - with ParConcurrentTrieMapCombiner[K, V] - with Serializable -{ - def this() = this(new ConcurrentTrieMap) - - override def mapCompanion: GenericParMapCompanion[ParConcurrentTrieMap] = ParConcurrentTrieMap - - override def empty: ParConcurrentTrieMap[K, V] = ParConcurrentTrieMap.empty - - protected[this] override def newCombiner = ParConcurrentTrieMap.newCombiner - - override def seq = ctrie - - def splitter = new ParConcurrentTrieMapSplitter(0, ctrie.readOnlySnapshot().asInstanceOf[ConcurrentTrieMap[K, V]], true) - - override def clear() = ctrie.clear() - - def result = this - - def get(key: K): Option[V] = ctrie.get(key) - - def put(key: K, value: V): Option[V] = ctrie.put(key, value) - - def update(key: K, value: V): Unit = ctrie.update(key, value) - - def remove(key: K): Option[V] = ctrie.remove(key) - - def +=(kv: (K, V)): this.type = { - ctrie.+=(kv) - this - } - - def -=(key: K): this.type = { - ctrie.-=(key) - this - } - - override def size = { - val in = ctrie.readRoot() - val r = in.gcasRead(ctrie) - r match { - case tn: TNode[_, _] => tn.cachedSize(ctrie) - case ln: LNode[_, _] => ln.cachedSize(ctrie) - case cn: CNode[_, _] => - tasksupport.executeAndWaitResult(new Size(0, cn.array.length, cn.array)) - cn.cachedSize(ctrie) - } - } - - override def stringPrefix = "ParConcurrentTrieMap" - - /* tasks */ - - /** Computes ConcurrentTrieMap size in parallel. */ - class Size(offset: Int, howmany: Int, array: Array[BasicNode]) extends Task[Int, Size] { - var result = -1 - def leaf(prev: Option[Int]) = { - var sz = 0 - var i = offset - val until = offset + howmany - while (i < until) { - array(i) match { - case sn: SNode[_, _] => sz += 1 - case in: INode[K, V] => sz += in.cachedSize(ctrie) - } - i += 1 - } - result = sz - } - def split = { - val fp = howmany / 2 - Seq(new Size(offset, fp, array), new Size(offset + fp, howmany - fp, array)) - } - def shouldSplitFurther = howmany > 1 - override def merge(that: Size) = result = result + that.result - } - -} - - -private[collection] class ParConcurrentTrieMapSplitter[K, V](lev: Int, ct: ConcurrentTrieMap[K, V], mustInit: Boolean) -extends ConcurrentTrieMapIterator[K, V](lev, ct, mustInit) - with IterableSplitter[(K, V)] -{ - // only evaluated if `remaining` is invoked (which is not used by most tasks) - lazy val totalsize = ct.par.size - var iterated = 0 - - protected override def newIterator(_lev: Int, _ct: ConcurrentTrieMap[K, V], _mustInit: Boolean) = new ParConcurrentTrieMapSplitter[K, V](_lev, _ct, _mustInit) - - override def shouldSplitFurther[S](coll: collection.parallel.ParIterable[S], parallelismLevel: Int) = { - val maxsplits = 3 + Integer.highestOneBit(parallelismLevel) - level < maxsplits - } - - def dup = { - val it = newIterator(0, ct, false) - dupTo(it) - it.iterated = this.iterated - it - } - - override def next() = { - iterated += 1 - super.next() - } - - def split: Seq[IterableSplitter[(K, V)]] = subdivide().asInstanceOf[Seq[IterableSplitter[(K, V)]]] - - override def isRemainingCheap = false - - def remaining: Int = totalsize - iterated -} - - -/** Only used within the `ParConcurrentTrieMap`. */ -private[mutable] trait ParConcurrentTrieMapCombiner[K, V] extends Combiner[(K, V), ParConcurrentTrieMap[K, V]] { - - def combine[N <: (K, V), NewTo >: ParConcurrentTrieMap[K, V]](other: Combiner[N, NewTo]): Combiner[N, NewTo] = if (this eq other) this else { - throw new UnsupportedOperationException("This shouldn't have been called in the first place.") - - val thiz = this.asInstanceOf[ParConcurrentTrieMap[K, V]] - val that = other.asInstanceOf[ParConcurrentTrieMap[K, V]] - val result = new ParConcurrentTrieMap[K, V] - - result ++= thiz.iterator - result ++= that.iterator - - result - } - - override def canBeShared = true - -} - - -object ParConcurrentTrieMap extends ParMapFactory[ParConcurrentTrieMap] { - - def empty[K, V]: ParConcurrentTrieMap[K, V] = new ParConcurrentTrieMap[K, V] - - def newCombiner[K, V]: Combiner[(K, V), ParConcurrentTrieMap[K, V]] = new ParConcurrentTrieMap[K, V] - - implicit def canBuildFrom[K, V]: CanCombineFrom[Coll, (K, V), ParConcurrentTrieMap[K, V]] = new CanCombineFromMap[K, V] - -} - - - - - - - - -- cgit v1.2.3 From 479aee3617e952d8705b95ef2ea3a155914dd03c Mon Sep 17 00:00:00 2001 From: Josh Suereth Date: Wed, 14 Mar 2012 09:35:42 -0400 Subject: properties loading is now maven/osgi version aware. yippie. --- src/library/scala/util/Properties.scala | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/util/Properties.scala b/src/library/scala/util/Properties.scala index 0c7772cd07..3ba803712d 100644 --- a/src/library/scala/util/Properties.scala +++ b/src/library/scala/util/Properties.scala @@ -72,10 +72,11 @@ private[scala] trait PropertiesTrait { * it is an RC, Beta, etc. or was built from source, or if the version * cannot be read. */ - val releaseVersion = scalaPropOrNone("version.number") flatMap { s => - val segments = s split '.' - if (segments.size == 4 && segments.last == "final") Some(segments take 3 mkString ".") else None - } + val releaseVersion = + for { + v <- scalaPropOrNone("maven.version.number") + if !(v endsWith "-SNAPSHOT") + } yield v /** The development Scala version, if this is not a final release. * The precise contents are not guaranteed, but it aims to provide a @@ -85,15 +86,12 @@ private[scala] trait PropertiesTrait { * @return Some(version) if this is a non-final version, None if this * is a final release or the version cannot be read. */ - val developmentVersion = scalaPropOrNone("version.number") flatMap { s => - val segments = s split '.' - if (segments.isEmpty || segments.last == "final") - None - else if (segments.last startsWith "r") - Some(s takeWhile (ch => ch != '-')) // Cutting e.g. 2.10.0.r24774-b20110417125606 to 2.10.0.r24774 - else - Some(s) - } + val developmentVersion = + for { + v <- scalaPropOrNone("maven.version.number") + if v endsWith "-SNAPSHOT" + ov <- scalaPropOrNone("version.number") + } yield ov /** Either the development or release version if known, otherwise * the empty string. @@ -103,7 +101,8 @@ private[scala] trait PropertiesTrait { /** The version number of the jar this was loaded from plus "version " prefix, * or "version (unknown)" if it cannot be determined. */ - val versionString = "version " + scalaPropOrElse("version.number", "(unknown)") + val versionString = "version " + scalaPropOrElse("version.number", "(unknown)") + + scalaPropOrNone("maven.version.number").map(v => "(" + v + ")").getOrElse("") val copyrightString = scalaPropOrElse("copyright.string", "(c) 2002-2011 LAMP/EPFL") /** This is the encoding to use reading in source files, overridden with -encoding -- cgit v1.2.3 From 1d8037bbf56b303d69cd3e8faafc05fc5fc5db3e Mon Sep 17 00:00:00 2001 From: Josh Suereth Date: Fri, 16 Mar 2012 01:05:31 -0400 Subject: Finished migrating to new versioning scheme Conflicts: build.xml tools/get-scala-revision.bat --- build.xml | 43 +++++++++++++++++++++++--------- src/library/scala/util/Properties.scala | 3 +-- tools/get-scala-commit-date | 16 ++++++++++++ tools/get-scala-commit-date.bat | 24 ++++++++++++++++++ tools/get-scala-commit-drift | 40 ++++++++++++++++++++++++++++++ tools/get-scala-commit-drift.bat | 21 ++++++++++++++++ tools/get-scala-commit-sha | 39 +++++++++++++++++++++++++++++ tools/get-scala-commit-sha.bat | 21 ++++++++++++++++ tools/get-scala-revision | 44 --------------------------------- tools/get-scala-revision.bat | 27 -------------------- 10 files changed, 193 insertions(+), 85 deletions(-) create mode 100755 tools/get-scala-commit-date create mode 100644 tools/get-scala-commit-date.bat create mode 100755 tools/get-scala-commit-drift create mode 100644 tools/get-scala-commit-drift.bat create mode 100755 tools/get-scala-commit-sha create mode 100644 tools/get-scala-commit-sha.bat delete mode 100755 tools/get-scala-revision delete mode 100644 tools/get-scala-revision.bat (limited to 'src/library') diff --git a/build.xml b/build.xml index 1b92893b5d..7d05f02e2e 100644 --- a/build.xml +++ b/build.xml @@ -245,21 +245,21 @@ INITIALISATION - - - + + + + - - - + + - + @@ -280,6 +280,15 @@ INITIALISATION + + + + + + + + + @@ -289,13 +298,16 @@ INITIALISATION + - + value="${maven.version.number}-${git.commit.date}-${git.commit.drift}-${git.commit.sha}"/> + name="osgi.version.number" + value="${version.major}.${version.minor}.${version.patch}.r${git.commit.date}${version.suffix}-${git.commit.sha}"/> + @@ -334,7 +346,8 @@ INITIALISATION - + + @@ -402,6 +415,7 @@ LOCAL REFERENCE BUILD (LOCKER) + @@ -442,6 +456,7 @@ LOCAL REFERENCE BUILD (LOCKER) + @@ -674,6 +689,7 @@ QUICK BUILD (QUICK) + @@ -734,6 +750,7 @@ QUICK BUILD (QUICK) + @@ -1217,6 +1234,7 @@ BOOTSTRAPPING BUILD (STRAP) + @@ -1257,6 +1275,7 @@ BOOTSTRAPPING BUILD (STRAP) + diff --git a/src/library/scala/util/Properties.scala b/src/library/scala/util/Properties.scala index 3ba803712d..38ca89b98b 100644 --- a/src/library/scala/util/Properties.scala +++ b/src/library/scala/util/Properties.scala @@ -101,8 +101,7 @@ private[scala] trait PropertiesTrait { /** The version number of the jar this was loaded from plus "version " prefix, * or "version (unknown)" if it cannot be determined. */ - val versionString = "version " + scalaPropOrElse("version.number", "(unknown)") + - scalaPropOrNone("maven.version.number").map(v => "(" + v + ")").getOrElse("") + val versionString = "version " + scalaPropOrElse("version.number", "(unknown)") val copyrightString = scalaPropOrElse("copyright.string", "(c) 2002-2011 LAMP/EPFL") /** This is the encoding to use reading in source files, overridden with -encoding diff --git a/tools/get-scala-commit-date b/tools/get-scala-commit-date new file mode 100755 index 0000000000..ef5b0f540d --- /dev/null +++ b/tools/get-scala-commit-date @@ -0,0 +1,16 @@ +#!/usr/bin/env bash +# +# Usage: get-scala-commit-date [dir] +# Figures out current commit date of a git clone. +# If no dir is given, current working dir is used. +# +# Example build version string: +# 20120312 +# + +[[ $# -eq 0 ]] || cd "$1" + +lastcommitdate=$(git log --format="%ci" HEAD | head -n 1 | cut -d ' ' -f 1) + +# 20120324 +echo "${lastcommitdate//-/}" diff --git a/tools/get-scala-commit-date.bat b/tools/get-scala-commit-date.bat new file mode 100644 index 0000000000..a07155533f --- /dev/null +++ b/tools/get-scala-commit-date.bat @@ -0,0 +1,24 @@ +@echo off +rem +rem Usage: get-scala-revison.bat [dir] +rem Figures out current scala commit date of a git clone. +rem +rem If no dir is given, current working dir is used. + +@setlocal +set _DIR= +if "%*"=="" ( + for /f "delims=;" %%i in ('cd') do set "_DIR=%%i" +) else ( + set "_DIR=%~1" +) +cd %_DIR% + +rem TODO - Check with a real windows user that this works! +if exist .git\NUL ( + for /f "tokens=1delims= " in ('git log --format="%ci" -1') do set commitdate=%%a + echo %commitdate% +) + +:end +@endlocal diff --git a/tools/get-scala-commit-drift b/tools/get-scala-commit-drift new file mode 100755 index 0000000000..4959826ec1 --- /dev/null +++ b/tools/get-scala-commit-drift @@ -0,0 +1,40 @@ +#!/usr/bin/env bash +# +# Usage: get-scala-commit-drift [dir] +# Figures out current commit drift of a git clone. +# If no dir is given, current working dir is used. +# +# Example output string: +# 123 +# +# Build drift = # of commits since last tag. + +[[ $# -eq 0 ]] || cd "$1" + +ensure_tag () { + sha=$1 + rev=$2 + + [[ -n $(git tag -l $rev) ]] || { + git tag -a -m "generated by get-scala-revision" $rev $sha + } +} + +# Ensure some baseline tags are present so if this repository's +# tags are screwed up or stale, we should still have a reference +# point for a build string. +ensure_tag 58cb15c40d v2.10.0-M1 +ensure_tag 29f3eace1e v2.9.1 +ensure_tag b0d78f6b9c v2.8.2 + +# the closest tag, obtained separately because we have to +# reconstruct the string around the padded distance. +tag=$(git describe --tags --match 'v2*' --abbrev=0) + +# printf %016s is not portable for 0-padding, has to be a digit. +# so we're stuck disassembling it. +described=$(git describe --tags --match 'v2*' --abbrev=10) +suffix="${described##${tag}-}" +counter=$(echo $suffix | cut -d - -f 1) + +echo "$counter" diff --git a/tools/get-scala-commit-drift.bat b/tools/get-scala-commit-drift.bat new file mode 100644 index 0000000000..ac289d3481 --- /dev/null +++ b/tools/get-scala-commit-drift.bat @@ -0,0 +1,21 @@ +@echo off +rem +rem Usage: get-scala-commit-drift.bat [dir] +rem Figures out current scala commit drift, of a clone. +rem +rem If no dir is given, current working dir is used. + +@setlocal +set _DIR= +if "%*"=="" ( + for /f "delims=;" %%i in ('cd') do set "_DIR=%%i" +) else ( + set "_DIR=%~1" +) +cd %_DIR% + +rem TODO - WRITE THIS +echo "TODO" + +:end +@endlocal diff --git a/tools/get-scala-commit-sha b/tools/get-scala-commit-sha new file mode 100755 index 0000000000..0aa70d985c --- /dev/null +++ b/tools/get-scala-commit-sha @@ -0,0 +1,39 @@ +#!/usr/bin/env bash +# +# Usage: get-scala-commit-sha [dir] +# Figures out current commit sha of a git clone. +# If no dir is given, current working dir is used. +# +# Example build version string: +# g6f1c486d0b +# + +[[ $# -eq 0 ]] || cd "$1" + +ensure_tag () { + sha=$1 + rev=$2 + + [[ -n $(git tag -l $rev) ]] || { + git tag -a -m "generated by get-scala-revision" $rev $sha + } +} + +# Ensure some baseline tags are present so if this repository's +# tags are screwed up or stale, we should still have a reference +# point for a build string. +ensure_tag 58cb15c40d v2.10.0-M1 +ensure_tag 29f3eace1e v2.9.1 +ensure_tag b0d78f6b9c v2.8.2 + +# the closest tag, obtained separately because we have to +# reconstruct the string around the padded distance. +tag=$(git describe --tags --match 'v2*' --abbrev=0) + +# printf %016s is not portable for 0-padding, has to be a digit. +# so we're stuck disassembling it. +described=$(git describe --tags --match 'v2*' --abbrev=10) +suffix="${described##${tag}-}" +hash=$(echo $suffix | cut -d - -f 2) + +echo "$hash" diff --git a/tools/get-scala-commit-sha.bat b/tools/get-scala-commit-sha.bat new file mode 100644 index 0000000000..80d9aa34b1 --- /dev/null +++ b/tools/get-scala-commit-sha.bat @@ -0,0 +1,21 @@ +@echo off +rem +rem Usage: get-scala-commit-drift.bat [dir] +rem Figures out current scala commit drift, of a clone. +rem +rem If no dir is given, current working dir is used. + +@setlocal +set _DIR= +if "%*"=="" ( + for /f "delims=;" %%i in ('cd') do set "_DIR=%%i" +) else ( + set "_DIR=%~1" +) +cd %_DIR% + +rem TODO - truncate chars. +git log -1 --format="%T" + +:end +@endlocal diff --git a/tools/get-scala-revision b/tools/get-scala-revision deleted file mode 100755 index 14c84d0ad4..0000000000 --- a/tools/get-scala-revision +++ /dev/null @@ -1,44 +0,0 @@ -#!/usr/bin/env bash -# -# Usage: get-scala-revision [dir] -# Figures out current scala revision of a git clone. -# If no dir is given, current working dir is used. -# -# Example build version string: -# v2.10.0-M1-0098-g6f1c486d0b-2012-02-01 -# - -[[ $# -eq 0 ]] || cd "$1" - -ensure_tag () { - sha=$1 - rev=$2 - - [[ -n $(git tag -l $rev) ]] || { - git tag -a -m "generated by get-scala-revision" $rev $sha - } -} - -# Ensure some baseline tags are present so if this repository's -# tags are screwed up or stale, we should still have a reference -# point for a build string. -ensure_tag 58cb15c40d v2.10.0-M1 -ensure_tag 29f3eace1e v2.9.1 -ensure_tag b0d78f6b9c v2.8.2 - -# the closest tag, obtained separately because we have to -# reconstruct the string around the padded distance. -tag=$(git describe --tags --match 'v2*' --abbrev=0) - -# printf %016s is not portable for 0-padding, has to be a digit. -# so we're stuck disassembling it. -described=$(git describe --tags --match 'v2*' --abbrev=10) -suffix="${described##${tag}-}" -counter=$(echo $suffix | cut -d - -f 1) -hash=$(echo $suffix | cut -d - -f 2) - -# remove any alphabetic characters before the version number -tag=$(echo $tag | sed "s/\([a-z_A-Z]*\)\(.*\)/\2/") - -# 20120324-123-b0d78f7b9c -printf "%s-%04d-%s\n" $(date "+%Y%m%d") "$counter" "$hash" diff --git a/tools/get-scala-revision.bat b/tools/get-scala-revision.bat deleted file mode 100644 index b5b30eb3a8..0000000000 --- a/tools/get-scala-revision.bat +++ /dev/null @@ -1,27 +0,0 @@ -@echo off -rem -rem Usage: get-scala-revison.bat [dir] -rem Figures out current scala revision of a git clone. -rem -rem If no dir is given, current working dir is used. - -@setlocal -set _DIR= -if "%*"=="" ( - for /f "delims=;" %%i in ('cd') do set "_DIR=%%i" -) else ( - set "_DIR=%~1" -) -cd %_DIR% - -rem TODO - Look up bat scripting example and fix the darn string. -if exist .git\NUL ( - git describe --abbrev=10 --always --tags -) - -rem Implement something like the following -rem for /f "tokens=1,2,3 delims=- " %%a in ("%gitdescribe%") do set version=%%a&set commits=%%b&set sha=%%c -rem echo %date?%-%commits%-%sha% - -:end -@endlocal -- cgit v1.2.3