http://git-wip-us.apache.org/repos/asf/incubator-wave/blob/d35211be/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomDocOpGenerator.java ---------------------------------------------------------------------- diff --git a/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomDocOpGenerator.java b/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomDocOpGenerator.java deleted file mode 100644 index 3db3715..0000000 --- a/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomDocOpGenerator.java +++ /dev/null @@ -1,1421 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -package org.waveprotocol.wave.model.testing; - -import org.waveprotocol.wave.model.document.bootstrap.BootstrapDocument; -import org.waveprotocol.wave.model.document.operation.Attributes; -import org.waveprotocol.wave.model.document.operation.AttributesUpdate; -import org.waveprotocol.wave.model.document.operation.DocOp; -import org.waveprotocol.wave.model.document.operation.DocOpCursor; -import org.waveprotocol.wave.model.document.operation.automaton.AutomatonDocument; -import org.waveprotocol.wave.model.document.operation.automaton.DocOpAutomaton; -import org.waveprotocol.wave.model.document.operation.automaton.DocOpAutomaton.ValidationResult; -import org.waveprotocol.wave.model.document.operation.automaton.DocOpAutomaton.ViolationCollector; -import org.waveprotocol.wave.model.document.operation.automaton.DocumentSchema; -import org.waveprotocol.wave.model.document.operation.impl.AnnotationBoundaryMapImpl; -import org.waveprotocol.wave.model.document.operation.impl.AnnotationMap; -import org.waveprotocol.wave.model.document.operation.impl.AttributesUpdateImpl; -import org.waveprotocol.wave.model.document.operation.impl.DocInitializationBuilder; -import org.waveprotocol.wave.model.document.operation.impl.DocOpBuffer; -import org.waveprotocol.wave.model.document.operation.impl.DocOpUtil; -import org.waveprotocol.wave.model.document.operation.impl.DocOpValidator; -import org.waveprotocol.wave.model.operation.OperationException; -import org.waveprotocol.wave.model.testing.RandomDocOpGenerator.Parameters.AnnotationOption; -import org.waveprotocol.wave.model.util.Preconditions; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collections; -import java.util.Comparator; -import java.util.HashSet; -import java.util.List; -import java.util.Set; -import java.util.TreeSet; - -/** - * Generates random document operations based on a document. They can be - * valid or invalid, depending on parameters. - */ -public final class RandomDocOpGenerator { - - /** - * Random number generator interface, to avoid the dependency on java.util.Random, - * which would prevent the use of this class with GWT. - */ - public interface RandomProvider { - /** @returns a pseudorandom non-negative integer smaller than upperBound */ - int nextInt(int upperBound); - - /** @returns a pseudorandom boolean */ - boolean nextBoolean(); - } - - private RandomDocOpGenerator() {} - - /** Parameters for random DocOp generation. */ - public static final class Parameters { - - /** - * An annotation key with the corresponding list of value alternatives. - */ - public static final class AnnotationOption { - final String key; - final List<String> valueAlternatives; - - public AnnotationOption(String key, List<String> valueAlternatives) { - Preconditions.checkNotNull(key, "key must not be null"); - Preconditions.checkNotNull(valueAlternatives, "valueAlternatives must not be null"); - this.key = key; - this.valueAlternatives = valueAlternatives; - } - - public String getKey() { - return key; - } - - public String randomValue(RandomProvider r) { - return randomElement(r, valueAlternatives); - } - } - - int maxOpeningComponents = 16; - int maxInsertLength = 10; - int maxDeleteLength = 5; - boolean valid = true; - // only relevant when producing invalid ops. - int maxSkipAfterEnd = 5; - - // We use lists here instead of sets to have an explicit fixed ordering, - // which helps reproducibility when generating pseudo-random operations. - // SortedSets would also work for this, but then we'd have to make - // AnnotationOptions comparable, which is more work. - - List<String> elementTypes = Collections.unmodifiableList(Arrays.asList( - "body", "line", "input", - "image", "caption", "br"// "gadget", - )); - List<String> attributeNames = Collections.unmodifiableList(Arrays.asList( - "_t", "t", "i", "attachment", - "style", "blipId", "state", "url", "fontWeight", "fontStyle", "invalid_dummy")); - // TODO: We should make attributeValues dependent on attributeNames (and perhaps on element - // types) so that we can randomly insert chess gadgets with a valid state and inline images - // with a proper attachment spec. - // - // updateAttributes will only generate attribute removals if null is in this list. - List<String> attributeValues = Collections.unmodifiableList(Arrays.asList( - null, "title", "li", - "h1", "h2", "h3", "h4", "", - "0", "1", "2", "3", "4", "5", "114", "9817")); - - List<AnnotationOption> annotationOptions = Collections.unmodifiableList( - Arrays.asList( - new AnnotationOption("a", Arrays.asList(null, "1", "2")), - new AnnotationOption("b", Arrays.asList(null, "1")), - new AnnotationOption("c", Arrays.asList(null, "1")) - )); - - public static final List<AnnotationOption> RENDERABLE_ANNOTATION_OPTIONS = - Collections.unmodifiableList(Arrays.asList( - new AnnotationOption("link/auto", - Arrays.asList(null, - "http://www.youtube.com/watch?v=NBplLTBBmiA&feature=hd";, - "http://code.google.com/p/wave-protocols/issues/entry";)), - new AnnotationOption("style/fontWeight", Arrays.asList(null, "bold")), - new AnnotationOption("style/textDecoration", Arrays.asList(null, "underline")) - )); - - - public List<String> attributeValues() { - return Collections.unmodifiableList(Arrays.asList("title", "li", "h1", "h2", "h3", "h4", "", - "0", "1", "2", "3", "4", "5", "114", "9817")); - } - - - public Parameters() { - } - - public int getMaxOpeningComponents() { - return maxOpeningComponents; - } - - /** - * @return the maxInsertLength - */ - public int getMaxInsertLength() { - return maxInsertLength; - } - - /** - * @return the maxDeleteLength - */ - public int getMaxDeleteLength() { - return maxDeleteLength; - } - - /** - * @return the annotationOptions - */ - public List<AnnotationOption> getAnnotationOptions() { - return Collections.unmodifiableList(annotationOptions); - } - - public Parameters setMaxOpeningComponents(int maxOpeningComponents) { - this.maxOpeningComponents = maxOpeningComponents; - return this; - } - - /** - * @param maxInsertLength the maxInsertLength to set - */ - public Parameters setMaxInsertLength(int maxInsertLength) { - this.maxInsertLength = maxInsertLength; - return this; - } - - /** - * @param maxDeleteLength the maxDeleteLength to set - */ - public Parameters setMaxDeleteLength(int maxDeleteLength) { - this.maxDeleteLength = maxDeleteLength; - return this; - } - - /** - * @param annotationOptions the annotationOptions to set - */ - public Parameters setAnnotationOptions(List<AnnotationOption> annotationOptions) { - this.annotationOptions = annotationOptions; - return this; - } - - // Gotta love auto-generated javadoc. - /** - * @return the valid - */ - public boolean getValidity() { - return valid; - } - - /** - * @param valid the valid to set - */ - public Parameters setValidity(boolean valid) { - this.valid = valid; - return this; - } - - public int getMaxSkipAfterEnd() { - return maxSkipAfterEnd; - } - - public Parameters setMaxSkipBeyondEnd(int maxSkipAfterEnd) { - this.maxSkipAfterEnd = maxSkipAfterEnd; - return this; - } - - /** - * Returns the list of keys from annotationOptions. - */ - public List<String> getAnnotationKeys() { - List<String> keys = new ArrayList<String>(annotationOptions.size()); - for (AnnotationOption o : annotationOptions) { - keys.add(o.key); - } - return Collections.unmodifiableList(keys); - } - - public List<String> getElementTypes() { - return elementTypes; - } - - public Parameters setElementTypes(List<String> elementTypes) { - this.elementTypes = elementTypes; - return this; - } - - public List<String> getAttributeNames() { - return attributeNames; - } - - public Parameters setAttributeNames(List<String> attributeNames) { - Preconditions.checkArgument( - new HashSet<String>(attributeNames).size() == attributeNames.size(), - "duplicate attribute name"); - this.attributeNames = attributeNames; - return this; - } - - public List<String> getAttributeValues() { - return attributeValues; - } - - public Parameters setAttributeValues(List<String> attributeValues) { - this.attributeValues = attributeValues; - return this; - } - - } - - private static <T> T randomElement(RandomProvider r, List<T> l) { - return l.get(r.nextInt(l.size())); - } - - private static int randomIntFromRange(RandomProvider r, int min, int limit) { - assert 0 <= min; // not really a precondition, but true in our case - assert min < limit; - - int x = r.nextInt(limit - min) + min; - assert min <= x; - assert x < limit; - return x; - } - - private static <T> void swap(ArrayList<T> a, int i, int j) { - T temp = a.get(i); - a.set(i, a.get(j)); - a.set(j, temp); - } - - private static void shuffle(RandomProvider r, ArrayList<?> a) { - int N = a.size(); - for (int i = 0; i < N; i++) { - int j = randomIntFromRange(r, i, N); - swap(a, i, j); - } - } - - - private interface Mapper<I, O> { - O map(I in); - } - - private static <I, O> O pickRandomNonNullMappedElement(RandomProvider r, List<I> in, - Mapper<I, O> mapper) { - List<I> list = new ArrayList<I>(in); - while (!list.isEmpty()) { - int index = randomIntFromRange(r, 0, list.size()); - O value = mapper.map(list.get(index)); - if (value != null) { - return value; - } - // Remove element efficiently by swapping in an element from the end. - list.set(index, list.get(list.size() - 1)); - list.remove(list.size() - 1); - } - return null; - } - - - private static class Generator { - - abstract class RandomizerOperationComponent { - abstract ValidationResult check(DocOpAutomaton a, ViolationCollector v); - abstract void apply(DocOpAutomaton a); - abstract void output(DocOpCursor c); - boolean isAnnotationBoundary() { return false; } - } - - enum Stage { - // all components are permitted - S1_UNRESTRICTED, - // if deletion stack and insertion stack are empty, permit nothing (go to next stage). - // while deletion stack is nonempty, permit annotation boundaries, deleteCharacters, - // deleteElementStarts and deleteElementEnds. Must move on to next stage as soon as - // deletion stack becomes empty. - // while insertion stack is nonempty, permit elementEnds. - S2_CLOSE_STRUCTURE, - // if annotations are open, close them - S3_CLOSE_ANNOTATIONS, - // if not at end of document, assert invalidity and skip to end of document. - S4_SKIP_TO_END; - } - - abstract class RandomOperationComponentGenerator { - // returns null if it couldn't generate a matching component - abstract RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage); - } - - class SkipGenerator extends RandomOperationComponentGenerator { - @SuppressWarnings("fallthrough") - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - final int distance; - switch (stage) { - case S1_UNRESTRICTED: - int maxDistance = a.maxRetainItemCount(); - if (maxDistance == 0) { - return null; - } - if (a.checkRetain(1, null).isIllFormed()) { - return null; - } - if (valid) { - if (!a.checkRetain(1, null).isValid()) { - return null; - } - int d = randomIntFromRange(r, 1, maxDistance + 1); - while (!a.checkRetain(d, null).isValid()) { - d--; - assert d > 0; - } - distance = d; - assert a.checkRetain(distance, null).isValid(); - } else { - distance = randomIntFromRange(r, maxDistance + 1, maxDistance + p.getMaxSkipAfterEnd()); - assert a.checkRetain(distance, null) == ValidationResult.INVALID_DOCUMENT; - } - break; - case S2_CLOSE_STRUCTURE: - case S3_CLOSE_ANNOTATIONS: - return null; - case S4_SKIP_TO_END: - if (!valid) { - throw new RuntimeException("Not implemented"); - } - switch (a.checkRetain(1, null)) { - case INVALID_DOCUMENT: - assert a.checkFinish(null).isValid(); - return null; - case VALID: - distance = a.maxRetainItemCount(); - assert distance > 0; - assert !a.checkFinish(null).isValid(); - break; - case INVALID_SCHEMA: - case ILL_FORMED: assert false; - default: - throw new RuntimeException("Unexpected validation result"); - } - break; - default: - throw new RuntimeException("Unexpected stage: " + stage); - } - return new RandomizerOperationComponent() { - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkRetain(distance, v); - } - - @Override - public void apply(DocOpAutomaton a) { - a.doRetain(distance); - } - - @Override - public void output(DocOpCursor c) { - c.retain(distance); - } - - @Override - public String toString() { - return "Skip(" + distance + ")"; - } - }; - } - } - - class CharactersGenerator extends RandomOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - if (stage != Stage.S1_UNRESTRICTED) { - return null; - } - ValidationResult v = a.checkCharacters("a", null); - if (v.isIllFormed()) { - return null; - } - int count; - if (valid) { - if (!v.isValid()) { - return null; - } - // TODO: implement this once we have size limits. - int max = p.getMaxInsertLength(); - if (max == 0) { - return null; - } - count = randomIntFromRange(r, 1, max + 1); - } else { - if (v.isValid()) { - // Exceed length of document (if p.maxInsertLength allows it). - int max = p.getMaxInsertLength(); - // TODO: implement this once we have size limits. - //count = randomIntFromRange(r, min, max + 1); - return null; - } else { - count = randomIntFromRange(r, 1, p.getMaxInsertLength()); - } - } - StringBuilder sb = new StringBuilder(); - assert count > 0; - char startChar = r.nextBoolean() ? 'a' : 'A'; - for (int i = 0; i < count; i++) { - if (i <= 26) { - sb.append((char) (startChar + i)); - } else { - sb.append('.'); - } - } - final String s = sb.toString(); - return new RandomizerOperationComponent() { - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkCharacters(s, v); - } - - @Override - public void apply(DocOpAutomaton a) { - a.doCharacters(s); - } - - @Override - public void output(DocOpCursor c) { - c.characters(s); - } - - @Override - public String toString() { - return "Characters(" + s + ")"; - } - }; - } - } - - class DeleteCharactersGenerator extends RandomOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - if (stage != Stage.S1_UNRESTRICTED && (stage != Stage.S2_CLOSE_STRUCTURE || a.deletionStackComplexityMeasure() == 0)) { - return null; - } - // TODO: In stage 2, this should perhaps be less random about how many characters - // it deletes. Alternatively, skip in stage 4 could be more random. - int nextChar = a.nextChar(0); - if (nextChar == -1 || - a.checkDeleteCharacters("" + ((char) nextChar), null).isIllFormed()) { - return null; - } - final int count; - if (valid) { - int max = Math.min(a.maxCharactersToDelete(), p.getMaxDeleteLength()); - if (max == 0) { - return null; - } - count = randomIntFromRange(r, 1, max + 1); - } else { - int max = p.getMaxDeleteLength(); - int min = a.maxCharactersToDelete() + 1; - if (min > max) { - return null; - } - count = randomIntFromRange(r, min, max + 1); - } - // TODO: implement invalid case, both by right char but wrong - // annotations (if possible) and wrong char. - StringBuilder b = new StringBuilder(); - for (int i = 0; i < count; i++) { - int c = a.nextChar(i); - assert c != -1; - b.append((char) c); - if (valid && !a.checkDeleteCharacters(b.toString(), null).isValid()) { - b.deleteCharAt(b.length() - 1); - break; - } - } - if (b.length() == 0) { - // TODO: simplify this method - return null; - } - final String s = b.toString(); - RandomizerOperationComponent c = new RandomizerOperationComponent() { - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkDeleteCharacters(s, v); - } - - @Override - public void apply(DocOpAutomaton a) { - a.doDeleteCharacters(s); - } - - @Override - public void output(DocOpCursor c) { - c.deleteCharacters(s); - } - - @Override - public String toString() { - return "DeleteCharacters(" + s + ")"; - } - }; - if (c.check(a, null).isValid() != valid) { - return null; - } else { - return c; - } - } - } - - interface AttributesUpdateChecker { - ValidationResult check(AttributesUpdate u); - } - - // returns null on failure - AttributesUpdate generateRandomAttributesUpdate(final boolean valid, - final Attributes oldAttributes, - final AttributesUpdateChecker checker) { - AttributesUpdate accu = new AttributesUpdateImpl(); - if (valid && !checker.check(accu).isValid() - || !valid && checker.check(accu).isIllFormed()) { - return null; - } - if (!valid) { - // If we want an invalid component, and it's not already invalid without - // any attributes, make it invalid by adding an invalid attribute first. - if (checker.check(accu).isValid()) { - assert accu.changeSize() == 0; - accu = pickRandomNonNullMappedElement(r, - p.getAttributeNames(), new Mapper<String, AttributesUpdate>() { - @Override - public AttributesUpdate map(final String name) { - return pickRandomNonNullMappedElement(r, p.getAttributeValues(), - new Mapper<String, AttributesUpdate> () { - @Override - public AttributesUpdate map(String value) { - AttributesUpdate b = new AttributesUpdateImpl(name, - oldAttributes.get(name), value); - switch (checker.check(b)) { - case ILL_FORMED: - return null; - case INVALID_DOCUMENT: - case INVALID_SCHEMA: - return b; - case VALID: - return null; - default: - throw new RuntimeException("Unexpected validation result"); - } - } - }); - } - }); - if (accu == null) { - return null; - } - } - assert !checker.check(accu).isValid(); - // Flip a coin and terminate if the number of attributes was really - // supposed to be zero. - if (r.nextBoolean()) { - return accu; - } - } - while (r.nextBoolean()) { - final AttributesUpdate finalAccu = accu; - AttributesUpdate newAccu = pickRandomNonNullMappedElement(r, - p.getAttributeNames(), new Mapper<String, AttributesUpdate>() { - @Override - public AttributesUpdate map(final String name) { - for (int i = 0; i < finalAccu.changeSize(); i++) { - if (finalAccu.getChangeKey(i).equals(name)) { - return null; - } - } - return pickRandomNonNullMappedElement(r, p.getAttributeValues(), - new Mapper<String, AttributesUpdate>() { - @Override - public AttributesUpdate map(String value) { - AttributesUpdate b = finalAccu.composeWith(new AttributesUpdateImpl(name, - oldAttributes.get(name), value)); - assert b != finalAccu; // assert non-destructiveness - ValidationResult v = checker.check(b); - if (valid && !v.isValid() || !valid && v.isIllFormed()) { - return null; - } else { - return b; - } - } - }); - } - }); - if (newAccu == null) { - return accu; - } - accu = newAccu; - } - return accu; - } - - class ElementStartGenerator extends RandomOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - switch (stage) { - case S1_UNRESTRICTED: - return generate(a, valid); - case S2_CLOSE_STRUCTURE: - case S3_CLOSE_ANNOTATIONS: - case S4_SKIP_TO_END: - return null; - default: - throw new RuntimeException("Unexpected stage: " + stage); - } - } - - RandomizerOperationComponent generateGivenTag(final DocOpAutomaton a, final boolean valid, - final String tag) { - { - ValidationResult v = a.checkElementStart(tag, Attributes.EMPTY_MAP, null); - if (valid && !v.isValid() || !valid && v.isIllFormed()) { - // Early exit if we can't build an element start with this tag. - return null; - } - } - - AttributesUpdate u = generateRandomAttributesUpdate(valid, Attributes.EMPTY_MAP, - new AttributesUpdateChecker() { - @Override - public ValidationResult check(AttributesUpdate u) { - Attributes attrs = Attributes.EMPTY_MAP.updateWith(u); - return a.checkElementStart(tag, attrs, null); - } - }); - if (u == null) { - return null; - } else { - final Attributes attributes = Attributes.EMPTY_MAP.updateWith(u); - return new RandomizerOperationComponent() { - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkElementStart(tag, attributes, v); - } - - @Override - public void apply(DocOpAutomaton a) { - a.doElementStart(tag, attributes); - } - - @Override - public void output(DocOpCursor c) { - c.elementStart(tag, attributes); - } - - @Override - public String toString() { - return "ElementStart(" + tag + ", " + attributes + ")"; - } - }; - } - } - - RandomizerOperationComponent generate(final DocOpAutomaton a, final boolean valid) { - return pickRandomNonNullMappedElement(r, p.getElementTypes(), - new Mapper<String, RandomizerOperationComponent>() { - @Override - public RandomizerOperationComponent map(final String tag) { - return generateGivenTag(a, valid, tag); - } - }); - } - } - - abstract class RandomConstantOperationComponentGenerator - extends RandomOperationComponentGenerator { - abstract ValidationResult check(DocOpAutomaton a, ViolationCollector v); - abstract void apply(DocOpAutomaton a); - abstract void output(DocOpCursor c); - - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid) { - switch (check(a, null)) { - case ILL_FORMED: - return null; - case VALID: - if (!valid) { - return null; - } - break; - case INVALID_DOCUMENT: - if (valid) { - return null; - } - break; - case INVALID_SCHEMA: - if (valid) { - return null; - } - break; - default: - throw new RuntimeException("Unexpected validation result"); - } - return new RandomizerOperationComponent() { - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return RandomConstantOperationComponentGenerator.this.check(a, v); - } - - @Override - public void apply(DocOpAutomaton a) { - RandomConstantOperationComponentGenerator.this.apply(a); - } - - @Override - public void output(DocOpCursor c) { - RandomConstantOperationComponentGenerator.this.output(c); - } - - @Override - public String toString() { - return "Constant component from " - + RandomConstantOperationComponentGenerator.this.getClass().getName(); - } - }; - } - } - - class ElementEndGenerator extends RandomConstantOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - switch (stage) { - case S1_UNRESTRICTED: - return generate(a, valid); - case S2_CLOSE_STRUCTURE: - if (a.insertionStackComplexityMeasure() == 0) { - return null; - } - return generate(a, valid); - case S3_CLOSE_ANNOTATIONS: - case S4_SKIP_TO_END: - return null; - default: - throw new RuntimeException("Unexpected stage: " + stage); - } - } - - @Override - ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkElementEnd(v); - } - - @Override - void apply(DocOpAutomaton a) { - a.doElementEnd(); - } - - @Override - void output(DocOpCursor c) { - c.elementEnd(); - } - } - - class DeleteElementStartGenerator extends RandomOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - switch (stage) { - case S1_UNRESTRICTED: - return generate(a, valid); - case S2_CLOSE_STRUCTURE: - if (a.deletionStackComplexityMeasure() == 0) { - return null; - } - return generate(a, valid); - case S3_CLOSE_ANNOTATIONS: - case S4_SKIP_TO_END: - return null; - default: - throw new RuntimeException("Unexpected stage: " + stage); - } - } - - RandomizerOperationComponent generate(final DocOpAutomaton a, final boolean valid) { - final String tag = a.currentElementStartTag(); - final Attributes oldAttrs = a.currentElementStartAttributes(); - if (tag == null) { - assert oldAttrs == null; - return null; - } - assert oldAttrs != null; - switch (a.checkDeleteElementStart(tag, oldAttrs, null)) { - case ILL_FORMED: - case INVALID_DOCUMENT: // TODO: bring back generating invalid ops - case INVALID_SCHEMA: - return null; - case VALID: - return new RandomizerOperationComponent() { - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkDeleteElementStart(tag, oldAttrs, v); - } - - @Override - public void apply(DocOpAutomaton a) { - a.doDeleteElementStart(tag, oldAttrs); - } - - @Override - public void output(DocOpCursor c) { - c.deleteElementStart(tag, oldAttrs); - } - }; - default: - throw new RuntimeException("Unexpected validation result"); - } - } - } - - class DeleteElementEndGenerator extends RandomConstantOperationComponentGenerator { - @Override - void apply(DocOpAutomaton a) { - a.doDeleteElementEnd(); - } - - @Override - ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkDeleteElementEnd(v); - } - - @Override - void output(DocOpCursor c) { - c.deleteElementEnd(); - } - - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - switch (stage) { - case S1_UNRESTRICTED: - return generate(a, valid); - case S2_CLOSE_STRUCTURE: - if (a.deletionStackComplexityMeasure() == 0) { - return null; - } - return generate(a, valid); - case S3_CLOSE_ANNOTATIONS: - case S4_SKIP_TO_END: - return null; - default: - throw new RuntimeException("Unexpected stage: " + stage); - } - } - } - - - class ReplaceAttributesGenerator extends RandomOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(final DocOpAutomaton a, boolean valid, Stage stage) { - if (stage != Stage.S1_UNRESTRICTED) { - return null; - } - final Attributes oldAttrs = a.currentElementStartAttributes(); - if (oldAttrs == null) { - if (valid) { - return null; - } - } - if (!valid) { - // TODO: bring this back. - // several cases: invalid because of wrong old attributes, or invalid - // because of schema violation of new attributes, or because no - // element start here - throw new RuntimeException("Not implemented"); - } - AttributesUpdate u = generateRandomAttributesUpdate(valid, - oldAttrs, new AttributesUpdateChecker() { - @Override - public ValidationResult check(AttributesUpdate u) { - return a.checkReplaceAttributes(oldAttrs, oldAttrs.updateWith(u), null); - } - }); - - if (u == null) { - return null; - } - - final Attributes newAttrs = oldAttrs.updateWith(u); - return new RandomizerOperationComponent() { - @Override - public void apply(DocOpAutomaton a) { - a.doReplaceAttributes(oldAttrs, newAttrs); - } - - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkReplaceAttributes(oldAttrs, newAttrs, v); - } - - @Override - public void output(DocOpCursor c) { - c.replaceAttributes(oldAttrs, newAttrs); - } - - @Override - public String toString() { - return "ReplaceAttributes(" + oldAttrs + ", " + newAttrs + ")"; - } - }; - } - } - - class UpdateAttributesGenerator extends RandomOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(final DocOpAutomaton a, boolean valid, Stage stage) { - if (stage != Stage.S1_UNRESTRICTED) { - return null; - } - final Attributes oldAttrs = a.currentElementStartAttributes(); - if (oldAttrs == null) { - if (valid) { - return null; - } - } - if (!valid) { - // TODO: bring this back. - // several cases: invalid because of wrong old attributes, or invalid - // because of schema violation of new attributes, or because no - // element start here - throw new RuntimeException("Not implemented"); - } - final AttributesUpdate update = generateRandomAttributesUpdate(valid, - oldAttrs, new AttributesUpdateChecker() { - @Override - public ValidationResult check(AttributesUpdate u) { - return a.checkUpdateAttributes(u, null); - } - }); - - if (update == null) { - return null; - } - - return new RandomizerOperationComponent() { - @Override - public void apply(DocOpAutomaton a) { - a.doUpdateAttributes(update); - } - - @Override - public ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkUpdateAttributes(update, v); - } - - @Override - public void output(DocOpCursor c) { - c.updateAttributes(update); - } - - @Override - public String toString() { - return "UpdateAttributes(" + update + ")"; - } - }; - } - } - - interface RunnableWithException<E extends Throwable> { - void run() throws E; - } - - class AnnotationBoundaryGenerator extends RandomOperationComponentGenerator { - @Override - RandomizerOperationComponent generate(DocOpAutomaton a, boolean valid, Stage stage) { - switch (stage) { - case S1_UNRESTRICTED: - case S2_CLOSE_STRUCTURE: - return generateWithLookahead(a, valid, stage); - case S3_CLOSE_ANNOTATIONS: - assert valid; - return generateClosing(a); - case S4_SKIP_TO_END: - return null; - default: - throw new RuntimeException("Unexpected stage: " + stage); - } - } - - RandomizerOperationComponent generate(final AnnotationBoundaryMapImpl map) { - return new RandomizerOperationComponent() { - @Override - void apply(DocOpAutomaton a) { - a.doAnnotationBoundary(map); - } - - @Override - ValidationResult check(DocOpAutomaton a, ViolationCollector v) { - return a.checkAnnotationBoundary(map, v); - } - - @Override - void output(DocOpCursor c) { - c.annotationBoundary(map); - } - - @Override - boolean isAnnotationBoundary() { return true; } - - @Override - public String toString() { - return "AnnotationBoundary(" + map + ")"; - } - }; - } - - String[] toArray(ArrayList<String> a) { - return a.toArray(new String[0]); - } - - RandomizerOperationComponent generateClosing(DocOpAutomaton a) { - if (a.openAnnotations().isEmpty()) { - return null; - } - ArrayList<String> l = new ArrayList<String>(a.openAnnotations()); - Collections.sort(l); - AnnotationBoundaryMapImpl map = - AnnotationBoundaryMapImpl.builder().initializationEnd( - toArray(l)).build(); - assert !a.checkAnnotationBoundary(map, null).isIllFormed(); - return generate(map); - } - - class Result extends Exception { - final RandomizerOperationComponent component; - Result(RandomizerOperationComponent component) { - this.component = component; - } - } - - class StringNullComparator implements Comparator<String> { - @Override - public int compare(String a, String b) { - if (a == b) { - return 0; - } - if (a == null) { - return -1; - } - if (b == null) { - return 1; - } - return a.compareTo(b); - } - } - - RandomizerOperationComponent generateWithLookahead(final DocOpAutomaton a, boolean valid, - final Stage stage) { - { - ValidationResult r = a.checkAnnotationBoundary( - AnnotationBoundaryMapImpl.builder().updateValues("a", null, "1").build(), null); - assert r.isIllFormed() || r.isValid(); - if (r.isIllFormed()) { - return null; - } - } - Set<String> keySet = new TreeSet<String>(new StringNullComparator()); - for (AnnotationOption o : p.getAnnotationOptions()) { - keySet.add(o.key); - } - keySet.addAll(a.currentAnnotations().keySet()); - keySet.addAll(a.inheritedAnnotations().keySet()); - final ArrayList<String> keys = new ArrayList<String>(keySet); - - Collections.sort(keys); - - // For every key, either pick it, or don't (choice point, recursively - // explore both options). - - // For each key, one option is to end that key if it currently is in - // openAnnotations(). - // Another option is not to end that key: In that case, given the key, - // the valid old values are those from annotationOptions and - // those from currentAnnotations() (for deletions) and - // those from inheritedAnnotations() (for insertions); - // the valid new values are those from annotationOptions and - // those from inheritedAnnotations() (for deletion). - // - // Given the full map, we need to check if the component is valid, then - // temporarily apply it to find out if there is any valid component - // to follow up with. - - final RunnableWithException<Result> chooseKeys = new RunnableWithException<Result>() { - - ArrayList<String> keysToEnd = new ArrayList<String>(); - ArrayList<String> changeKeys = new ArrayList<String>(); - ArrayList<String> changeOldValues = new ArrayList<String>(); - ArrayList<String> changeNewValues = new ArrayList<String>(); - - void tryThisOption() throws Result { - AnnotationBoundaryMapImpl map = AnnotationBoundaryMapImpl.builder() - .initializationEnd(toArray(keysToEnd)) - .updateValues(toArray(changeKeys), toArray(changeOldValues), - toArray(changeNewValues)).build(); - final RandomizerOperationComponent component = generate(map); - DocOpAutomaton temp = new DocOpAutomaton(a); - ViolationCollector v = new ViolationCollector(); - component.check(temp, v); - assert !component.check(temp, null).isIllFormed(); - component.apply(temp); -// System.err.println("begin lookahead for " + map); - RandomizerOperationComponent followup = pickComponent(temp, stage); - if (followup != null) { -// System.err.println("end lookahead, success"); - throw new Result(component); - } -// System.err.println("end lookahead, failed"); - } - - void removeLastMaybe(ArrayList<String> l, int lastItemIndex) { - assert lastItemIndex == l.size() || lastItemIndex == l.size() - 1; - if (lastItemIndex == l.size() - 1) { - l.remove(lastItemIndex); - } - } - - void take(int nextKeyIndex, String key) throws Result { - assert key != null; - if (a.openAnnotations().contains(key)) { - int oldSize = keysToEnd.size(); - try { - keysToEnd.add(key); - nextKey(nextKeyIndex); - } finally { - removeLastMaybe(keysToEnd, oldSize); - } - } - - Set<String> valueSet = new TreeSet<String>(new StringNullComparator()); - for (AnnotationOption o : p.getAnnotationOptions()) { - if (key.equals(o.key)) { - valueSet.addAll(o.valueAlternatives); - } - } - AnnotationMap inheritedAnnotations = a.inheritedAnnotations(); - if (inheritedAnnotations.containsKey(key)) { - valueSet.add(inheritedAnnotations.get(key)); - } else { - valueSet.add(null); - } - ArrayList<String> newValues = new ArrayList<String>(valueSet); - AnnotationMap currentAnnotations = a.currentAnnotations(); - if (currentAnnotations.containsKey(key)) { - valueSet.add(currentAnnotations.get(key)); - } else { - valueSet.add(null); - } - ArrayList<String> oldValues = new ArrayList<String>(valueSet); - - shuffle(r, oldValues); - shuffle(r, newValues); - - for (String oldValue : oldValues) { - for (String newValue : newValues) { - assert changeKeys.size() == changeOldValues.size(); - assert changeKeys.size() == changeNewValues.size(); - int oldSize = changeKeys.size(); - try { - changeKeys.add(key); - changeOldValues.add(oldValue); - changeNewValues.add(newValue); - nextKey(nextKeyIndex); - } finally { - removeLastMaybe(changeNewValues, oldSize); - removeLastMaybe(changeOldValues, oldSize); - removeLastMaybe(changeKeys, oldSize); - assert changeKeys.size() == changeOldValues.size(); - assert changeKeys.size() == changeNewValues.size(); - } - } - } - } - - void nextKey(int nextKeyIndex) throws Result { - if (nextKeyIndex >= keys.size()) { - tryThisOption(); - return; - } - String key = keys.get(nextKeyIndex); - boolean take = r.nextBoolean(); - if (take) { - take(nextKeyIndex + 1, key); - nextKey(nextKeyIndex + 1); - } else { - nextKey(nextKeyIndex + 1); - take(nextKeyIndex + 1, key); - } - } - - @Override - public void run() throws Result { - nextKey(0); - } - }; - - try { - chooseKeys.run(); - } catch (Result e) { - return e.component; - } - return null; - } - } - - private static boolean equal(Object a, Object b) { - return a == null ? b == null : a.equals(b); - } - - final RandomProvider r; - final Parameters p; - final AutomatonDocument doc; - - Generator(RandomProvider r, Parameters p, AutomatonDocument doc) { - this.r = r; - this.p = p; - this.doc = doc; - } - - final List<RandomOperationComponentGenerator> componentGenerators = - Arrays.asList( - new AnnotationBoundaryGenerator(), - new CharactersGenerator(), - new ElementStartGenerator(), - new ElementEndGenerator(), - new SkipGenerator(), - new DeleteCharactersGenerator(), - new DeleteElementStartGenerator(), - new DeleteElementEndGenerator(), - new ReplaceAttributesGenerator(), - new UpdateAttributesGenerator() - ); - - DocOp generate() { - DocOpAutomaton a = new DocOpAutomaton(doc, DocumentSchema.NO_SCHEMA_CONSTRAINTS); - DocOpBuffer b = new DocOpBuffer(); - generate1(a, b); - return b.finish(); - } - - RandomizerOperationComponent pickComponent(final DocOpAutomaton a, final Stage stage) { -// System.err.println("stage: " + stage); - RandomizerOperationComponent component = pickRandomNonNullMappedElement(r, - componentGenerators, - new Mapper<RandomOperationComponentGenerator, RandomizerOperationComponent>() { - @Override - public RandomizerOperationComponent map(RandomOperationComponentGenerator g) { -// System.err.println("trying generator " + g); - RandomizerOperationComponent c = g.generate(a, true, stage); - if (c != null) { - assert c.check(a, null).isValid(); - } - return c; - } - }); -// System.err.println("picked " + component); - return component; - } - - RandomizerOperationComponent generate2(DocOpAutomaton a, DocOpCursor output, Stage stage) { - RandomizerOperationComponent component = pickComponent(a, stage); - assert component != null; - component.apply(a); - component.output(output); - return component; - } - - void generate1(DocOpAutomaton a, DocOpCursor output) { - if (!p.getValidity()) { - throw new RuntimeException("generation of invalid operations not supported yet"); - } - int desiredNumComponents = randomIntFromRange(r, 0, p.getMaxOpeningComponents()); - int numComponentsPicked = 0; - while (numComponentsPicked < desiredNumComponents) { - RandomizerOperationComponent component = generate2(a, output, Stage.S1_UNRESTRICTED); - if (!component.isAnnotationBoundary()) { - numComponentsPicked++; - } - } - - while (a.deletionStackComplexityMeasure() > 0) { - generate2(a, output, Stage.S2_CLOSE_STRUCTURE); - } - - while (a.insertionStackComplexityMeasure() > 0) { - int before = a.insertionStackComplexityMeasure(); - generate2(a, output, Stage.S2_CLOSE_STRUCTURE); - assert a.insertionStackComplexityMeasure() <= before; - } - - if (!a.openAnnotations().isEmpty()) { - generate2(a, output, Stage.S3_CLOSE_ANNOTATIONS); - assert a.openAnnotations().isEmpty(); - } - - if (a.maxRetainItemCount() > 0) { - generate2(a, output, Stage.S4_SKIP_TO_END); - assert a.maxRetainItemCount() == 0; - } - } - } - - /** - * Returns a randomly-generated document operation based on the given document, - * parameters, and schema. - */ - public static DocOp generate(RandomProvider r, Parameters p, AutomatonDocument doc) { - DocOp op = new Generator(r, p, doc).generate(); - ViolationCollector v = new ViolationCollector(); - DocOpValidator.validate(v, null, doc, op); - assert !v.isIllFormed(); - assert p.getValidity() == v.isValid(); - return op; - } - - - /** - * Stand-alone main() for quick experimentation. - */ - public static void main(String[] args) throws OperationException { - BootstrapDocument initialDoc = new BootstrapDocument(); - initialDoc.consume(new DocInitializationBuilder() - .elementStart("blip", Attributes.EMPTY_MAP) - .elementStart("p", Attributes.EMPTY_MAP) - .characters("abc") - .elementEnd() - .elementEnd().build()); - - Parameters p = new Parameters(); - - p.setMaxOpeningComponents(10); - - RandomProvider r = RandomProviderImpl.ofSeed(2538); - for (int i = 0; i < 200; i++) { - BootstrapDocument doc = new BootstrapDocument(); - doc.consume(initialDoc.asOperation()); - for (int j = 0; j < 20; j++) { - System.err.println("i=" + i + ", j=" + j); - System.err.println("old: " + DocOpUtil.toXmlString(doc.asOperation())); - System.err.println("old: " + DocOpUtil.toConciseString(doc.asOperation())); - DocOp op = generate(r, p, doc); - System.err.println("op: " + DocOpUtil.toConciseString(op)); - doc.consume(op); - System.err.println("new: " + DocOpUtil.toConciseString(doc.asOperation())); - System.err.println("new: " + DocOpUtil.toXmlString(doc.asOperation())); - if (!DocOpValidator.validate(null, DocumentSchema.NO_SCHEMA_CONSTRAINTS, - doc.asOperation()).isValid()) { - throw new RuntimeException("doc not valid"); - } - } - } - } - -}
http://git-wip-us.apache.org/repos/asf/incubator-wave/blob/d35211be/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomNindoGenerator.java ---------------------------------------------------------------------- diff --git a/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomNindoGenerator.java b/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomNindoGenerator.java deleted file mode 100644 index 65d97b7..0000000 --- a/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomNindoGenerator.java +++ /dev/null @@ -1,776 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -package org.waveprotocol.wave.model.testing; - -import org.waveprotocol.wave.model.document.indexed.IndexedDocument; -import org.waveprotocol.wave.model.document.operation.Attributes; -import org.waveprotocol.wave.model.document.operation.Nindo; -import org.waveprotocol.wave.model.document.operation.Nindo.NindoCursor; -import org.waveprotocol.wave.model.document.operation.NindoAutomaton; -import org.waveprotocol.wave.model.document.operation.NindoValidator; -import org.waveprotocol.wave.model.document.operation.automaton.DocOpAutomaton.ValidationResult; -import org.waveprotocol.wave.model.document.operation.automaton.DocOpAutomaton.ViolationCollector; -import org.waveprotocol.wave.model.document.operation.automaton.DocumentSchema; -import org.waveprotocol.wave.model.document.operation.impl.AttributesImpl; -import org.waveprotocol.wave.model.document.operation.impl.AttributesUpdateImpl; -import org.waveprotocol.wave.model.document.raw.impl.Element; -import org.waveprotocol.wave.model.document.raw.impl.Node; -import org.waveprotocol.wave.model.document.raw.impl.Text; -import org.waveprotocol.wave.model.testing.RandomDocOpGenerator.Parameters; -import org.waveprotocol.wave.model.testing.RandomDocOpGenerator.RandomProvider; -import org.waveprotocol.wave.model.util.Pair; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.List; -import java.util.Set; - -/** - * Generates random document operations based on a document. They can be - * valid or invalid, depending on parameters. - * - * @author [email protected] (Christian Ohler) - */ -@SuppressWarnings("unchecked") // TODO(ohler, danilatos): declare generics properly -public final class RandomNindoGenerator { - - private RandomNindoGenerator() {} - - private static <T> T randomElement(RandomProvider r, List<T> l) { - return l.get(r.nextInt(l.size())); - } - - private static <T> T randomElement(RandomProvider r, Set<T> s) { - int n = randomIntFromRange(r, 0, s.size()); - for (T e : s) { - if (n == 0) { - return e; - } - n--; - } - assert false; - throw new RuntimeException("fell off end of loop"); - } - - private static int randomIntFromRange(RandomProvider r, int min, int limit) { - assert 0 <= min; // not really a precondition, but true in our case - assert min < limit; - - int x = r.nextInt(limit - min) + min; - assert min <= x; - assert x < limit; - return x; - } - - private interface Mapper<I, O> { - O map(I in); - } - - private static <I, O> O pickRandomNonNullMappedElement(RandomProvider r, List<I> in, - Mapper<I, O> mapper) { - List<I> list = new ArrayList<I>(in); - while (!list.isEmpty()) { - int index = randomIntFromRange(r, 0, list.size()); - O value = mapper.map(list.get(index)); - if (value != null) { - return value; - } - // Remove element efficiently by swapping in an element from the end. - list.set(index, list.get(list.size() - 1)); - list.remove(list.size() - 1); - } - return null; - } - - - private static class Generator { - - interface RandomizerMutationComponent { - ValidationResult check(ViolationCollector v); - void apply(); - } - - abstract class RandomMutationComponentGenerator { - abstract RandomizerMutationComponent generate(boolean valid); - // 0 means this transition will never be needed to complete an operation - // (e.g., skip or setAttributes) - // -1 means this transition may be needed to complete an operation but - // increases the size of the structural stack (e.g. deleteElementStart) - // -2 means this transition may be needed to complete an operation but - // does not change the size of the structural stack (e.g. deleteCharacters) - // -3 means this transition may be needed to complete an operation and - // decreases the size of the structural stack (e.g. deleteElementEnd) - abstract int potential(); - } - - class SkipGenerator extends RandomMutationComponentGenerator { - @Override - public int potential() { - return 0; - } - - @Override - RandomizerMutationComponent generate(boolean valid) { - int maxDistance = a.maxSkipDistance(); - if (maxDistance == 0) { - return null; - } - if (a.checkSkip(1, null).isIllFormed()) { - return null; - } - final int distance; - if (valid) { - distance = randomIntFromRange(r, 1, maxDistance + 1); - assert a.checkSkip(distance, null).isValid(); - } else { - distance = randomIntFromRange(r, maxDistance + 1, maxDistance + p.getMaxSkipAfterEnd()); - assert a.checkSkip(distance, null) == ValidationResult.INVALID_DOCUMENT; - } - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return a.checkSkip(distance, v); - } - - @Override - public void apply() { - a.doSkip(distance); - targetDoc.skip(distance); - } - }; - } - } - - class CharactersGenerator extends RandomMutationComponentGenerator { - @Override - public int potential() { - return 0; - } - - @Override - RandomizerMutationComponent generate(boolean valid) { - ValidationResult v = a.checkCharacters("a", null); - if (v.isIllFormed()) { - return null; - } - int count; - if (valid) { - if (!v.isValid()) { - return null; - } - int max = Math.min(a.maxLengthIncrease(), p.getMaxInsertLength()); - if (max == 0) { - return null; - } - count = randomIntFromRange(r, 1, max + 1); - } else { - if (v.isValid()) { - // Exceed length of document (if p.maxInsertLength allows it). - int max = p.getMaxInsertLength(); - int min = a.maxLengthIncrease() + 1; - if (min > max) { - return null; - } - count = randomIntFromRange(r, min, max + 1); - } else { - count = randomIntFromRange(r, 1, p.getMaxInsertLength()); - } - } - StringBuilder sb = new StringBuilder(); - for (int i = 0; i < count; i++) { - if (i <= 26) { - sb.append((char) ('a' + i)); - } else { - sb.append('.'); - } - } - final String s = sb.toString(); - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return a.checkCharacters(s, v); - } - - @Override - public void apply() { - a.doCharacters(s); - targetDoc.characters(s); - } - }; - } - } - - class DeleteCharactersGenerator extends RandomMutationComponentGenerator { - @Override - RandomizerMutationComponent generate(boolean valid) { - if (a.checkDeleteCharacters(1, null).isIllFormed()) { - return null; - } - final int count; - if (valid) { - int max = Math.min(a.maxCharactersToDelete(), p.getMaxDeleteLength()); - if (max == 0) { - return null; - } - count = randomIntFromRange(r, 1, max + 1); - } else { - int max = p.getMaxDeleteLength(); - int min = a.maxCharactersToDelete() + 1; - if (min > max) { - return null; - } - count = randomIntFromRange(r, min, max + 1); - } - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return a.checkDeleteCharacters(count, v); - } - - @Override - public void apply() { - a.doDeleteCharacters(count); - targetDoc.deleteCharacters(count); - } - }; - } - - @Override - public int potential() { - return -2; - } - } - - interface AttributesChecker { - ValidationResult check(Attributes attrs); - } - - Attributes generateRandomAttributes(final boolean valid, final AttributesChecker checker) { - Attributes attrAccu = Attributes.EMPTY_MAP; - if (valid && !checker.check(Attributes.EMPTY_MAP).isValid() - || !valid && checker.check(Attributes.EMPTY_MAP).isIllFormed()) { - return null; - } - if (!valid) { - // If we want an invalid component, and it's not already invalid without - // any attributes, make it invalid by adding an invalid attribute first. - if (checker.check(attrAccu).isValid()) { - assert attrAccu.isEmpty(); - attrAccu = pickRandomNonNullMappedElement(r, - p.getAttributeNames(), new Mapper<String, Attributes>() { - @Override - public Attributes map(final String name) { - return pickRandomNonNullMappedElement(r, p.getAttributeValues(), - new Mapper<String, Attributes> () { - @Override - public Attributes map(String value) { - Attributes b = new AttributesImpl(name, value); - switch (checker.check(b)) { - case ILL_FORMED: - return null; - case INVALID_DOCUMENT: - case INVALID_SCHEMA: - return b; - case VALID: - return null; - default: - throw new RuntimeException("unexpected validation result"); - } - } - }); - } - }); - if (attrAccu == null) { - return null; - } - } - assert !checker.check(attrAccu).isValid(); - // Flip a coin and terminate if the number of attributes was really - // supposed to be zero. - if (r.nextBoolean()) { - return attrAccu; - } - } - while (r.nextBoolean()) { - final Attributes finalAttrAccu = attrAccu; - Pair<String, String> newAttr = pickRandomNonNullMappedElement(r, - p.getAttributeNames(), new Mapper<String, Pair<String, String>>() { - @Override - public Pair<String, String> map(final String name) { - if (finalAttrAccu.containsKey(name)) { - return null; - } - return pickRandomNonNullMappedElement(r, p.getAttributeValues(), - new Mapper<String, Pair<String, String>>() { - @Override - public Pair<String, String> map(String value) { - Attributes b = finalAttrAccu.updateWith( - new AttributesUpdateImpl(name, null, value)); - assert b != finalAttrAccu; // assert non-destructiveness - ValidationResult v = checker.check(b); - if (valid && !v.isValid() || !valid && v.isIllFormed()) { - return null; - } else { - return Pair.of(name, value); - } - } - }); - } - }); - if (newAttr == null) { - return attrAccu; - } - attrAccu = attrAccu.updateWith( - new AttributesUpdateImpl(newAttr.getFirst(), null, newAttr.getSecond())); - } - return attrAccu; - } - - class ElementStartGenerator extends RandomMutationComponentGenerator { - @Override - public int potential() { - return 0; - } - - @Override - RandomizerMutationComponent generate(final boolean valid) { - Pair<String, Attributes> args = pickRandomNonNullMappedElement(r, p.getElementTypes(), - new Mapper<String, Pair<String, Attributes>>() { - @Override - public Pair<String, Attributes> map(final String tag) { - { - ValidationResult v = a.checkElementStart(tag, Attributes.EMPTY_MAP, null); - if (valid && !v.isValid() || !valid && v.isIllFormed()) { - // Early exit if we can't build an element start with this tag. - return null; - } - } - - Attributes attrs = generateRandomAttributes(valid, - new AttributesChecker() { - @Override - public ValidationResult check(Attributes attrs) { - return a.checkElementStart(tag, attrs, null); - } - }); - if (attrs == null) { - return null; - } else { - return Pair.of(tag, attrs); - } - } - }); - if (args == null) { - return null; - } - final String tag = args.getFirst(); - final Attributes attributes = args.getSecond(); - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return a.checkElementStart(tag, attributes, v); - } - - @Override - public void apply() { - a.doElementStart(tag, attributes); - targetDoc.elementStart(tag, attributes); - } - }; - } - } - - abstract class RandomConstantMutationComponentGenerator - extends RandomMutationComponentGenerator { - abstract ValidationResult check(ViolationCollector v); - abstract void apply(); - - @Override - RandomizerMutationComponent generate(boolean valid) { - switch (check(null)) { - case ILL_FORMED: - return null; - case VALID: - if (!valid) { - return null; - } - break; - case INVALID_DOCUMENT: - if (valid) { - return null; - } - break; - case INVALID_SCHEMA: - if (valid) { - return null; - } - break; - default: - throw new RuntimeException("unexpected validation result"); - } - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return RandomConstantMutationComponentGenerator.this.check(v); - } - - @Override - public void apply() { - RandomConstantMutationComponentGenerator.this.apply(); - } - - @Override - public String toString() { - return this.getClass().getName() + " from " - + RandomConstantMutationComponentGenerator.this.getClass().getName(); - } - }; - } - } - - class ElementEndGenerator extends RandomConstantMutationComponentGenerator { - @Override - int potential() { - return -3; - } - - @Override - ValidationResult check(ViolationCollector v) { - return a.checkElementEnd(v); - } - - @Override - void apply() { - a.doElementEnd(); - targetDoc.elementEnd(); - } - } - - class DeleteElementStartGenerator extends RandomConstantMutationComponentGenerator { - @Override - int potential() { - return -1; - } - - @Override - ValidationResult check(ViolationCollector v) { - return a.checkDeleteElementStart(v); - } - - @Override - void apply() { - a.doDeleteElementStart(); - targetDoc.deleteElementStart(); - } - } - - class DeleteElementEndGenerator extends RandomConstantMutationComponentGenerator { - @Override - int potential() { - return -3; - } - - @Override - ValidationResult check(ViolationCollector v) { - return a.checkDeleteElementEnd(v); - } - - @Override - void apply() { - a.doDeleteElementEnd(); - targetDoc.deleteElementEnd(); - } - } - - abstract class AttributesOnlyRandomMutationComponentGenerator - extends RandomMutationComponentGenerator { - abstract ValidationResult check(Attributes attrs, ViolationCollector v); - abstract void apply(Attributes attrs); - @Override - RandomizerMutationComponent generate(boolean valid) { - final Attributes attrs = generateRandomAttributes(valid, new AttributesChecker() { - @Override - public ValidationResult check(Attributes attrs) { - return AttributesOnlyRandomMutationComponentGenerator.this.check(attrs, null); - } - }); - - if (attrs == null) { - return null; - } - - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return AttributesOnlyRandomMutationComponentGenerator.this.check(attrs, v); - } - - @Override - public void apply() { - AttributesOnlyRandomMutationComponentGenerator.this.apply(attrs); - } - - @Override - public String toString() { - return this.getClass().getName() + " from " - + AttributesOnlyRandomMutationComponentGenerator.this.getClass().getName() - + " " + attrs; - } - }; - } - } - - class SetAttributesGenerator extends AttributesOnlyRandomMutationComponentGenerator { - @Override - int potential() { - return 0; - } - - @Override - ValidationResult check(Attributes attrs, ViolationCollector v) { - return a.checkSetAttributes(attrs, v); - } - - @Override - void apply(Attributes attrs) { - a.doSetAttributes(attrs); - targetDoc.replaceAttributes(attrs); - } - } - - class UpdateAttributesGenerator extends AttributesOnlyRandomMutationComponentGenerator { - @Override - int potential() { - return 0; - } - - @Override - ValidationResult check(Attributes attrs, ViolationCollector v) { - return a.checkUpdateAttributes(attrs, v); - } - - @Override - void apply(Attributes attrs) { - a.doUpdateAttributes(attrs); - targetDoc.updateAttributes(attrs); - } - } - - class StartAnnotationGenerator extends RandomMutationComponentGenerator { - @Override - int potential() { - return 0; - } - - @Override - RandomizerMutationComponent generate(boolean valid) { - if (!valid) { - return null; - } - if (p.getAnnotationOptions().isEmpty()) { - return null; - } - - Parameters.AnnotationOption option = randomElement(r, p.getAnnotationOptions()); - final String key = option.getKey(); - final String value = option.randomValue(r); - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return a.checkStartAnnotation(key, value, v); - } - - @Override - public void apply() { - a.doStartAnnotation(key, value); - targetDoc.startAnnotation(key, value); - } - }; - } - } - - class EndAnnotationGenerator extends RandomMutationComponentGenerator { - @Override - int potential() { - return -3; - } - - @Override - RandomizerMutationComponent generate(boolean valid) { - if (!valid) { - return null; - } - return pickRandomNonNullMappedElement(r, p.getAnnotationKeys(), - new Mapper<String, RandomizerMutationComponent>() { - @Override - public RandomizerMutationComponent map(final String key) { - switch (a.checkEndAnnotation(key, null)) { - case ILL_FORMED: - return null; - case VALID: - return new RandomizerMutationComponent() { - @Override - public ValidationResult check(ViolationCollector v) { - return a.checkEndAnnotation(key, v); - } - - @Override - public void apply() { - a.doEndAnnotation(key); - targetDoc.endAnnotation(key); - } - }; - case INVALID_DOCUMENT: - case INVALID_SCHEMA: - default: - throw new RuntimeException("unexpected validation result"); - } - } - } - ); - } - } - - final RandomProvider r; - final Parameters p; - final DocumentSchema schemaConstraints; - @SuppressWarnings("rawtypes") - NindoAutomaton a; - NindoCursor targetDoc; - final IndexedDocument<Node, Element, Text> doc; - - Generator(RandomProvider r, Parameters p, DocumentSchema s, - IndexedDocument<Node, Element, Text> doc) { - this.r = r; - this.p = p; - this.doc = doc; - this.schemaConstraints = s; - } - - final List<RandomMutationComponentGenerator> componentGenerators = - Arrays.asList(new SkipGenerator(), - new CharactersGenerator(), - new DeleteCharactersGenerator(), - new ElementStartGenerator(), - new ElementEndGenerator(), - new DeleteElementStartGenerator(), - new DeleteElementEndGenerator(), - new SetAttributesGenerator(), - new UpdateAttributesGenerator(), - new StartAnnotationGenerator(), - new EndAnnotationGenerator() - ); - - @SuppressWarnings("rawtypes") - Nindo generate() { - while (true) { - this.a = new NindoAutomaton(schemaConstraints, doc); - Nindo.Builder b = new Nindo.Builder(); - targetDoc = b; - boolean ok = generate1(); - if (ok) { - return b.build(); - } - } - } - - boolean generate1() { - int desiredNumComponents = randomIntFromRange(r, 0, p.getMaxOpeningComponents()); - for (int i = 0; i < desiredNumComponents; i++) { - RandomizerMutationComponent component = pickRandomNonNullMappedElement(r, - componentGenerators, - new Mapper<RandomMutationComponentGenerator, RandomizerMutationComponent>() { - @Override - public RandomizerMutationComponent map(RandomMutationComponentGenerator g) { - return g.generate(p.getValidity()); - } - }); - if (component == null) { - // This can happen e.g. if we have skipped to the end of the document, and valid - // may be true, and there may not be any annotation options. - break; - } - component.apply(); - } - - // Close all open components. - while (a.checkFinish(null) == ValidationResult.ILL_FORMED) { - int potential = -3 - 1; - RandomizerMutationComponent component; - do { - potential++; - final int finalPotential = potential; - component = pickRandomNonNullMappedElement(r, componentGenerators, - new Mapper<RandomMutationComponentGenerator, RandomizerMutationComponent>() { - @Override - public RandomizerMutationComponent map(RandomMutationComponentGenerator g) { - if (g.potential() >= finalPotential) { - return null; - } - return g.generate(p.getValidity()); - } - }); - } while (potential < 0 && component == null); - if (component == null) { - // This can happen e.g. if we did an deleteAntiElementStart on the - // final </p> of the blip, where there is nothing to join with. - return false; - } - component.apply(); - } - return true; - } - } - - /** - * Returns a randomly-generated document mutation based on the given document, - * parameters, and schema. - */ - public static Nindo generate(RandomProvider r, Parameters p, - DocumentSchema s, IndexedDocument<Node, Element, Text> doc) { - Nindo m = new Generator(r, p, s, doc).generate(); - ViolationCollector v = NindoValidator.validate(doc, m, s); - assert !v.isIllFormed(); - assert p.getValidity() == v.isValid(); - return m; - } - - - /** - * Stand-alone main() for quick experimentation. - */ - public static void main(String[] args) { -// IndexedDocument<Node, Element, Text> doc = -// DocProviders.POJO.parse("<body><line></line>a</body>"); -// -// Parameters p = new Parameters(); -// -// p.setMaxOpeningComponents(10); -// -// for (int i = 0; i < 200; i++) { -// System.out.println("i=" + i); -// RandomProvider r = RandomProviderImpl.ofSeed(i); -// Nindo m = generate(r, p, -// NindoValidator.DEFAULT_BLIP_SCHEMA_CONSTRAINTS, doc); -// System.out.print(m); -// } - } - -} http://git-wip-us.apache.org/repos/asf/incubator-wave/blob/d35211be/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomProviderImpl.java ---------------------------------------------------------------------- diff --git a/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomProviderImpl.java b/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomProviderImpl.java deleted file mode 100644 index d6a9c17..0000000 --- a/wave/src/main/java/org/waveprotocol/wave/model/testing/RandomProviderImpl.java +++ /dev/null @@ -1,72 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -package org.waveprotocol.wave.model.testing; - -import org.waveprotocol.wave.model.testing.RandomDocOpGenerator.RandomProvider; -import org.waveprotocol.wave.model.util.Preconditions; - -/** - * Implementation of RandomProvider for use in classes intended for use in - * GWT, which doesn't support java.util.Random. - * - * The implementation is simplistic and not well tested, so don't use it for - * any usage that depends on the quality of the generated pseudorandom numbers. - * - * The implementation is based on the recommendations in - * Knuth: The Art of Computer Programming, Volume 2, Section 3.6. - * - */ -public class RandomProviderImpl implements RandomProvider { - - public static RandomProviderImpl ofSeed(int seed) { - return new RandomProviderImpl(seed); - } - - private int next32; - - public RandomProviderImpl(int seed) { - next32 = seed; - } - - @Override - public int nextInt(int upperBound) { - Preconditions.checkArgument(upperBound > 0, "upperBound must be positive"); - - // 0x77DD9E95 is a random number from http://www.fourmilab.ch/hotbits/ - // satisfying 0x77DD9E95 % 8 == 5 - // TODO: check if this multiplier passes the spectral test and other tests in Knuth's book - next32 = (int) (0x77DD9E95L * (long) next32 + 1L); - // NOTE(2010/06/08): the casts above were necessary to work around a Gwt miscompilation - // problem, in Java a simpler expression works: next32 = 0x77DD9E95L * next32 + 1; - - // convert the signed 32 bit content into a floating point number - // between 0 (inclusive) and 1 (exclusive) - double d = (((double) next32) + 2147483648.0) / 4294967296.0; - - // truncate the multiplum of d and upperBound to get an integer - // between 0 (inclusive) and upperBound (exclusive) - return (int) (d * (double) upperBound); - } - - @Override - public boolean nextBoolean() { - return nextInt(2) != 0; - } -} http://git-wip-us.apache.org/repos/asf/incubator-wave/blob/d35211be/wave/src/main/java/org/waveprotocol/wave/model/testing/Response.java ---------------------------------------------------------------------- diff --git a/wave/src/main/java/org/waveprotocol/wave/model/testing/Response.java b/wave/src/main/java/org/waveprotocol/wave/model/testing/Response.java deleted file mode 100644 index 5efb790..0000000 --- a/wave/src/main/java/org/waveprotocol/wave/model/testing/Response.java +++ /dev/null @@ -1,107 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -package org.waveprotocol.wave.model.testing; - -import org.mockito.invocation.InvocationOnMock; -import org.mockito.stubbing.Answer; - -import java.util.Arrays; -import java.util.List; - -/** - * A simple answer for providing type-safe generic containers as return - * values to Mockito stubbing calls. - * - * Java doesn't resolve the wildcard generic here: - * <pre> - * interface Container { - * Collection<? extends Foo> getFoos(); - * } - * - * public void testFooContainer() { - * Container c = mock(Container.class); - * when(c.getFoos()).thenReturn(Arrays.asList(a, b)); - * } - * </pre> - * - * Instead, try: - * <pre> - * public void testFooContainer() { - * Container c = mock(Container.class); - * when(c.getFoos()).thenAnswer(Response.of(Arrays.asList(a, b))); - * } - * </pre> - * or - * <pre> - * public void testFooContainer() { - * Container c = mock(Container.class); - * when(c.getFoos()).thenAnswer(Response.ofList(a, b)); - * } - * </pre> - * - * Note that {@code Mockito.doReturn()} does work, but is unnatural. - * <pre> - * public void testFooContainer() { - * Container c = mock(Container.class); - * doReturn(Arrays.asList(a, b)).when(c.getFoos()); - * } - * </pre> - * - * @author [email protected] (Alex North) - */ -public final class Response { - /** - * Creates a response which returns a value. - * - * @param response the value to return - */ - public static <T> ResponseAnswer<T> of(T response) { - return new ResponseAnswer<T>(response); - } - - /** - * Creates a response which returns a list of values. - */ - @SuppressWarnings("unchecked") - public static <T> ResponseAnswer<List<T>> ofList(T... responses) { - return new ResponseAnswer<List<T>>(Arrays.asList(responses)); - } - - /** - * An answer which simply returns a response value. - * - * @param <T> type of the response - */ - public static final class ResponseAnswer<T> implements Answer<T> { - private final T response; - - ResponseAnswer(T response) { - this.response = response; - } - - @Override - public T answer(InvocationOnMock invocation) throws Throwable { - return response; - } - } - - private Response() { - } -} http://git-wip-us.apache.org/repos/asf/incubator-wave/blob/d35211be/wave/src/main/java/org/waveprotocol/wave/model/testing/TestOperations.java ---------------------------------------------------------------------- diff --git a/wave/src/main/java/org/waveprotocol/wave/model/testing/TestOperations.java b/wave/src/main/java/org/waveprotocol/wave/model/testing/TestOperations.java deleted file mode 100644 index 8e2bf29..0000000 --- a/wave/src/main/java/org/waveprotocol/wave/model/testing/TestOperations.java +++ /dev/null @@ -1,87 +0,0 @@ -/** - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ - -package org.waveprotocol.wave.model.testing; - -import org.waveprotocol.wave.model.document.operation.Attributes; -import org.waveprotocol.wave.model.document.operation.DocOp; -import org.waveprotocol.wave.model.document.operation.impl.AnnotationBoundaryMapImpl; -import org.waveprotocol.wave.model.document.operation.impl.AttributesImpl; -import org.waveprotocol.wave.model.document.operation.impl.AttributesUpdateImpl; -import org.waveprotocol.wave.model.document.operation.impl.DocOpBuffer; - -public class TestOperations { - - // The test case for the message-based implementation should also use this. - public static DocOp getBasicTestOp() { - DocOpBuffer b = new DocOpBuffer(); - - // The operation starts with characters/deleteCharacters of various lengths - // and case, mixed with some retains and nested element start/end with - // different mixes of attributes. - b.characters("hello"); - b.characters("z"); - b.retain(1); - b.deleteCharacters("ab"); - b.characters("world"); - b.retain(2); - b.deleteCharacters("cd"); - b.elementStart("a", Attributes.EMPTY_MAP); - b.characters("hEllo"); - b.elementStart("b", new AttributesImpl("a", "1")); - b.characters("world"); - b.elementStart("B", new AttributesImpl("A", "1", "b", "abc12")); - b.elementEnd(); - // A non-ASCII Unicode character. - b.characters("\u2603"); - b.elementEnd(); - b.elementEnd(); - b.deleteElementStart("a", new AttributesImpl("a", "2", "c", "")); - b.deleteCharacters("asdf"); - b.deleteElementEnd(); - - // Now some replaceAttributes with different size and case. - b.replaceAttributes(new AttributesImpl("a", "b"), new AttributesImpl("b", "c", "c", "d")); - b.replaceAttributes(Attributes.EMPTY_MAP, new AttributesImpl("Aa", "aA")); - b.replaceAttributes(new AttributesImpl("B", "A"), new AttributesImpl()); - // Try both a fresh empty AttributesImpl() instance and the preallocated - // EMPTY_MAP. - b.replaceAttributes(new AttributesImpl(), Attributes.EMPTY_MAP); - // Now we add similar cases for annotation boundaries. Since consecutive annotation - // boundaries would make the operation ill-formed, we interleave them with further - // updateAttributes tests. - b.annotationBoundary(AnnotationBoundaryMapImpl.builder().build()); - b.updateAttributes(new AttributesUpdateImpl()); - b.annotationBoundary(AnnotationBoundaryMapImpl.builder() - .updateValues("b", "XZ", "yz", "f-", null, null, - "g-", "a", null, "k-", "b", "", "r", "", "2") - .build()); - b.updateAttributes(new AttributesUpdateImpl("a", null, "1")); - b.annotationBoundary(AnnotationBoundaryMapImpl.builder() - .initializationEnd("b", "g-", "k-", "r") - .updateValues("e", "166", null, "f-", null, null) - .build()); - b.updateAttributes(new AttributesUpdateImpl("P", null, "", ":wq", "ZZ", null)); - b.annotationBoundary(AnnotationBoundaryMapImpl.builder() - .initializationEnd("e", "f-") - .build()); - - return b.finish(); - } -}
