From e78e3ac11870926332f47e6c3522ad819c3917b8 Mon Sep 17 00:00:00 2001 From: bjculkin Date: Mon, 20 Mar 2017 16:19:20 -0400 Subject: Move delimiter stuff to a new package --- .../bjc/utils/parserutils/DelimiterException.java | 16 - .../java/bjc/utils/parserutils/DelimiterGroup.java | 485 --------------------- .../utils/parserutils/SequenceCharacteristics.java | 101 ----- .../bjc/utils/parserutils/SequenceDelimiter.java | 304 ------------- .../bjc/utils/parserutils/StringDelimiter.java | 31 -- .../parserutils/delims/DelimiterException.java | 16 + .../utils/parserutils/delims/DelimiterGroup.java | 485 +++++++++++++++++++++ .../delims/SequenceCharacteristics.java | 101 +++++ .../parserutils/delims/SequenceDelimiter.java | 304 +++++++++++++ .../utils/parserutils/delims/StringDelimiter.java | 31 ++ 10 files changed, 937 insertions(+), 937 deletions(-) delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterException.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterGroup.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceCharacteristics.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceDelimiter.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/StringDelimiter.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterException.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterGroup.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceCharacteristics.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceDelimiter.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/StringDelimiter.java (limited to 'BJC-Utils2/src/main/java/bjc/utils') diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterException.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterException.java deleted file mode 100644 index 667e2fe..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterException.java +++ /dev/null @@ -1,16 +0,0 @@ -package bjc.utils.parserutils; - -/** - * The superclass for exceptions thrown during sequence delimitation. - */ -public class DelimiterException extends RuntimeException { - /** - * Create a new generic delimiter exception. - * - * @param res - * The reason for this exception. - */ - public DelimiterException(String res) { - super(res); - } -} \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterGroup.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterGroup.java deleted file mode 100644 index 1d13565..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/parserutils/DelimiterGroup.java +++ /dev/null @@ -1,485 +0,0 @@ -package bjc.utils.parserutils; - -import bjc.utils.data.IPair; -import bjc.utils.data.ITree; -import bjc.utils.data.Pair; -import bjc.utils.data.Tree; -import bjc.utils.funcdata.FunctionalList; -import bjc.utils.funcdata.IList; - -import java.util.Arrays; -import java.util.Deque; -import java.util.HashMap; -import java.util.HashSet; -import java.util.LinkedList; -import java.util.List; -import java.util.Map; -import java.util.Map.Entry; -import java.util.Set; -import java.util.function.BiPredicate; -import java.util.function.Function; - -/** - * Represents a possible delimiter group to match. - * - * @author EVE - * - * @param - * The type of items in the sequence. - */ -public class DelimiterGroup { - /** - * Represents an instance of a delimiter group. - * - * @author EVE - * - */ - public class OpenGroup { - private Deque> contents; - - private IList> currentGroup; - - private T opener; - - private T[] params; - - /** - * Create a new instance of a delimiter group. - * - * @param open - * The item that opened this group. - * - * @param parms - * Any parameters from the opener. - */ - public OpenGroup(T open, T[] parms) { - opener = open; - params = parms; - - contents = new LinkedList<>(); - - currentGroup = new FunctionalList<>(); - } - - /** - * Add an item to this group instance. - * - * @param itm - * The item to add to this group instance. - */ - public void addItem(ITree itm) { - currentGroup.add(itm); - } - - /** - * Mark a subgroup. - * - * @param marker - * The item that indicated this subgroup. - * - * @param chars - * The characteristics for building the tree. - */ - public void markSubgroup(T marker, SequenceCharacteristics chars) { - ITree subgroupContents = new Tree<>(chars.contents); - for(ITree itm : currentGroup) { - subgroupContents.addChild(itm); - } - - while(!contents.isEmpty()) { - ITree possibleSubordinate = contents.peek(); - - if(possibleSubordinate.getHead().equals(chars.subgroup)) { - T otherMarker = possibleSubordinate.getChild(1).getHead(); - - if(subgroups.get(marker) > subgroups.get(otherMarker)) { - subgroupContents.prependChild(contents.pop()); - } else { - break; - } - } else { - subgroupContents.prependChild(contents.pop()); - } - } - - Tree subgroup = new Tree<>(chars.subgroup, subgroupContents, new Tree<>(marker)); - - //System.out.println("\tTRACE: generated subgroup\n" + subgroup + "\n\n"); - contents.push(subgroup); - - currentGroup = new FunctionalList<>(); - } - - /** - * Convert this group into a tree. - * - * @param closer - * The item that closed this group. - * - * @param chars - * The characteristics for building the tree. - * - * @return This group as a tree. - */ - public ITree toTree(T closer, SequenceCharacteristics chars) { - if(impliedSubgroups.containsKey(closer)) { - markSubgroup(impliedSubgroups.get(closer), chars); - } - - ITree res = new Tree<>(chars.contents); - - if(contents.isEmpty()) { - currentGroup.forEach(res::addChild); - } else { - while(!contents.isEmpty()) { - res.prependChild(contents.poll()); - } - - currentGroup.forEach(res::addChild); - } - - return new Tree<>(groupName, new Tree<>(opener), res, new Tree<>(closer)); - } - - @Override - public String toString() { - StringBuilder builder = new StringBuilder(); - - builder.append("OpenGroup [contents="); - builder.append(contents); - builder.append(", currentGroup="); - builder.append(currentGroup); - builder.append(", opener="); - builder.append(opener); - builder.append("]"); - - return builder.toString(); - } - - /** - * Check if a group is excluded at the top level of this group. - * - * @param groupName - * The group to check. - * - * @return Whether or not the provided group is excluded. - */ - public boolean excludes(T groupName) { - return topLevelExclusions.contains(groupName); - } - - /** - * Check if the provided delimiter would close this group. - * - * @param del - * The string to check as a closing delimiter. - * - * @return Whether or not the provided delimiter closes this - * group. - */ - public boolean isClosing(T del) { - if(closingDelimiters.contains(del)) { - return true; - } - - for(BiPredicate pred : predClosers) { - if(pred.test(del, params)) { - return true; - } - } - - return closingDelimiters.contains(del); - } - - /** - * Get the name of the group this is an instance of. - * - * @return The name of the group this is an instance of. - */ - public T getName() { - return groupName; - } - - /** - * Get the groups that aren't allowed at all in this group. - * - * @return The groups that aren't allowed at all in this group. - */ - public Set getNestingExclusions() { - return groupExclusions; - } - - /** - * Checks if a given token marks a subgroup. - * - * @param tok - * The token to check. - * - * @return Whether or not the token marks a subgroup. - */ - public boolean marksSubgroup(T tok) { - return subgroups.containsKey(tok); - } - - /** - * Checks if a given token opens a group. - * - * @param marker - * The token to check. - * - * @return The name of the group T opens, or null if it doesn't - * open one. - */ - public IPair doesOpen(T marker) { - if(openDelimiters.containsKey(marker)) { - return new Pair<>(openDelimiters.get(marker), null); - } - - for(Function> pred : predOpeners) { - IPair par = pred.apply(marker); - - if(par.getLeft() != null) { - return par; - } - } - - return new Pair<>(null, null); - } - } - - /** - * The name of this delimiter group. - */ - public final T groupName; - - /* - * The delimiters that open groups at the top level of this group. - */ - private Map openDelimiters; - - /* - * The delimiters that close this group. - */ - private Set closingDelimiters; - - /* - * The groups that can't occur in the top level of this group. - */ - private Set topLevelExclusions; - - /* - * The groups that can't occur anywhere inside this group. - */ - private Set groupExclusions; - - /* - * Mapping from sub-group delimiters, to any sub-groups enclosed in - * them. - */ - private Map subgroups; - - /* - * Subgroups implied by a particular closing delimiter - */ - private Map impliedSubgroups; - - /* - * Allows more complex openings - */ - private List>> predOpeners; - - /* - * Allow more complex closings - */ - private List> predClosers; - - /** - * Create a new empty delimiter group. - * - * @param name - * The name of the delimiter group - */ - public DelimiterGroup(T name) { - if(name == null) throw new NullPointerException("Group name must not be null"); - - groupName = name; - - openDelimiters = new HashMap<>(); - closingDelimiters = new HashSet<>(); - - topLevelExclusions = new HashSet<>(); - groupExclusions = new HashSet<>(); - - subgroups = new HashMap<>(); - impliedSubgroups = new HashMap<>(); - - predOpeners = new LinkedList<>(); - predClosers = new LinkedList<>(); - } - - /** - * Adds one or more delimiters that close this group. - * - * @param closers - * Delimiters that close this group. - */ - @SafeVarargs - public final void addClosing(T... closers) { - List closerList = Arrays.asList(closers); - - for(T closer : closerList) { - if(closer == null) { - throw new NullPointerException("Closing delimiter must not be null"); - } else if(closer.equals("")) { - /* - * We can do this because equals works on - * arbitrary objects, not just those of the same - * type. - */ - throw new IllegalArgumentException("Empty string is not a valid exclusion"); - } else { - closingDelimiters.add(closer); - } - } - } - - /** - * Adds one or more groups that cannot occur in the top level of this - * group. - * - * @param exclusions - * The groups forbidden in the top level of this group. - */ - @SafeVarargs - public final void addTopLevelForbid(T... exclusions) { - for(T exclusion : exclusions) { - if(exclusion == null) { - throw new NullPointerException("Exclusion must not be null"); - } else if(exclusion.equals("")) { - /* - * We can do this because equals works on - * arbitrary objects, not just those of the same - * type. - */ - throw new IllegalArgumentException("Empty string is not a valid exclusion"); - } else { - topLevelExclusions.add(exclusion); - } - } - } - - /** - * Adds one or more groups that cannot occur at all in this group. - * - * @param exclusions - * The groups forbidden inside this group. - */ - @SafeVarargs - public final void addGroupForbid(T... exclusions) { - for(T exclusion : exclusions) { - if(exclusion == null) { - throw new NullPointerException("Exclusion must not be null"); - } else if(exclusion.equals("")) { - /* - * We can do this because equals works on - * arbitrary objects, not just those of the same - * type. - */ - throw new IllegalArgumentException("Empty string is not a valid exclusion"); - } else { - groupExclusions.add(exclusion); - } - } - } - - /** - * Adds sub-group markers to this group. - * - * @param subgroup - * The token to mark a sub-group. - * - * @param priority - * The priority of this sub-group. - * - * @param contained - * Any sub-groups to enclose in this group. - */ - public void addSubgroup(T subgroup, int priority) { - if(subgroup == null) { - throw new NullPointerException("Subgroup marker must not be null"); - } - - subgroups.put(subgroup, priority); - } - - public void addOpener(T opener, T group) { - openDelimiters.put(opener, group); - } - - public void implySubgroup(T closer, T subgroup) { - impliedSubgroups.put(closer, subgroup); - } - - @Override - public String toString() { - StringBuilder builder = new StringBuilder(); - - builder.append("("); - - builder.append("groupName=["); - builder.append(groupName); - builder.append("], "); - - builder.append("closingDelimiters=["); - for(T closer : closingDelimiters) { - builder.append(closer + ","); - } - builder.deleteCharAt(builder.length() - 1); - builder.append("]"); - - if(topLevelExclusions != null && !topLevelExclusions.isEmpty()) { - builder.append(", "); - builder.append("topLevelExclusions=["); - for(T exclusion : topLevelExclusions) { - builder.append(exclusion + ","); - } - builder.deleteCharAt(builder.length() - 1); - builder.append("]"); - } - - if(groupExclusions != null && !groupExclusions.isEmpty()) { - builder.append(", "); - builder.append("groupExclusions=["); - for(T exclusion : groupExclusions) { - builder.append(exclusion + ","); - } - builder.deleteCharAt(builder.length() - 1); - builder.append("]"); - } - - builder.append(" )"); - - return builder.toString(); - } - - /** - * Open an instance of this group. - * - * @param opener - * The item that opened this group. - * - * @return An opened instance of this group. - */ - public OpenGroup open(T opener, T[] parms) { - return new OpenGroup(opener, parms); - } - - public void addPredOpener(Function> pred) { - predOpeners.add(pred); - } - - public void addPredCloser(BiPredicate pred) { - predClosers.add(pred); - } - -} \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceCharacteristics.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceCharacteristics.java deleted file mode 100644 index c28e42b..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceCharacteristics.java +++ /dev/null @@ -1,101 +0,0 @@ -package bjc.utils.parserutils; - -/** - * Marks the parameters for building a sequence tree. - * - * @author EVE - * - * @param - * The type of item in the tree. - */ -public class SequenceCharacteristics { - /** - * The item to mark the root of the tree. - */ - public final T root; - - /** - * The item to mark the contents of a group/subgroup. - */ - - public final T contents; - - /** - * The item to mark a subgroup. - */ - public final T subgroup; - - /** - * Create a new set of parameters for building a tree. - * - * @param root - * The root marker. - * @param contents - * The group/subgroup contents marker. - * @param subgroup - * The subgroup marker. - */ - public SequenceCharacteristics(T root, T contents, T subgroup) { - this.root = root; - this.contents = contents; - this.subgroup = subgroup; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#hashCode() - */ - @Override - public int hashCode() { - final int prime = 31; - int result = 1; - result = prime * result + ((contents == null) ? 0 : contents.hashCode()); - result = prime * result + ((root == null) ? 0 : root.hashCode()); - result = prime * result + ((subgroup == null) ? 0 : subgroup.hashCode()); - return result; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#equals(java.lang.Object) - */ - @Override - public boolean equals(Object obj) { - if(this == obj) return true; - if(obj == null) return false; - if(!(obj instanceof SequenceCharacteristics)) return false; - - SequenceCharacteristics other = (SequenceCharacteristics) obj; - - if(contents == null) { - if(other.contents != null) return false; - } else if(!contents.equals(other.contents)) return false; - - if(root == null) { - if(other.root != null) return false; - } else if(!root.equals(other.root)) return false; - - if(subgroup == null) { - if(other.subgroup != null) return false; - } else if(!subgroup.equals(other.subgroup)) return false; - - return true; - } - - @Override - public String toString() { - StringBuilder builder = new StringBuilder(); - - builder.append("SequenceCharacteristics [root="); - builder.append(root == null ? "(null)" : root); - builder.append(", contents="); - builder.append(contents == null ? "(null)" : contents); - builder.append(", subgroup="); - builder.append(subgroup == null ? "(null)" : subgroup); - builder.append("]"); - - return builder.toString(); - } -} \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceDelimiter.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceDelimiter.java deleted file mode 100644 index 771933a..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/parserutils/SequenceDelimiter.java +++ /dev/null @@ -1,304 +0,0 @@ -package bjc.utils.parserutils; - -import bjc.utils.data.IPair; -import bjc.utils.data.ITree; -import bjc.utils.data.Tree; -import bjc.utils.esodata.PushdownMap; -import bjc.utils.esodata.SimpleStack; -import bjc.utils.esodata.Stack; -import bjc.utils.funcdata.IMap; -import bjc.utils.funcutils.StringUtils; - -import com.google.common.collect.HashMultiset; -import com.google.common.collect.Multiset; - -import java.util.HashMap; -import java.util.Map; - -/** - * Convert linear sequences into trees that represent group structure. - * - * @author EVE - * - * @param - * The type of items in the sequence. - */ -public class SequenceDelimiter { - /* - * Mapping from opening delimiters to the names of the groups they open - */ - - /* - * Mapping from group names to actual groups. - */ - private Map> groups; - - private DelimiterGroup initialGroup; - - /** - * Create a new sequence delimiter. - */ - public SequenceDelimiter() { - groups = new HashMap<>(); - } - - /** - * Convert a linear sequence into a tree that matches the delimiter - * structure. - * - * Essentially, creates a parse tree of the expression against the - * following grammar while obeying the defined group rules. - * - * 
-	 *              -> ( |  | )*
-	 *          ->  
-	 *             ->   
-	 *         
-	 *              -> STRING
-	 *              -> STRING
-	 *             -> STRING
-	 *            -> STRING
-	 *
- * - * @param chars - * The parameters on how to mark certain portions of the - * tree. - * @param seq - * The sequence to delimit. - * - * @return The sequence as a tree that matches its group structure. Each - * node in the tree is either a data node, a subgroup node, or a - * group node. - * - * A data node is a leaf node whose data is the string it - * represents. - * - * A subgroup node is a node with two children, and the name of - * the sub-group as its label. The first child is the contents - * of the sub-group, and the second is the marker that started - * the subgroup. The marker is a leaf node labeled with its - * contents, and the contents contains a recursive tree. - * - * A group node is a node with three children, and the name of - * the group as its label. The first child is the opening - * delimiter, the second is the group contents, and the third is - * the closing delimiter. The delimiters are leaf nodes labeled - * with their contents, while the group node contains a - * recursive tree. - * - * @throws DelimiterException - * Thrown if something went wrong during sequence - * delimitation. - * - */ - public ITree delimitSequence(SequenceCharacteristics chars, @SuppressWarnings("unchecked") T... seq) - throws DelimiterException { - if(initialGroup == null) { - throw new NullPointerException("Initial group must be specified."); - } - - /* - * The stack of opened and not yet closed groups. - */ - Stack.OpenGroup> groupStack = new SimpleStack<>(); - - /* - * Open initial group. - */ - groupStack.push(initialGroup.open(chars.root, null)); - - /* - * Groups that aren't allowed to be opened at the moment. - */ - Multiset forbiddenDelimiters = HashMultiset.create(); - - /* - * Map of who forbid what for debugging purposes. - */ - IMap whoForbid = new PushdownMap<>(); - - for(int i = 0; i < seq.length; i++) { - T tok = seq[i]; - - IPair possibleOpenPar = groupStack.top().doesOpen(tok); - T possibleOpen = possibleOpenPar.getLeft(); - - /* - * If we have an opening delimiter, handle it. - */ - if(possibleOpen != null) { - DelimiterGroup group = groups.get(possibleOpen); - - /* - * Error on groups that can't open in this - * context. - * - * This means groups that can't occur at the - * top-level of this group, as well as nested - * exclusions from all enclosing groups. - */ - if(isForbidden(groupStack, forbiddenDelimiters, possibleOpen)) { - StringBuilder msgBuilder = new StringBuilder(); - - T forbiddenBy; - - if(whoForbid.containsKey(tok)) { - forbiddenBy = whoForbid.get(tok); - } else { - forbiddenBy = groupStack.top().getName(); - } - - String ctxList = StringUtils.toEnglishList(groupStack.toArray(), "then"); - - msgBuilder.append("Group '"); - msgBuilder.append(group); - msgBuilder.append("' can't be opened in this context."); - msgBuilder.append(" (forbidden by '"); - msgBuilder.append(forbiddenBy); - msgBuilder.append("')\nContext stack: "); - msgBuilder.append(ctxList); - - throw new DelimiterException(msgBuilder.toString()); - } - - /* - * Add an open group. - */ - DelimiterGroup.OpenGroup open = group.open(tok, possibleOpenPar.getRight()); - groupStack.push(open); - - /* - * Add the nested exclusions from this group - */ - for(T exclusion : open.getNestingExclusions()) { - forbiddenDelimiters.add(exclusion); - - whoForbid.put(exclusion, possibleOpen); - } - } else if(!groupStack.empty() && groupStack.top().isClosing(tok)) { - /* - * Close the group. - */ - DelimiterGroup.OpenGroup closed = groupStack.pop(); - - groupStack.top().addItem(closed.toTree(tok, chars)); - - /* - * Remove nested exclusions from this group. - */ - for(T excludedGroup : closed.getNestingExclusions()) { - forbiddenDelimiters.remove(excludedGroup); - - whoForbid.remove(excludedGroup); - } - } else if(!groupStack.empty() && groupStack.top().marksSubgroup(tok)) { - groupStack.top().markSubgroup(tok, chars); - } else { - groupStack.top().addItem(new Tree<>(tok)); - } - } - - /* - * Error if not all groups were closed. - */ - if(groupStack.size() > 1) { - DelimiterGroup.OpenGroup group = groupStack.top(); - - StringBuilder msgBuilder = new StringBuilder(); - - String closingDelims = StringUtils.toEnglishList(group.getNestingExclusions().toArray(), false); - - String ctxList = StringUtils.toEnglishList(groupStack.toArray(), "then"); - - msgBuilder.append("Unclosed group '"); - msgBuilder.append(group.getName()); - msgBuilder.append("'. Expected one of "); - msgBuilder.append(closingDelims); - msgBuilder.append(" to close it\nOpen groups: "); - msgBuilder.append(ctxList); - - throw new DelimiterException(msgBuilder.toString()); - } - - return groupStack.pop().toTree(chars.root, chars); - } - - private boolean isForbidden(Stack.OpenGroup> groupStack, Multiset forbiddenDelimiters, - T groupName) { - boolean localForbid; - if(groupStack.empty()) - localForbid = false; - else - localForbid = groupStack.top().excludes(groupName); - - return localForbid || forbiddenDelimiters.contains(groupName); - } - - /** - * Add a delimiter group. - * - * @param group - * The delimiter group. - */ - public void addGroup(DelimiterGroup group) { - if(group == null) { - throw new NullPointerException("Group must not be null"); - } - - groups.put(group.groupName, group); - } - - /** - * Creates and adds a delimiter group using the provided settings. - * - * @param openers - * The tokens that open this group - * @param groupName - * The name of the group - * @param closers - * The tokens that close this group - */ - public void addGroup(T[] openers, T groupName, @SuppressWarnings("unchecked") T... closers) { - DelimiterGroup group = new DelimiterGroup<>(groupName); - - group.addClosing(closers); - - addGroup(group); - - for(T open : openers) { - group.addOpener(open, groupName); - } - } - - @Override - public String toString() { - StringBuilder builder = new StringBuilder(); - - builder.append("SequenceDelimiter ["); - - if(groups != null) { - builder.append("groups="); - builder.append(groups); - builder.append(","); - } - - if(initialGroup != null) { - builder.append("initialGroup="); - builder.append(initialGroup); - } - - builder.append("]"); - - return builder.toString(); - } - - /** - * Set the initial group of this delimiter. - * - * @param initialGroup - * The initial group of this delimiter. - */ - public void setInitialGroup(DelimiterGroup initialGroup) { - this.initialGroup = initialGroup; - } -} diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/StringDelimiter.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/StringDelimiter.java deleted file mode 100644 index 26d0c59..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/parserutils/StringDelimiter.java +++ /dev/null @@ -1,31 +0,0 @@ -package bjc.utils.parserutils; - -import bjc.utils.data.ITree; - -/** - * A sequence delimiter specialized for strings. - * - * @author EVE - * - */ -public class StringDelimiter extends SequenceDelimiter { - - /** - * Override of - * {@link SequenceDelimiter#delimitSequence(Object, Object, Object...)} - * for ease of use for strings. - * - * @param seq - * The sequence to delimit. - * - * @return The sequence as a tree. - * - * @throws DelimiterException - * if something went wrong with delimiting the sequence. - * - * @see SequenceDelimiter - */ - public ITree delimitSequence(String... seq) throws DelimiterException { - return super.delimitSequence(new SequenceCharacteristics("root", "contents", "subgroup"), seq); - } -} diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterException.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterException.java new file mode 100644 index 0000000..3aba434 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterException.java @@ -0,0 +1,16 @@ +package bjc.utils.parserutils.delims; + +/** + * The superclass for exceptions thrown during sequence delimitation. + */ +public class DelimiterException extends RuntimeException { + /** + * Create a new generic delimiter exception. + * + * @param res + * The reason for this exception. + */ + public DelimiterException(String res) { + super(res); + } +} \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterGroup.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterGroup.java new file mode 100644 index 0000000..23a3b9f --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/DelimiterGroup.java @@ -0,0 +1,485 @@ +package bjc.utils.parserutils.delims; + +import bjc.utils.data.IPair; +import bjc.utils.data.ITree; +import bjc.utils.data.Pair; +import bjc.utils.data.Tree; +import bjc.utils.funcdata.FunctionalList; +import bjc.utils.funcdata.IList; + +import java.util.Arrays; +import java.util.Deque; +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; +import java.util.function.BiPredicate; +import java.util.function.Function; + +/** + * Represents a possible delimiter group to match. + * + * @author EVE + * + * @param + * The type of items in the sequence. + */ +public class DelimiterGroup { + /** + * Represents an instance of a delimiter group. + * + * @author EVE + * + */ + public class OpenGroup { + private Deque> contents; + + private IList> currentGroup; + + private T opener; + + private T[] params; + + /** + * Create a new instance of a delimiter group. + * + * @param open + * The item that opened this group. + * + * @param parms + * Any parameters from the opener. + */ + public OpenGroup(T open, T[] parms) { + opener = open; + params = parms; + + contents = new LinkedList<>(); + + currentGroup = new FunctionalList<>(); + } + + /** + * Add an item to this group instance. + * + * @param itm + * The item to add to this group instance. + */ + public void addItem(ITree itm) { + currentGroup.add(itm); + } + + /** + * Mark a subgroup. + * + * @param marker + * The item that indicated this subgroup. + * + * @param chars + * The characteristics for building the tree. + */ + public void markSubgroup(T marker, SequenceCharacteristics chars) { + ITree subgroupContents = new Tree<>(chars.contents); + for(ITree itm : currentGroup) { + subgroupContents.addChild(itm); + } + + while(!contents.isEmpty()) { + ITree possibleSubordinate = contents.peek(); + + if(possibleSubordinate.getHead().equals(chars.subgroup)) { + T otherMarker = possibleSubordinate.getChild(1).getHead(); + + if(subgroups.get(marker) > subgroups.get(otherMarker)) { + subgroupContents.prependChild(contents.pop()); + } else { + break; + } + } else { + subgroupContents.prependChild(contents.pop()); + } + } + + Tree subgroup = new Tree<>(chars.subgroup, subgroupContents, new Tree<>(marker)); + + //System.out.println("\tTRACE: generated subgroup\n" + subgroup + "\n\n"); + contents.push(subgroup); + + currentGroup = new FunctionalList<>(); + } + + /** + * Convert this group into a tree. + * + * @param closer + * The item that closed this group. + * + * @param chars + * The characteristics for building the tree. + * + * @return This group as a tree. + */ + public ITree toTree(T closer, SequenceCharacteristics chars) { + if(impliedSubgroups.containsKey(closer)) { + markSubgroup(impliedSubgroups.get(closer), chars); + } + + ITree res = new Tree<>(chars.contents); + + if(contents.isEmpty()) { + currentGroup.forEach(res::addChild); + } else { + while(!contents.isEmpty()) { + res.prependChild(contents.poll()); + } + + currentGroup.forEach(res::addChild); + } + + return new Tree<>(groupName, new Tree<>(opener), res, new Tree<>(closer)); + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + + builder.append("OpenGroup [contents="); + builder.append(contents); + builder.append(", currentGroup="); + builder.append(currentGroup); + builder.append(", opener="); + builder.append(opener); + builder.append("]"); + + return builder.toString(); + } + + /** + * Check if a group is excluded at the top level of this group. + * + * @param groupName + * The group to check. + * + * @return Whether or not the provided group is excluded. + */ + public boolean excludes(T groupName) { + return topLevelExclusions.contains(groupName); + } + + /** + * Check if the provided delimiter would close this group. + * + * @param del + * The string to check as a closing delimiter. + * + * @return Whether or not the provided delimiter closes this + * group. + */ + public boolean isClosing(T del) { + if(closingDelimiters.contains(del)) { + return true; + } + + for(BiPredicate pred : predClosers) { + if(pred.test(del, params)) { + return true; + } + } + + return closingDelimiters.contains(del); + } + + /** + * Get the name of the group this is an instance of. + * + * @return The name of the group this is an instance of. + */ + public T getName() { + return groupName; + } + + /** + * Get the groups that aren't allowed at all in this group. + * + * @return The groups that aren't allowed at all in this group. + */ + public Set getNestingExclusions() { + return groupExclusions; + } + + /** + * Checks if a given token marks a subgroup. + * + * @param tok + * The token to check. + * + * @return Whether or not the token marks a subgroup. + */ + public boolean marksSubgroup(T tok) { + return subgroups.containsKey(tok); + } + + /** + * Checks if a given token opens a group. + * + * @param marker + * The token to check. + * + * @return The name of the group T opens, or null if it doesn't + * open one. + */ + public IPair doesOpen(T marker) { + if(openDelimiters.containsKey(marker)) { + return new Pair<>(openDelimiters.get(marker), null); + } + + for(Function> pred : predOpeners) { + IPair par = pred.apply(marker); + + if(par.getLeft() != null) { + return par; + } + } + + return new Pair<>(null, null); + } + } + + /** + * The name of this delimiter group. + */ + public final T groupName; + + /* + * The delimiters that open groups at the top level of this group. + */ + private Map openDelimiters; + + /* + * The delimiters that close this group. + */ + private Set closingDelimiters; + + /* + * The groups that can't occur in the top level of this group. + */ + private Set topLevelExclusions; + + /* + * The groups that can't occur anywhere inside this group. + */ + private Set groupExclusions; + + /* + * Mapping from sub-group delimiters, to any sub-groups enclosed in + * them. + */ + private Map subgroups; + + /* + * Subgroups implied by a particular closing delimiter + */ + private Map impliedSubgroups; + + /* + * Allows more complex openings + */ + private List>> predOpeners; + + /* + * Allow more complex closings + */ + private List> predClosers; + + /** + * Create a new empty delimiter group. + * + * @param name + * The name of the delimiter group + */ + public DelimiterGroup(T name) { + if(name == null) throw new NullPointerException("Group name must not be null"); + + groupName = name; + + openDelimiters = new HashMap<>(); + closingDelimiters = new HashSet<>(); + + topLevelExclusions = new HashSet<>(); + groupExclusions = new HashSet<>(); + + subgroups = new HashMap<>(); + impliedSubgroups = new HashMap<>(); + + predOpeners = new LinkedList<>(); + predClosers = new LinkedList<>(); + } + + /** + * Adds one or more delimiters that close this group. + * + * @param closers + * Delimiters that close this group. + */ + @SafeVarargs + public final void addClosing(T... closers) { + List closerList = Arrays.asList(closers); + + for(T closer : closerList) { + if(closer == null) { + throw new NullPointerException("Closing delimiter must not be null"); + } else if(closer.equals("")) { + /* + * We can do this because equals works on + * arbitrary objects, not just those of the same + * type. + */ + throw new IllegalArgumentException("Empty string is not a valid exclusion"); + } else { + closingDelimiters.add(closer); + } + } + } + + /** + * Adds one or more groups that cannot occur in the top level of this + * group. + * + * @param exclusions + * The groups forbidden in the top level of this group. + */ + @SafeVarargs + public final void addTopLevelForbid(T... exclusions) { + for(T exclusion : exclusions) { + if(exclusion == null) { + throw new NullPointerException("Exclusion must not be null"); + } else if(exclusion.equals("")) { + /* + * We can do this because equals works on + * arbitrary objects, not just those of the same + * type. + */ + throw new IllegalArgumentException("Empty string is not a valid exclusion"); + } else { + topLevelExclusions.add(exclusion); + } + } + } + + /** + * Adds one or more groups that cannot occur at all in this group. + * + * @param exclusions + * The groups forbidden inside this group. + */ + @SafeVarargs + public final void addGroupForbid(T... exclusions) { + for(T exclusion : exclusions) { + if(exclusion == null) { + throw new NullPointerException("Exclusion must not be null"); + } else if(exclusion.equals("")) { + /* + * We can do this because equals works on + * arbitrary objects, not just those of the same + * type. + */ + throw new IllegalArgumentException("Empty string is not a valid exclusion"); + } else { + groupExclusions.add(exclusion); + } + } + } + + /** + * Adds sub-group markers to this group. + * + * @param subgroup + * The token to mark a sub-group. + * + * @param priority + * The priority of this sub-group. + * + * @param contained + * Any sub-groups to enclose in this group. + */ + public void addSubgroup(T subgroup, int priority) { + if(subgroup == null) { + throw new NullPointerException("Subgroup marker must not be null"); + } + + subgroups.put(subgroup, priority); + } + + public void addOpener(T opener, T group) { + openDelimiters.put(opener, group); + } + + public void implySubgroup(T closer, T subgroup) { + impliedSubgroups.put(closer, subgroup); + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + + builder.append("("); + + builder.append("groupName=["); + builder.append(groupName); + builder.append("], "); + + builder.append("closingDelimiters=["); + for(T closer : closingDelimiters) { + builder.append(closer + ","); + } + builder.deleteCharAt(builder.length() - 1); + builder.append("]"); + + if(topLevelExclusions != null && !topLevelExclusions.isEmpty()) { + builder.append(", "); + builder.append("topLevelExclusions=["); + for(T exclusion : topLevelExclusions) { + builder.append(exclusion + ","); + } + builder.deleteCharAt(builder.length() - 1); + builder.append("]"); + } + + if(groupExclusions != null && !groupExclusions.isEmpty()) { + builder.append(", "); + builder.append("groupExclusions=["); + for(T exclusion : groupExclusions) { + builder.append(exclusion + ","); + } + builder.deleteCharAt(builder.length() - 1); + builder.append("]"); + } + + builder.append(" )"); + + return builder.toString(); + } + + /** + * Open an instance of this group. + * + * @param opener + * The item that opened this group. + * + * @return An opened instance of this group. + */ + public OpenGroup open(T opener, T[] parms) { + return new OpenGroup(opener, parms); + } + + public void addPredOpener(Function> pred) { + predOpeners.add(pred); + } + + public void addPredCloser(BiPredicate pred) { + predClosers.add(pred); + } + +} \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceCharacteristics.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceCharacteristics.java new file mode 100644 index 0000000..f053ef6 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceCharacteristics.java @@ -0,0 +1,101 @@ +package bjc.utils.parserutils.delims; + +/** + * Marks the parameters for building a sequence tree. + * + * @author EVE + * + * @param + * The type of item in the tree. + */ +public class SequenceCharacteristics { + /** + * The item to mark the root of the tree. + */ + public final T root; + + /** + * The item to mark the contents of a group/subgroup. + */ + + public final T contents; + + /** + * The item to mark a subgroup. + */ + public final T subgroup; + + /** + * Create a new set of parameters for building a tree. + * + * @param root + * The root marker. + * @param contents + * The group/subgroup contents marker. + * @param subgroup + * The subgroup marker. + */ + public SequenceCharacteristics(T root, T contents, T subgroup) { + this.root = root; + this.contents = contents; + this.subgroup = subgroup; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((contents == null) ? 0 : contents.hashCode()); + result = prime * result + ((root == null) ? 0 : root.hashCode()); + result = prime * result + ((subgroup == null) ? 0 : subgroup.hashCode()); + return result; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#equals(java.lang.Object) + */ + @Override + public boolean equals(Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof SequenceCharacteristics)) return false; + + SequenceCharacteristics other = (SequenceCharacteristics) obj; + + if(contents == null) { + if(other.contents != null) return false; + } else if(!contents.equals(other.contents)) return false; + + if(root == null) { + if(other.root != null) return false; + } else if(!root.equals(other.root)) return false; + + if(subgroup == null) { + if(other.subgroup != null) return false; + } else if(!subgroup.equals(other.subgroup)) return false; + + return true; + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + + builder.append("SequenceCharacteristics [root="); + builder.append(root == null ? "(null)" : root); + builder.append(", contents="); + builder.append(contents == null ? "(null)" : contents); + builder.append(", subgroup="); + builder.append(subgroup == null ? "(null)" : subgroup); + builder.append("]"); + + return builder.toString(); + } +} \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceDelimiter.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceDelimiter.java new file mode 100644 index 0000000..dee5034 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/SequenceDelimiter.java @@ -0,0 +1,304 @@ +package bjc.utils.parserutils.delims; + +import bjc.utils.data.IPair; +import bjc.utils.data.ITree; +import bjc.utils.data.Tree; +import bjc.utils.esodata.PushdownMap; +import bjc.utils.esodata.SimpleStack; +import bjc.utils.esodata.Stack; +import bjc.utils.funcdata.IMap; +import bjc.utils.funcutils.StringUtils; + +import com.google.common.collect.HashMultiset; +import com.google.common.collect.Multiset; + +import java.util.HashMap; +import java.util.Map; + +/** + * Convert linear sequences into trees that represent group structure. + * + * @author EVE + * + * @param + * The type of items in the sequence. + */ +public class SequenceDelimiter { + /* + * Mapping from opening delimiters to the names of the groups they open + */ + + /* + * Mapping from group names to actual groups. + */ + private Map> groups; + + private DelimiterGroup initialGroup; + + /** + * Create a new sequence delimiter. + */ + public SequenceDelimiter() { + groups = new HashMap<>(); + } + + /** + * Convert a linear sequence into a tree that matches the delimiter + * structure. + * + * Essentially, creates a parse tree of the expression against the + * following grammar while obeying the defined group rules. + * + * 
+	 *              -> ( |  | )*
+	 *          ->  
+	 *             ->   
+	 *         
+	 *              -> STRING
+	 *              -> STRING
+	 *             -> STRING
+	 *            -> STRING
+	 *
+ * + * @param chars + * The parameters on how to mark certain portions of the + * tree. + * @param seq + * The sequence to delimit. + * + * @return The sequence as a tree that matches its group structure. Each + * node in the tree is either a data node, a subgroup node, or a + * group node. + * + * A data node is a leaf node whose data is the string it + * represents. + * + * A subgroup node is a node with two children, and the name of + * the sub-group as its label. The first child is the contents + * of the sub-group, and the second is the marker that started + * the subgroup. The marker is a leaf node labeled with its + * contents, and the contents contains a recursive tree. + * + * A group node is a node with three children, and the name of + * the group as its label. The first child is the opening + * delimiter, the second is the group contents, and the third is + * the closing delimiter. The delimiters are leaf nodes labeled + * with their contents, while the group node contains a + * recursive tree. + * + * @throws DelimiterException + * Thrown if something went wrong during sequence + * delimitation. + * + */ + public ITree delimitSequence(SequenceCharacteristics chars, @SuppressWarnings("unchecked") T... seq) + throws DelimiterException { + if(initialGroup == null) { + throw new NullPointerException("Initial group must be specified."); + } + + /* + * The stack of opened and not yet closed groups. + */ + Stack.OpenGroup> groupStack = new SimpleStack<>(); + + /* + * Open initial group. + */ + groupStack.push(initialGroup.open(chars.root, null)); + + /* + * Groups that aren't allowed to be opened at the moment. + */ + Multiset forbiddenDelimiters = HashMultiset.create(); + + /* + * Map of who forbid what for debugging purposes. + */ + IMap whoForbid = new PushdownMap<>(); + + for(int i = 0; i < seq.length; i++) { + T tok = seq[i]; + + IPair possibleOpenPar = groupStack.top().doesOpen(tok); + T possibleOpen = possibleOpenPar.getLeft(); + + /* + * If we have an opening delimiter, handle it. + */ + if(possibleOpen != null) { + DelimiterGroup group = groups.get(possibleOpen); + + /* + * Error on groups that can't open in this + * context. + * + * This means groups that can't occur at the + * top-level of this group, as well as nested + * exclusions from all enclosing groups. + */ + if(isForbidden(groupStack, forbiddenDelimiters, possibleOpen)) { + StringBuilder msgBuilder = new StringBuilder(); + + T forbiddenBy; + + if(whoForbid.containsKey(tok)) { + forbiddenBy = whoForbid.get(tok); + } else { + forbiddenBy = groupStack.top().getName(); + } + + String ctxList = StringUtils.toEnglishList(groupStack.toArray(), "then"); + + msgBuilder.append("Group '"); + msgBuilder.append(group); + msgBuilder.append("' can't be opened in this context."); + msgBuilder.append(" (forbidden by '"); + msgBuilder.append(forbiddenBy); + msgBuilder.append("')\nContext stack: "); + msgBuilder.append(ctxList); + + throw new DelimiterException(msgBuilder.toString()); + } + + /* + * Add an open group. + */ + DelimiterGroup.OpenGroup open = group.open(tok, possibleOpenPar.getRight()); + groupStack.push(open); + + /* + * Add the nested exclusions from this group + */ + for(T exclusion : open.getNestingExclusions()) { + forbiddenDelimiters.add(exclusion); + + whoForbid.put(exclusion, possibleOpen); + } + } else if(!groupStack.empty() && groupStack.top().isClosing(tok)) { + /* + * Close the group. + */ + DelimiterGroup.OpenGroup closed = groupStack.pop(); + + groupStack.top().addItem(closed.toTree(tok, chars)); + + /* + * Remove nested exclusions from this group. + */ + for(T excludedGroup : closed.getNestingExclusions()) { + forbiddenDelimiters.remove(excludedGroup); + + whoForbid.remove(excludedGroup); + } + } else if(!groupStack.empty() && groupStack.top().marksSubgroup(tok)) { + groupStack.top().markSubgroup(tok, chars); + } else { + groupStack.top().addItem(new Tree<>(tok)); + } + } + + /* + * Error if not all groups were closed. + */ + if(groupStack.size() > 1) { + DelimiterGroup.OpenGroup group = groupStack.top(); + + StringBuilder msgBuilder = new StringBuilder(); + + String closingDelims = StringUtils.toEnglishList(group.getNestingExclusions().toArray(), false); + + String ctxList = StringUtils.toEnglishList(groupStack.toArray(), "then"); + + msgBuilder.append("Unclosed group '"); + msgBuilder.append(group.getName()); + msgBuilder.append("'. Expected one of "); + msgBuilder.append(closingDelims); + msgBuilder.append(" to close it\nOpen groups: "); + msgBuilder.append(ctxList); + + throw new DelimiterException(msgBuilder.toString()); + } + + return groupStack.pop().toTree(chars.root, chars); + } + + private boolean isForbidden(Stack.OpenGroup> groupStack, Multiset forbiddenDelimiters, + T groupName) { + boolean localForbid; + if(groupStack.empty()) + localForbid = false; + else + localForbid = groupStack.top().excludes(groupName); + + return localForbid || forbiddenDelimiters.contains(groupName); + } + + /** + * Add a delimiter group. + * + * @param group + * The delimiter group. + */ + public void addGroup(DelimiterGroup group) { + if(group == null) { + throw new NullPointerException("Group must not be null"); + } + + groups.put(group.groupName, group); + } + + /** + * Creates and adds a delimiter group using the provided settings. + * + * @param openers + * The tokens that open this group + * @param groupName + * The name of the group + * @param closers + * The tokens that close this group + */ + public void addGroup(T[] openers, T groupName, @SuppressWarnings("unchecked") T... closers) { + DelimiterGroup group = new DelimiterGroup<>(groupName); + + group.addClosing(closers); + + addGroup(group); + + for(T open : openers) { + group.addOpener(open, groupName); + } + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + + builder.append("SequenceDelimiter ["); + + if(groups != null) { + builder.append("groups="); + builder.append(groups); + builder.append(","); + } + + if(initialGroup != null) { + builder.append("initialGroup="); + builder.append(initialGroup); + } + + builder.append("]"); + + return builder.toString(); + } + + /** + * Set the initial group of this delimiter. + * + * @param initialGroup + * The initial group of this delimiter. + */ + public void setInitialGroup(DelimiterGroup initialGroup) { + this.initialGroup = initialGroup; + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/StringDelimiter.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/StringDelimiter.java new file mode 100644 index 0000000..9799ea9 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/delims/StringDelimiter.java @@ -0,0 +1,31 @@ +package bjc.utils.parserutils.delims; + +import bjc.utils.data.ITree; + +/** + * A sequence delimiter specialized for strings. + * + * @author EVE + * + */ +public class StringDelimiter extends SequenceDelimiter { + + /** + * Override of + * {@link SequenceDelimiter#delimitSequence(Object, Object, Object...)} + * for ease of use for strings. + * + * @param seq + * The sequence to delimit. + * + * @return The sequence as a tree. + * + * @throws DelimiterException + * if something went wrong with delimiting the sequence. + * + * @see SequenceDelimiter + */ + public ITree delimitSequence(String... seq) throws DelimiterException { + return super.delimitSequence(new SequenceCharacteristics("root", "contents", "subgroup"), seq); + } +} -- cgit v1.2.3