1 package org.daisy.pipeline.common.calabash.impl;
2
3 import java.net.URI;
4 import java.util.ArrayList;
5 import java.util.Collection;
6 import java.util.Collections;
7 import java.util.Comparator;
8 import java.util.function.BiFunction;
9 import java.util.function.Function;
10 import java.util.function.Predicate;
11 import java.util.HashMap;
12 import java.util.Iterator;
13 import java.util.LinkedList;
14 import java.util.List;
15 import java.util.ListIterator;
16 import java.util.Map;
17 import java.util.NoSuchElementException;
18 import java.util.Optional;
19 import java.util.regex.Pattern;
20 import java.util.Set;
21 import java.util.SortedSet;
22 import java.util.TreeSet;
23
24 import javax.xml.namespace.QName;
25 import static javax.xml.stream.XMLStreamConstants.CHARACTERS;
26 import static javax.xml.stream.XMLStreamConstants.END_ELEMENT;
27 import static javax.xml.stream.XMLStreamConstants.START_ELEMENT;
28 import javax.xml.stream.XMLStreamException;
29 import javax.xml.stream.XMLStreamWriter;
30
31 import com.google.common.collect.ArrayListMultimap;
32 import com.google.common.collect.Multimap;
33
34 import com.xmlcalabash.model.RuntimeValue;
35
36 import net.sf.saxon.Configuration;
37 import net.sf.saxon.s9api.Axis;
38 import net.sf.saxon.s9api.SaxonApiException;
39 import net.sf.saxon.s9api.XdmItem;
40 import net.sf.saxon.s9api.XdmNode;
41 import net.sf.saxon.s9api.XdmNodeKind;
42 import net.sf.saxon.sxpath.XPathExpression;
43 import net.sf.saxon.trans.XPathException;
44
45 import org.daisy.common.saxon.SaxonHelper;
46 import org.daisy.common.saxon.SaxonInputValue;
47 import org.daisy.common.stax.BaseURIAwareXMLStreamReader;
48 import org.daisy.common.stax.BaseURIAwareXMLStreamWriter;
49 import org.daisy.common.stax.DelegatingBaseURIAwareXMLStreamWriter;
50 import static org.daisy.common.stax.XMLStreamWriterHelper.getAttributes;
51 import static org.daisy.common.stax.XMLStreamWriterHelper.writeAttribute;
52 import static org.daisy.common.stax.XMLStreamWriterHelper.writeAttributes;
53 import static org.daisy.common.stax.XMLStreamWriterHelper.writeCharacters;
54 import static org.daisy.common.stax.XMLStreamWriterHelper.writeDocument;
55 import static org.daisy.common.stax.XMLStreamWriterHelper.writeEvent;
56 import static org.daisy.common.stax.XMLStreamWriterHelper.writeStartElement;
57
58 import org.daisy.common.transform.InputValue;
59 import org.daisy.common.transform.Mult;
60 import org.daisy.common.transform.SingleInSingleOutXMLTransformer;
61 import org.daisy.common.transform.TransformerException;
62 import org.daisy.common.transform.XMLInputValue;
63 import org.daisy.common.transform.XMLOutputValue;
64
65
66
67
68
69
70 class Chunker extends SingleInSingleOutXMLTransformer {
71
72 final RuntimeValue allowBreakBeforeOption;
73 final RuntimeValue allowBreakAfterOption;
74 final RuntimeValue preferBreakBeforeOption;
75 final RuntimeValue preferBreakAfterOption;
76 final RuntimeValue alwaysBreakBeforeOption;
77 final RuntimeValue alwaysBreakAfterOption;
78 final QName partAttribute;
79
80 final boolean propagate;
81 final int maxChunkSize;
82 final Configuration config;
83
84 private static final QName _ID = new QName("id");
85 private static final QName XML_ID = new QName("http://www.w3.org/XML/1998/namespace", "id", "xml");
86 private static final QName D_FILESET = new QName("http://www.daisy.org/ns/pipeline/data", "fileset");
87 private static final QName D_FILE = new QName("http://www.daisy.org/ns/pipeline/data", "file");
88 private static final QName D_ANCHOR = new QName("http://www.daisy.org/ns/pipeline/data", "anchor");
89 private static final QName _HREF = new QName("href");
90 private static final QName _ORIGINAL_HREF = new QName("original-href");
91
92 Chunker(RuntimeValue allowBreakBeforeOption, RuntimeValue allowBreakAfterOption,
93 RuntimeValue preferBreakBeforeOption, RuntimeValue preferBreakAfterOption,
94 RuntimeValue alwaysBreakBeforeOption, RuntimeValue alwaysBreakAfterOption,
95 QName partAttribute, boolean propagate, int maxChunkSize, Configuration config) {
96 this.allowBreakBeforeOption = allowBreakBeforeOption;
97 this.allowBreakAfterOption = allowBreakAfterOption;
98 this.preferBreakBeforeOption = preferBreakBeforeOption;
99 this.preferBreakAfterOption = preferBreakAfterOption;
100 this.alwaysBreakBeforeOption = alwaysBreakBeforeOption;
101 this.alwaysBreakAfterOption = alwaysBreakAfterOption;
102 this.partAttribute = partAttribute;
103 this.propagate = propagate;
104 this.maxChunkSize = maxChunkSize;
105 this.config = config;
106 }
107
108 private LinkedList<QName> parents;
109 private LinkedList<Map<QName,String>> parentAttrs;
110 private Path.Builder currentPath;
111 private Iterator<BreakPosition> splitPoints;
112 private Multimap<Integer,String> idToChunk;
113 private BreakPosition nextSplitPoint;
114
115 public Runnable transform(XMLInputValue<?> source, XMLOutputValue<?> result, InputValue<?> params) throws IllegalArgumentException {
116 if (source == null || result == null)
117 throw new IllegalArgumentException();
118 if (!(source instanceof SaxonInputValue))
119 throw new IllegalArgumentException();
120 return () -> transform((SaxonInputValue)source.ensureSingleItem(), result.asXMLStreamWriter());
121 }
122
123 void transform(SaxonInputValue input, BaseURIAwareXMLStreamWriter output) throws TransformerException {
124 Mult<SaxonInputValue> mult = input.mult(2);
125 XdmItem item = mult.get().asXdmItemIterator().next();
126 if (!(item instanceof XdmNode))
127 throw new TransformerException(new IllegalArgumentException());
128 XdmNode doc = (XdmNode)item;
129 BaseURIAwareXMLStreamReader reader = mult.get().asXMLStreamReader();
130 int chunkCount;
131 try {
132 SortedSet<BreakPosition> collectSplitPoints = new TreeSet<>();
133 Map<String,Path> collectIds = new HashMap<>();
134 getSplitPoints(doc, collectSplitPoints, collectIds);
135 chunkCount = collectSplitPoints.size() + 1;
136 idToChunk = ArrayListMultimap.<Integer,String>create();
137 int n = 1;
138 for (BreakPosition sp : collectSplitPoints) {
139 Iterator<Map.Entry<String,Path>> i = collectIds.entrySet().iterator();
140 while (i.hasNext()) {
141 Map.Entry<String,Path> e = i.next();
142 if (sp.compareTo(e.getValue()) > 0) {
143 idToChunk.put(n, e.getKey());
144 i.remove();
145 }
146 }
147 n++;
148 }
149 for (String id : collectIds.keySet())
150 idToChunk.put(n, id);
151 splitPoints = collectSplitPoints.iterator();
152 } catch (XPathException | SaxonApiException e) {
153 throw new TransformerException(e);
154 }
155 URI inputBase = doc.getBaseURI();
156 if (inputBase == null)
157 throw new TransformerException(new RuntimeException("source document must have a base URI"));
158 if (splitPoints.hasNext()) {
159
160 try {
161 output.setBaseURI(inputBase);
162 output.writeStartDocument();
163 writeStartElement(output, D_FILESET);
164 for (Integer chunk = 1; chunk <= chunkCount; chunk++) {
165 writeStartElement(output, D_FILE);
166 writeAttribute(output, _HREF, getChunkBaseURI(inputBase, chunk).toASCIIString());
167 writeAttribute(output, _ORIGINAL_HREF, inputBase.toASCIIString());
168 for (String id : idToChunk.get(chunk)) {
169 writeStartElement(output, D_ANCHOR);
170 writeAttribute(output, _ID, id);
171 output.writeEndElement();
172 }
173 output.writeEndElement();
174 }
175 output.writeEndElement();
176 output.writeEndDocument();
177 } catch (XMLStreamException e) {
178 throw new TransformerException(e);
179 }
180
181 output = setBaseURI(output, inputBase);
182 transform(reader, output);
183 } else {
184
185 try {
186 output.setBaseURI(inputBase);
187 output.writeStartDocument();
188 writeStartElement(output, D_FILESET);
189 output.writeEndElement();
190 output.writeEndDocument();
191 } catch (XMLStreamException e) {
192 throw new TransformerException(e);
193 }
194
195 try {
196 output.setBaseURI(inputBase);
197 writeDocument(output, reader);
198 } catch (XMLStreamException e) {
199 throw new TransformerException(e);
200 }
201 }
202 }
203
204 void transform(BaseURIAwareXMLStreamReader reader, BaseURIAwareXMLStreamWriter writer) throws TransformerException {
205 nextSplitPoint = null;
206 if (splitPoints.hasNext())
207 nextSplitPoint = splitPoints.next();
208 parents = new LinkedList<>();
209 parentAttrs = new LinkedList<>();
210 boolean containsSplitPoint = true;
211 LinkedList<Boolean> containsSplitPointStack = new LinkedList<>();
212 currentPath = new Path.Builder();
213 try {
214 int event = reader.getEventType();
215 while (true)
216 try {
217 switch (event) {
218 case START_ELEMENT:
219 containsSplitPointStack.push(containsSplitPoint);
220 if (!currentPath.isRoot()) {
221 currentPath.nextElement();
222 if (containsSplitPoint && isSplitPoint(currentPath, BreakPosition.Side.BEFORE, nextSplitPoint))
223 split(writer);
224 containsSplitPoint = containsSplitPoint(currentPath, nextSplitPoint);
225 }
226 writeStartElement(writer, reader);
227 writeAttributes(writer, reader);
228 if (partAttribute != null && containsSplitPoint)
229 writeAttribute(writer, partAttribute, "head");
230 currentPath.down();
231 if (containsSplitPoint) {
232 parents.push(reader.getName());
233 parentAttrs.push(getAttributes(reader));
234 }
235 break;
236 case END_ELEMENT:
237 if (containsSplitPoint) {
238 parents.pop();
239 parentAttrs.pop();
240 }
241 writer.writeEndElement();
242 containsSplitPoint = containsSplitPointStack.pop();
243 if (containsSplitPoint && isSplitPoint(currentPath, BreakPosition.Side.AFTER, nextSplitPoint))
244 split(writer);
245 currentPath.up();
246 break;
247 case CHARACTERS:
248 if (currentPath.isElement())
249 currentPath.inc();
250 if (containsSplitPoint && isSplitPoint(currentPath, BreakPosition.Side.BEFORE, nextSplitPoint))
251 split(writer);
252 writeCharacters(writer, reader);
253 if (containsSplitPoint && isSplitPoint(currentPath, BreakPosition.Side.AFTER, nextSplitPoint))
254 split(writer);
255 break;
256 default:
257 writeEvent(writer, reader); }
258 event = reader.next();
259 } catch (NoSuchElementException e) {
260 break;
261 }
262 } catch (XMLStreamException e) {
263 throw new TransformerException(e);
264 }
265 }
266
267 void split(XMLStreamWriter writer) throws XMLStreamException {
268 nextSplitPoint = splitPoints.hasNext() ? splitPoints.next() : null;
269 for (QName n : parents)
270 writer.writeEndElement();
271 writer.writeEndDocument();
272 writer.writeStartDocument();
273 Iterator<QName> elems = parents.descendingIterator();
274 Iterator<Map<QName,String>> attrs = parentAttrs.descendingIterator();
275 int i = 0;
276 while (elems.hasNext()) {
277 writeStartElement(writer, elems.next());
278 for (Map.Entry<QName,String> attr : attrs.next().entrySet())
279 if (!(attr.getKey().equals(_ID) || attr.getKey().equals(XML_ID)))
280 writeAttribute(writer, attr);
281 if (partAttribute != null) {
282 if (containsSplitPoint(currentPath.subPath(i++), nextSplitPoint))
283 writeAttribute(writer, partAttribute, "middle");
284 else
285 writeAttribute(writer, partAttribute, "tail");
286 }
287 }
288 }
289
290 static BaseURIAwareXMLStreamWriter setBaseURI(BaseURIAwareXMLStreamWriter output, URI sourceBaseURI) {
291 return new DelegatingBaseURIAwareXMLStreamWriter() {
292 int supplied = 0;
293 protected BaseURIAwareXMLStreamWriter delegate() {
294 return output;
295 }
296 @Override
297 public void writeStartDocument() throws XMLStreamException {
298 output.setBaseURI(getChunkBaseURI(sourceBaseURI, ++supplied));
299 super.writeStartDocument();
300 }
301 @Override
302 public void writeStartDocument(String version) throws XMLStreamException {
303 output.setBaseURI(getChunkBaseURI(sourceBaseURI, ++supplied));
304 super.writeStartDocument(version);
305 }
306 @Override
307 public void writeStartDocument(String encoding, String version) throws XMLStreamException {
308 output.setBaseURI(getChunkBaseURI(sourceBaseURI, ++supplied));
309 super.writeStartDocument(encoding, version);
310 }
311 };
312 }
313
314 static URI getChunkBaseURI(URI sourceBaseURI, int chunkNr) {
315 return URI.create(sourceBaseURI.toASCIIString().replaceAll("^(.+?)(\\.[^\\.]+)$", "$1-" + chunkNr + "$2"));
316 }
317
318 final static boolean isSplitPoint(Path elementPath, BreakPosition.Side side, BreakPosition splitPoint) {
319 return splitPoint != null && splitPoint.equals(elementPath, side);
320 }
321
322 final static boolean containsSplitPoint(Path elementPath, BreakPosition splitPoint) {
323 if (splitPoint == null)
324 return false;
325 return elementPath.contains(splitPoint.path);
326 }
327
328 void getSplitPoints(XdmNode source, SortedSet<BreakPosition> collectSplitPoints, Map<String,Path> collectIds)
329 throws XPathException, SaxonApiException {
330 SortedSet<BreakOpportunity> opportunities = new TreeSet<>();
331 int totalBytes = getBreakOpportunities(source, opportunities, collectIds);
332 collectSplitPoints.addAll(computeSplitPoints(opportunities, totalBytes, maxChunkSize * 1000));
333 }
334
335 static SortedSet<BreakPosition> computeSplitPoints(SortedSet<BreakOpportunity> opportunities, int totalBytes, int maxSize) {
336 SortedSet<BreakPosition> splitPoints = new TreeSet<>();
337 if (maxSize <= 0) {
338 for (BreakOpportunity o : opportunities)
339 if (o.weight == BreakOpportunity.Weight.ALWAYS)
340 splitPoints.add(o.position);
341 } else {
342 BreakOpportunity BEGIN = new BreakOpportunity(
343 new BreakPosition(Path.ROOT, BreakPosition.Side.BEFORE),
344 BreakOpportunity.Weight.ALWAYS,
345 0);
346 BreakOpportunity END = new BreakOpportunity(
347 new BreakPosition(Path.ROOT, BreakPosition.Side.AFTER),
348 BreakOpportunity.Weight.ALWAYS,
349 totalBytes);
350 opportunities.add(BEGIN);
351 opportunities.add(END);
352
353
354 int preferredSize = maxSize * 4 / 5;
355 Function<BreakOpportunity,Set<BreakOpportunity>> neighbors = (current) -> {
356 Set<BreakOpportunity> result = new TreeSet<>();
357 if (current.equals(END))
358 return result;
359 Iterator<BreakOpportunity> i = opportunities.iterator();
360 for (;;)
361 try {
362 BreakOpportunity n = i.next();
363 if (n.equals(current))
364 break; }
365 catch (NoSuchElementException e) {
366 throw new IllegalArgumentException(current+" is not a break opportunity"); }
367 while (i.hasNext()) {
368 BreakOpportunity n = i.next();
369 if (n.bytesBefore - current.bytesBefore <= maxSize) {
370 result.add(n);
371 if (n.weight == BreakOpportunity.Weight.ALWAYS)
372 break;
373 } else {
374 if (result.isEmpty())
375 result.add(n);
376 break;
377 }
378 }
379 return result;
380 };
381
382
383
384 BiFunction<BreakOpportunity,BreakOpportunity,Float> cost = (begin, end) -> {
385 float result = 0;
386 result += .2;
387 switch (end.weight) {
388 case ALWAYS:
389 case PREFER:
390 break;
391 case ALLOW:
392 result += .2;
393 }
394 int size = end.bytesBefore - begin.bytesBefore;
395 int diff = Math.abs(preferredSize - size);
396 if (size > maxSize)
397 diff *= 4;
398 result += (float)diff / (float)preferredSize;
399 return result;
400 };
401
402
403 List<BreakOpportunity> solution = shortestPath(BEGIN, END, neighbors, cost);
404 for (BreakOpportunity o : solution)
405 splitPoints.add(o.position);
406 }
407 return splitPoints;
408 }
409
410
411 static <T> List<T> shortestPath(T from, T to, Function<T,Set<T>> neighbors, BiFunction<T,T,Float> distance) {
412 Map<T,Float> tentativeDistance = new HashMap<>();
413 Set<T> visited = new TreeSet<>();
414 Map<T,T> bestPredecessor = new HashMap<>();
415 tentativeDistance.put(from, 0f);
416 T current = from;
417 for (;;) {
418 for (T n : neighbors.apply(current)) {
419 if (!visited.contains(n)) {
420 float distFromCurrent = distance.apply(current, n);
421 float distFromBegin = tentativeDistance.get(current) + distFromCurrent;
422 if (!tentativeDistance.containsKey(n) || tentativeDistance.get(n) > distFromBegin) {
423 tentativeDistance.put(n, distFromBegin);
424 bestPredecessor.put(n, current);
425 }}}
426 visited.add(current);
427 tentativeDistance.remove(current);
428 try {
429 current = Collections.min(
430 tentativeDistance.entrySet(),
431 Comparator.comparing(Map.Entry::getValue)).getKey();
432 } catch (NoSuchElementException e) {
433 throw new IllegalArgumentException("neighbors function cannot connect "+from+" and "+to);
434 }
435 if (current.equals(to)) {
436 List<T> path = new ArrayList<>();
437 current = to;
438 for (;;) {
439 current = bestPredecessor.get(current);
440 if (current.equals(from))
441 break;
442 path.add(0, current);
443 }
444 return path;
445 }}
446 }
447
448 int getBreakOpportunities(XdmNode source, SortedSet<BreakOpportunity> collectBreakOpportunities, Map<String,Path> collectIds)
449 throws XPathException, SaxonApiException {
450 net.sf.saxon.s9api.QName _ID = new net.sf.saxon.s9api.QName(Chunker._ID);
451 net.sf.saxon.s9api.QName XML_ID = new net.sf.saxon.s9api.QName(Chunker.XML_ID);
452 Predicate<XdmNode> allowBreakBefore = parseBreakOpportunityOption(allowBreakBeforeOption);
453 Predicate<XdmNode> allowBreakAfter = parseBreakOpportunityOption(allowBreakAfterOption);
454 Predicate<XdmNode> preferBreakBefore = parseBreakOpportunityOption(preferBreakBeforeOption);
455 Predicate<XdmNode> preferBreakAfter = parseBreakOpportunityOption(preferBreakAfterOption);
456 Predicate<XdmNode> alwaysBreakBefore = parseBreakOpportunityOption(alwaysBreakBeforeOption);
457 Predicate<XdmNode> alwaysBreakAfter = parseBreakOpportunityOption(alwaysBreakAfterOption);
458 return new Function<XdmNode,Integer>() {
459 Path.Builder currentPath = new Path.Builder();
460 public Integer apply(XdmNode node) {
461 int bytesSeen = 0;
462 if (node.getNodeKind() == XdmNodeKind.DOCUMENT) {
463 for (XdmItem i : SaxonHelper.axisIterable(node, Axis.CHILD))
464 bytesSeen += apply((XdmNode)i);
465 } else if (node.getNodeKind() == XdmNodeKind.ELEMENT) {
466 if (!currentPath.isRoot())
467 currentPath.nextElement();
468 String id = node.getAttributeValue(XML_ID);
469 if (id == null) id = node.getAttributeValue(_ID);
470 if (id != null)
471 collectIds.put(id, currentPath.build());
472 if (!currentPath.isRoot())
473 if (alwaysBreakBefore.test(node))
474 addOptionally(collectBreakOpportunities,
475 propagate(node, currentPath, BreakPosition.Side.BEFORE, BreakOpportunity.Weight.ALWAYS,
476 bytesSeen, propagate));
477 else if (preferBreakBefore.test(node))
478 addOptionally(collectBreakOpportunities,
479 propagate(node, currentPath, BreakPosition.Side.BEFORE, BreakOpportunity.Weight.PREFER,
480 bytesSeen, propagate));
481 else if (allowBreakBefore.test(node))
482 addOptionally(collectBreakOpportunities,
483 propagate(node, currentPath, BreakPosition.Side.BEFORE, BreakOpportunity.Weight.ALLOW,
484 bytesSeen, propagate));
485 currentPath.down();
486 for (XdmItem i : SaxonHelper.axisIterable(node, Axis.CHILD))
487 bytesSeen += apply((XdmNode)i);
488 currentPath.up();
489 if (!currentPath.isRoot())
490 if (alwaysBreakAfter.test(node))
491 addOptionally(collectBreakOpportunities,
492 propagate(node, currentPath, BreakPosition.Side.AFTER, BreakOpportunity.Weight.ALWAYS,
493 bytesSeen, propagate));
494 else if (preferBreakAfter.test(node))
495 addOptionally(collectBreakOpportunities,
496 propagate(node, currentPath, BreakPosition.Side.AFTER, BreakOpportunity.Weight.PREFER,
497 bytesSeen, propagate));
498 else if (allowBreakAfter.test(node))
499 addOptionally(collectBreakOpportunities,
500 propagate(node, currentPath, BreakPosition.Side.AFTER, BreakOpportunity.Weight.ALLOW,
501 bytesSeen, propagate));
502 } else if (node.getNodeKind() == XdmNodeKind.TEXT) {
503
504
505 bytesSeen += node.getStringValue().getBytes().length;
506 }
507 return bytesSeen;
508 }
509 }.apply(source);
510 }
511
512 Predicate<XdmNode> parseBreakOpportunityOption(RuntimeValue option) throws XPathException {
513 if (!option.getString().equals("/*")) {
514 XPathExpression matcher = SaxonHelper.compileExpression(option.getString(),
515 option.getNamespaceBindings(),
516 config);
517 return n -> n.getNodeKind() == XdmNodeKind.ELEMENT && SaxonHelper.evaluateBoolean(matcher, n);
518 } else
519 return n -> false;
520 }
521
522 static <T> void addOptionally(Collection<T> collection, Optional<T> object) {
523 if (object.isPresent())
524 collection.add(object.get());
525 }
526
527 static Optional<BreakOpportunity> propagate(XdmNode element, Path.Builder path, BreakPosition.Side side,
528 BreakOpportunity.Weight weight, int bytesSeen, boolean propagate) {
529 path = path.builder();
530 while (!path.isRoot()) {
531 if (propagate) {
532 if (shouldPropagateBreak(element, side)) {
533 element = (XdmNode)element.getParent();
534 path.up();
535 continue;
536 }
537 if (side == BreakPosition.Side.AFTER)
538 bytesSeen += skipWhiteSpaceNodes(element, side, path);
539 }
540 return Optional.of(new BreakOpportunity(new BreakPosition(path, side).normalize(), weight, bytesSeen));
541 }
542 return Optional.empty();
543 }
544
545 static boolean shouldPropagateBreak(XdmNode element, BreakPosition.Side side) {
546 for (XdmItem i : SaxonHelper.axisIterable(element, side == BreakPosition.Side.BEFORE ? Axis.PRECEDING_SIBLING
547 : Axis.FOLLOWING_SIBLING)) {
548 XdmNode n = (XdmNode)i;
549 if (n.getNodeKind() == XdmNodeKind.ELEMENT)
550 return false;
551 else if (n.getNodeKind() == XdmNodeKind.TEXT && !isWhiteSpaceNode(n))
552 return false;
553 }
554 return true;
555 }
556
557 static int skipWhiteSpaceNodes(XdmNode element, BreakPosition.Side side, Path.Builder path) {
558 int bytesSkipped = 0;
559 for (XdmItem i : SaxonHelper.axisIterable(element, side == BreakPosition.Side.BEFORE ? Axis.PRECEDING_SIBLING
560 : Axis.FOLLOWING_SIBLING)) {
561 XdmNode n = (XdmNode)i;
562 if (n.getNodeKind() == XdmNodeKind.ELEMENT) {
563 if (side == BreakPosition.Side.AFTER)
564 path.inc();
565 else
566 path.dec();
567 return bytesSkipped;
568 } else if (n.getNodeKind() == XdmNodeKind.TEXT) {
569 if (isWhiteSpaceNode(n))
570 bytesSkipped += n.getStringValue().getBytes().length;
571 else
572 return 0;
573 }
574 }
575 return 0;
576 }
577
578 static final Pattern WHITESPACE_RE = Pattern.compile("\\s*");
579
580 static boolean isWhiteSpaceNode(XdmNode textNode) {
581 return isWhiteSpace(textNode.getStringValue());
582 }
583
584 static boolean isWhiteSpace(String text) {
585 return WHITESPACE_RE.matcher(text).matches();
586 }
587
588
589
590
591
592
593
594
595
596
597 static class Path implements Comparable<Path> {
598
599 protected final List<Integer> path;
600
601 final static Path ROOT = new Builder().build();
602
603 private Path(List<Integer> path) {
604 this.path = path;
605 }
606
607 public boolean isRoot() {
608 return path.isEmpty();
609 }
610
611 public boolean isElement() {
612 return path.isEmpty() || path.get(0) % 2 == 0;
613 }
614
615 public Builder builder() {
616 return new Builder(this);
617 }
618
619
620
621
622
623 @Override
624 public int compareTo(Path o) {
625 ListIterator<Integer> a = path.listIterator(path.size());
626 ListIterator<Integer> b = o.path.listIterator(o.path.size());
627 while (a.hasPrevious() && b.hasPrevious()) {
628 int c = a.previous().compareTo(b.previous());
629 if (c != 0) return c;
630 }
631 return 0;
632 }
633
634 public boolean contains(Path o) {
635 if (compareTo(o) != 0)
636 return false;
637 return o.path.size() > this.path.size();
638 }
639
640
641 public Path subPath(int depth) {
642 if (depth < 0)
643 throw new IllegalArgumentException();
644 else if (depth == 0)
645 return ROOT;
646 else
647 return new Path(path.subList(path.size() - depth, path.size()));
648 }
649
650 static class Builder extends Path {
651
652 private final LinkedList<Integer> mutablePath;
653
654 public Builder() {
655 super(new LinkedList<>());
656 mutablePath = (LinkedList<Integer>)path;
657 }
658
659 private Builder(Path from) {
660 this();
661 for (Integer step : from.path)
662 mutablePath.add(step);
663 }
664
665 public Builder down() {
666 mutablePath.push(0);
667 return this;
668 }
669
670 public Builder up() {
671 mutablePath.pop();
672 return this;
673 }
674
675 public Builder inc() {
676 mutablePath.push(mutablePath.pop() + 1);
677 return this;
678 }
679
680 public Builder dec() {
681 mutablePath.push(mutablePath.pop() - 1);
682 return this;
683 }
684
685 public Builder nextElement() {
686 int step = mutablePath.pop() + 1;
687 if (step % 2 == 1)
688 step++;
689 mutablePath.push(step);
690 return this;
691 }
692
693 public Path build() {
694 List<Integer> copy = new LinkedList<>();
695 for (Integer step : path)
696 copy.add(step);
697 return new Path(copy);
698 }
699 }
700
701 @Override
702 public int hashCode() {
703 final int prime = 31;
704 int result = 1;
705 result = prime * result + path.hashCode();
706 return result;
707 }
708
709 @Override
710 public boolean equals(Object obj) {
711 if (this == obj)
712 return true;
713 if (obj == null)
714 return false;
715 if (getClass() != obj.getClass())
716 return false;
717 Path other = (Path)obj;
718 return this.path.equals(other.path);
719 }
720
721 @Override
722 public String toString() {
723 if (isRoot())
724 return "/";
725 StringBuilder b = new StringBuilder();
726 for (Integer i : path)
727 b.insert(0, "/" + i);
728 return b.toString();
729 }
730
731
732 static Path parse(String string) {
733 LinkedList<Integer> path = new LinkedList<>();
734 if ("/".equals(string))
735 return ROOT;
736 if (!string.matches("(/(0|[1-9][0-9]*))+"))
737 throw new IllegalArgumentException();
738 String[] steps = string.split("/");
739 for (int i = 1; i < steps.length; i++)
740 path.push(Integer.parseInt(steps[i]));
741 return new Path(path);
742 }
743 }
744
745 static class BreakPosition implements Comparable<BreakPosition> {
746
747 enum Side { BEFORE, AFTER }
748 final Path path;
749 final Side side;
750
751 BreakPosition(Path path, Side side) {
752 if (path == null || side == null)
753 throw new NullPointerException();
754 this.path = path;
755 this.side = side;
756 }
757
758
759 BreakPosition normalize() {
760 if (side == Side.BEFORE)
761 return this;
762 else
763 return new BreakPosition(path.builder().inc(), Side.BEFORE);
764 }
765
766 @Override
767 public int compareTo(BreakPosition o) {
768 int c = this.path.compareTo(o.path);
769 if (c != 0)
770 return c;
771 if (this.path.contains(o.path))
772 return this.side == Side.BEFORE ? -1 : 1;
773 else if (o.path.contains(this.path))
774 return o.side == Side.BEFORE ? 1 : -1;
775 else
776 return side.compareTo(o.side);
777 }
778
779
780
781
782
783
784 public int compareTo(Path path) {
785 int c = this.path.compareTo(path);
786 if (c != 0)
787 return c;
788 if (this.path.contains(path))
789 return 0;
790 else if (this.side == Side.BEFORE)
791 return -1;
792 else
793 return 1;
794 }
795
796 @Override
797 public int hashCode() {
798 final int prime = 31;
799 int result = 1;
800 result = prime * result + path.hashCode();
801 result = prime * result + side.hashCode();
802 return result;
803 }
804
805 @Override
806 public boolean equals(Object obj) {
807 if (this == obj)
808 return true;
809 if (obj == null)
810 return false;
811 if (getClass() != obj.getClass())
812 return false;
813 BreakPosition other = (BreakPosition)obj;
814 return equals(other.path, other.side);
815 }
816
817 public boolean equals(Path path, Side side) {
818 if (path == null)
819 return false;
820 if (this.side != side)
821 return false;
822 if (!this.path.equals(path))
823 return false;
824 return true;
825 }
826
827 @Override
828 public String toString() {
829 return side + " " + path;
830 }
831 }
832
833 static class BreakOpportunity implements Comparable<BreakOpportunity> {
834
835 enum Weight { ALWAYS, PREFER, ALLOW }
836 final BreakPosition position;
837 final Weight weight;
838 final int bytesBefore;
839
840 BreakOpportunity(BreakPosition position, Weight weight, int bytesBefore) {
841 this.position = position;
842 this.weight = weight;
843 this.bytesBefore = bytesBefore;
844 }
845
846 @Override
847 public int compareTo(BreakOpportunity o) {
848 int c = this.position.compareTo(o.position);
849 if (c != 0)
850 return c;
851 return this.weight.compareTo(o.weight);
852 }
853
854 @Override
855 public int hashCode() {
856 final int prime = 31;
857 int result = 1;
858 result = prime * result + bytesBefore;
859 result = prime * result + position.hashCode();
860 result = prime * result + weight.hashCode();
861 return result;
862 }
863
864 @Override
865 public boolean equals(Object obj) {
866 if (this == obj)
867 return true;
868 if (obj == null)
869 return false;
870 if (getClass() != obj.getClass())
871 return false;
872 BreakOpportunity other = (BreakOpportunity)obj;
873 if (bytesBefore != other.bytesBefore)
874 return false;
875 if (!position.equals(other.position))
876 return false;
877 if (weight != other.weight)
878 return false;
879 return true;
880 }
881
882 @Override
883 public String toString() {
884 return weight + " " + position;
885 }
886 }
887 }