A cross platform Audiobookshelf client for Android and iOS
Dart
import 'dart:convert';
import 'package:archive/archive_io.dart';
import 'package:html/dom.dart' as html;
import 'package:html/parser.dart' as html_parser;
import 'package:xml/xml.dart';
import 'media_overlay.dart';
import '../utils/percent_escapes.dart';
/// A spot found in a book's text: the spine section, where the words start
/// and end in its text, and how well they matched (0 to 1).
typedef TextMatch = ({int si, int s, int e, double fine});
final RegExp _token = RegExp(r"[\p{L}\p{N}']+", unicode: true);
/// Where [transcript] sits in [text], fuzzily: windows of the text holding
/// most of the transcript's words, scored by edit distance over the words.
/// The same scoring the reader runs on a page it has open.
({int s, int e, double fine})? matchTranscript(String text, String transcript) {
final t = [for (final m in _token.allMatches(transcript)) m.group(0)!.toLowerCase()];
if (t.length < 3) return null;
final need = <String, int>{};
for (final w in t) {
need[w] = (need[w] ?? 0) + 1;
}
final tNorm = t.join(' ');
final width = t.length;
final st = [
for (final m in _token.allMatches(text)) (t: m.group(0)!.toLowerCase(), s: m.start, e: m.end),
];
if (st.length < 3) return null;
final have = <String, int>{};
var matched = 0;
final cands = <({int i, int m})>[];
final floor = (width * 0.4).floor() > 2 ? (width * 0.4).floor() : 2;
for (var p = 0; p < st.length; p++) {
final tk = st[p].t;
have[tk] = (have[tk] ?? 0) + 1;
if (have[tk]! <= (need[tk] ?? 0)) matched++;
if (p >= width) {
final old = st[p - width].t;
if (have[old]! <= (need[old] ?? 0)) matched--;
have[old] = have[old]! - 1;
}
if (matched >= floor) cands.add((i: p - width + 1 < 0 ? 0 : p - width + 1, m: matched));
}
cands.sort((a, b) => b.m.compareTo(a.m));
final picked = <({int i, int m})>[];
for (final c in cands) {
if (picked.length >= 4) break;
if (picked.any((p) => (p.i - c.i).abs() < width)) continue;
picked.add(c);
}
({int s, int e, double fine})? out;
for (final c in picked) {
final e1 = c.i + width - 1 < st.length - 1 ? c.i + width - 1 : st.length - 1;
final win = [for (var k = c.i; k <= e1; k++) st[k].t].join(' ');
final longest = tNorm.length > win.length ? tNorm.length : win.length;
final fine = 1 - _levenshtein(tNorm, win) / longest;
if (out == null || fine > out.fine) out = (s: st[c.i].s, e: st[e1].e, fine: fine);
}
return out;
}
int _levenshtein(String a, String b) {
final m = a.length, n = b.length;
if (m == 0) return n;
if (n == 0) return m;
var prev = List<int>.generate(n + 1, (j) => j);
var cur = List<int>.filled(n + 1, 0);
for (var x = 1; x <= m; x++) {
cur[0] = x;
final ca = a.codeUnitAt(x - 1);
for (var j = 1; j <= n; j++) {
final cost = ca == b.codeUnitAt(j - 1) ? 0 : 1;
final del = prev[j] + 1, ins = cur[j - 1] + 1, sub = prev[j - 1] + cost;
cur[j] = del < ins ? (del < sub ? del : sub) : (ins < sub ? ins : sub);
}
final tmp = prev;
prev = cur;
cur = tmp;
}
return prev[n];
}
class _Section {
_Section(this.root, this.nodes, this.starts, this.text);
/// The html element.
final html.Element root;
final List<html.Text> nodes;
final List<int> starts;
final String text;
}
/// Text nodes directly under [parent], in order.
List<html.Text> _textKids(html.Node parent) => parent.nodes.whereType<html.Text>().toList();
/// An EPUB's text as the reader's pages hold it, read straight from the
/// file: each spine section's body text, the table of contents, and CFIs to
/// and from a spot in that text in the form the reader writes them. Lets a
/// place be found and saved with no reader open.
///
/// Sections are parsed as HTML, as the reader's epub.js does (it loads each
/// one through an iframe's srcdoc), so the text nodes, offsets and element
/// counts are the browser's: a self-closing `<span/>` swallows what follows
/// it, a table gains its tbody. Parsing as XML would place CFIs elsewhere.
class EpubBookText {
EpubBookText._(this._input, this._archive, this.spine, this._paths, this.toc, this._spineStep,
this.hasMediaOverlays);
final InputFileStream _input;
final Archive _archive;
/// Spine hrefs in reading order, as the package lists them.
final List<String> spine;
final List<String> _paths;
/// The table of contents, flattened in reading order.
final List<({String href, String title})> toc;
final int _spineStep;
/// The EPUB carries its own narration (EPUB 3 media overlays).
final bool hasMediaOverlays;
final Map<int, _Section?> _sections = {};
/// Opens the EPUB at [path]. Null when it isn't one.
static EpubBookText? open(String path) {
final input = InputFileStream(path);
try {
final archive = ZipDecoder().decodeStream(input);
final book = _read(input, archive);
if (book == null) input.closeSync();
return book;
} catch (_) {
input.closeSync();
return null;
}
}
void close() => _input.closeSync();
static String? _file(Archive archive, String name) {
final f = archive.findFile(name);
return f == null ? null : utf8.decode(f.content as List<int>, allowMalformed: true);
}
static XmlDocument? _xml(String? source) {
if (source == null) return null;
try {
return XmlDocument.parse(source, entityMapping: XmlDefaultEntityMapping.html5());
} catch (_) {
return null;
}
}
static String _dir(String path) {
final i = path.lastIndexOf('/');
return i < 0 ? '' : path.substring(0, i + 1);
}
static String _resolve(String base, String href) {
final clean = undoPathEscapes(href.split('#').first.split('?').first);
final parts = <String>[];
for (final p in '${_dir(base)}$clean'.split('/')) {
if (p.isEmpty || p == '.') continue;
if (p == '..') {
if (parts.isNotEmpty) parts.removeLast();
} else {
parts.add(p);
}
}
return parts.join('/');
}
static String _flat(String s) => s.replaceAll(RegExp(r'\s+'), ' ').trim();
static EpubBookText? _read(InputFileStream input, Archive archive) {
final container = _xml(_file(archive, 'META-INF/container.xml'));
final opfPath = container?.descendantElements
.where((e) => e.localName == 'rootfile')
.map((e) => e.getAttribute('full-path'))
.firstWhere((p) => p != null, orElse: () => null);
if (opfPath == null) return null;
final opf = _xml(_file(archive, opfPath));
final package = opf?.rootElement;
if (package == null) return null;
final children = package.childElements.toList();
final spineEl = children.where((e) => e.localName == 'spine').firstOrNull;
final manifestEl = children.where((e) => e.localName == 'manifest').firstOrNull;
if (spineEl == null || manifestEl == null) return null;
final manifest = <String, ({String href, String path, String type, String props})>{};
var overlays = false;
for (final item in manifestEl.childElements.where((e) => e.localName == 'item')) {
final id = item.getAttribute('id'), href = item.getAttribute('href');
if (id == null || href == null) continue;
if (item.getAttribute('media-overlay') != null) overlays = true;
manifest[id] = (
href: href,
path: _resolve(opfPath, href),
type: item.getAttribute('media-type') ?? '',
props: item.getAttribute('properties') ?? '',
);
}
final spine = <String>[];
final paths = <String>[];
for (final ref in spineEl.childElements.where((e) => e.localName == 'itemref')) {
final item = manifest[ref.getAttribute('idref')];
spine.add(item?.href ?? '');
paths.add(item?.path ?? '');
}
final toc = <({String href, String title})>[];
final nav = manifest.values.where((v) => v.props.split(' ').contains('nav')).firstOrNull;
if (nav != null) {
final doc = _xml(_file(archive, nav.path));
final navs = doc?.descendantElements.where((e) => e.localName == 'nav').toList() ?? const [];
final tocNav = navs
.where((e) => e.attributes.any((a) => a.localName == 'type' && a.value.split(' ').contains('toc')))
.firstOrNull ??
navs.firstOrNull;
for (final a in tocNav?.descendantElements.where((e) => e.localName == 'a') ?? const <XmlElement>[]) {
final href = a.getAttribute('href');
if (href == null) continue;
toc.add((href: _resolve(nav.path, href) + (href.contains('#') ? '#${href.split('#').last}' : ''),
title: _flat(a.innerText)));
}
}
if (toc.isEmpty) {
final ncxId = spineEl.getAttribute('toc');
final ncx = manifest[ncxId] ??
manifest.values.where((v) => v.type == 'application/x-dtbncx+xml').firstOrNull;
if (ncx != null) {
final doc = _xml(_file(archive, ncx.path));
for (final point in doc?.descendantElements.where((e) => e.localName == 'navPoint') ?? const <XmlElement>[]) {
final src = point.childElements.where((e) => e.localName == 'content').firstOrNull?.getAttribute('src');
final label = point.childElements.where((e) => e.localName == 'navLabel').firstOrNull;
if (src == null || label == null) continue;
toc.add((href: _resolve(ncx.path, src) + (src.contains('#') ? '#${src.split('#').last}' : ''),
title: _flat(label.innerText)));
}
}
}
return EpubBookText._(input, archive, spine, paths, toc, (children.indexOf(spineEl) + 1) * 2, overlays);
}
_Section? _section(int si) {
if (si < 0 || si >= _paths.length) return null;
return _sections.putIfAbsent(si, () {
final source = _file(_archive, _paths[si]);
if (source == null) return null;
final doc = html_parser.parse(source);
final root = doc.documentElement;
final body = doc.body;
if (root == null || body == null) return null;
final nodes = <html.Text>[];
void walk(html.Node n) {
for (final c in n.nodes) {
if (c is html.Text) {
nodes.add(c);
} else if (c is html.Element) {
walk(c);
}
}
}
walk(body);
final starts = <int>[];
final buf = StringBuffer();
for (final n in nodes) {
starts.add(buf.length);
buf.write(n.data);
}
return _Section(root, nodes, starts, buf.toString());
});
}
String sectionText(int si) => _section(si)?.text ?? '';
int sectionLength(int si) => sectionText(si).length;
/// The spine index of the document [href] names, as a media overlay or the
/// package names it, or -1.
int sectionOf(String href) {
for (var i = 0; i < spine.length; i++) {
if (MediaOverlay.sameDoc(spine[i], href)) return i;
if (i < _paths.length && MediaOverlay.sameDoc(_paths[i], href)) return i;
}
return -1;
}
/// The text of the element [id] in section [si], spaces tidied. Null when
/// the section has no such element.
String? elementText(int si, String id) {
final s = _section(si);
if (s == null) return null;
html.Element? find(html.Element e) {
if (e.id == id) return e;
for (final c in e.children) {
final hit = find(c);
if (hit != null) return hit;
}
return null;
}
final el = find(s.root);
return el == null ? null : _flat(el.text);
}
/// Where each element with an id starts in section [si]'s text: the
/// offset of its first text. Elements with no text are left out.
Map<String, int> elementOffsets(int si) {
final s = _section(si);
if (s == null) return const {};
final out = <String, int>{};
for (var k = 0; k < s.nodes.length; k++) {
for (html.Node? up = s.nodes[k].parent; up != null; up = up.parent) {
if (up is html.Element && up.id.isNotEmpty) out.putIfAbsent(up.id, () => s.starts[k]);
if (identical(up, s.root)) break;
}
}
return out;
}
/// The TOC title for a spine href, matched the way the reader matches it:
/// by file name first, then by the end of the path.
String? chapterForHref(String href) {
if (href.isEmpty || toc.isEmpty) return null;
String base(String s) => undoPercentEscapes(s.split('#').first.split('/').last).toLowerCase();
String? label(String t) => t.trim().isEmpty ? null : t.trim();
final b = base(href);
if (b.isNotEmpty) {
for (final c in toc) {
if (base(c.href) == b) return label(c.title);
}
}
final path = href.split('#').first;
for (final c in toc) {
final p = c.href.split('#').first;
if (p.isEmpty) continue;
if (path.endsWith(p) || p.endsWith(path)) return label(c.title);
}
return null;
}
/// How far through the whole book's text [offset] in section [si] is.
double fraction(int si, int offset) {
var before = 0, total = 0;
for (var i = 0; i < spine.length; i++) {
final n = sectionLength(i);
if (i < si) before += n;
total += n;
}
return total <= 0 ? 0 : ((before + offset) / total).clamp(0.0, 1.0);
}
/// Where [transcript] is in the book: the best-matching passage of any
/// section, the one nearest [near] (a fraction of the book) when two
/// match about as well. Null under [minFine].
TextMatch? findPassage(String transcript, {double? near, double minFine = 0.6}) {
final hits = <TextMatch>[];
for (var si = 0; si < spine.length; si++) {
final m = matchTranscript(sectionText(si), transcript);
if (m != null && m.fine >= minFine) hits.add((si: si, s: m.s, e: m.e, fine: m.fine));
}
if (hits.isEmpty) return null;
hits.sort((a, b) => b.fine.compareTo(a.fine));
final top = hits.where((h) => hits.first.fine - h.fine <= 0.05).toList();
if (near == null || top.length == 1) return top.first;
top.sort((a, b) => (fraction(a.si, a.s) - near).abs().compareTo((fraction(b.si, b.s) - near).abs()));
return top.first;
}
/// The CFI for [offset] in section [si], in the form the reader writes:
/// `epubcfi(/6/34!/4[body-id]/2/10/1:33)`. Null when the section has no
/// parsed text.
String? cfiAt(int si, int offset) {
final s = _section(si);
if (s == null || s.nodes.isEmpty) return null;
final root = s.root;
var k = s.nodes.length - 1;
for (var i = 0; i < s.nodes.length; i++) {
if (offset < s.starts[i] + s.nodes[i].data.length) {
k = i;
break;
}
}
final node = s.nodes[k];
final local = (offset - s.starts[k]).clamp(0, node.data.length);
final parent = node.parent;
if (parent == null) return null;
final steps = <String>['${1 + 2 * _textKids(parent).indexOf(node)}'];
for (html.Element? el = parent; el != null && !identical(el, root); el = el.parent) {
final up = el.parent;
if (up == null) break;
final id = el.attributes['id'];
steps.add('${(up.children.indexOf(el) + 1) * 2}${id == null || id.isEmpty ? '' : '[$id]'}');
}
return 'epubcfi(/$_spineStep/${(si + 1) * 2}!/${steps.reversed.join('/')}:$local)';
}
/// The section and text offset a CFI points at (a range's start). Null
/// when it doesn't resolve in this book.
({int si, int offset})? locate(String cfi) {
final m = RegExp(r'^epubcfi\((.*)\)$').firstMatch(cfi.trim());
if (m == null) return null;
final inner = m.group(1)!;
final bang = inner.indexOf('!');
if (bang < 0) return null;
final pkg = inner.substring(0, bang).split('/').where((p) => p.isNotEmpty).toList();
if (pkg.isEmpty) return null;
final spineStep = int.tryParse(pkg.last.split('[').first);
if (spineStep == null || spineStep < 2) return null;
final si = spineStep ~/ 2 - 1;
final parts = inner.substring(bang + 1).split(',');
final path = parts.length > 1 ? parts[0] + parts[1] : parts[0];
final s = _section(si);
if (s == null) return null;
var term = 0;
var steps = path;
final colon = path.lastIndexOf(':');
if (colon >= 0) {
term = int.tryParse(path.substring(colon + 1).split('[').first) ?? 0;
steps = path.substring(0, colon);
}
html.Element el = s.root;
html.Text? text;
for (final raw in steps.split('/').where((p) => p.isNotEmpty)) {
final n = int.tryParse(raw.split('[').first);
if (n == null || text != null) return null;
if (n.isEven) {
final kids = el.children;
final i = n ~/ 2 - 1;
if (i < 0 || i >= kids.length) return null;
el = kids[i];
} else {
final kids = _textKids(el);
final i = (n - 1) ~/ 2;
if (i < 0 || i >= kids.length) return null;
text = kids[i];
}
}
if (text != null) {
final k = s.nodes.indexOf(text);
if (k < 0) return null;
return (si: si, offset: s.starts[k] + term.clamp(0, text.data.length));
}
// An element: where its first text starts.
for (var k = 0; k < s.nodes.length; k++) {
for (html.Node? up = s.nodes[k].parent; up != null; up = up.parent) {
if (identical(up, el)) return (si: si, offset: s.starts[k]);
}
}
return null;
}
}
/// Book time of the narrated sentence a reading spot [cfi] falls in: the
/// last one in its section to start at or before it, or the section's first
/// when the spot comes before them all. Null when the spot isn't in [book] or
/// its section isn't narrated.
double? narrationTimeAtCfi(MediaOverlay overlay, EpubBookText book, String cfi) =>
placeCfiOnNarration(overlay, book, cfi).seconds;
/// [narrationTimeAtCfi], with how the spot was found or why it wasn't.
/// Another reader's CFI can count a chapter's elements differently (an XML
/// parse against this HTML one), so the ids it names are tried first: a
/// narrated sentence it names is the answer outright, and any other named
/// element gives a place in the text when the steps don't resolve here.
({double? seconds, String how}) placeCfiOnNarration(MediaOverlay overlay, EpubBookText book, String cfi) {
final m = RegExp(r'^epubcfi\((.*)\)$').firstMatch(cfi.trim());
final bang = m?.group(1)?.indexOf('!') ?? -1;
if (m == null || bang < 0) return (seconds: null, how: 'not a CFI');
final inner = m.group(1)!;
final pkg = inner.substring(0, bang).split('/').where((p) => p.isNotEmpty).toList();
final spineStep = pkg.isEmpty ? null : int.tryParse(pkg.last.split('[').first);
if (spineStep == null || spineStep < 2) return (seconds: null, how: 'no chapter in the CFI');
final si = spineStep ~/ 2 - 1;
final sectionOfHref = <String, int>{};
final clips = [
for (final c in overlay.clips)
if (c.fragment != null && sectionOfHref.putIfAbsent(c.textHref, () => book.sectionOf(c.textHref)) == si) c,
];
if (clips.isEmpty) return (seconds: null, how: 'chapter $si is not narrated');
// The ids the CFI names, deepest first, leaving out text assertions.
final ids = [
for (final a in RegExp(r'\[([^\]]*)\]').allMatches(inner.substring(bang + 1)))
if (a.group(1)!.isNotEmpty && !a.group(1)!.startsWith(';')) a.group(1)!.split(';').first,
].reversed.toList();
for (final id in ids) {
for (final c in clips) {
if (c.fragment == id) return (seconds: overlay.startOf(c), how: 'it names sentence $id');
}
}
final offsets = book.elementOffsets(si);
var target = book.locate(cfi)?.offset;
var how = 'its place in chapter $si';
if (target == null) {
for (final id in ids) {
final off = offsets[id];
if (off != null) {
target = off;
how = 'the element $id it names';
break;
}
}
}
if (target == null) return (seconds: null, how: 'its steps and ids are not in chapter $si here');
OverlayClip? best;
var bestOffset = -1;
for (final c in clips) {
final off = offsets[c.fragment];
if (off == null || off > target) continue;
if (off >= bestOffset) {
best = c;
bestOffset = off;
}
}
final pick = best ?? clips.first;
return (seconds: overlay.startOf(pick), how: how);
}